OpenRaiser/Intern-Atlas huggingface dataset:
Program Transformations for Asynchronous and Batched Query Submission
Venue: arXiv cs.DB 2014
Year: 2014

The performance of database/Web-service backed applications can be significantly improved by asynchronous submission of queries/requests well ahead of the point where the results are needed, so that results are likely to have been fetched already when they are actually needed. However, manually writing applications to exploit asynchronous query submission is tedious and error-prone. In this paper we address the issue of automatically transforming a program written assuming synchronous query submission, to one that exploits asynchronous query submission. Our program transformation method is based on data flow analysis and is framed as a set of transformation rules. Our rules can handle query executions within loops, unlike some of the earlier work in this area. We also present a novel approach that, at runtime, can combine multiple asynchronous requests into batches, thereby achieving the benefits of batching in addition to that of asynchronous submission. We have built a tool that implements our transformation techniques on Java programs that use JDBC calls; our tool can be extended to handle Web service calls. We have carried out a detailed experimental study on several real-life applications, which shows the effectiveness of the proposed rewrite techniques, both in terms of their applicability and the performance gains achieved.
On the Integrality Ratio of the Subtour LP for Euclidean TSP
Venue: arXiv cs.DM 2014
Year: 2014

A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is $4/3$. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was $8/7$. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.
Tripartite Graph Clustering for Dynamic Sentiment Analysis on Social Media
Venue: arXiv cs.SI 2014
Year: 2014

The growing popularity of social media (e.g, Twitter) allows users to easily share information with each other and influence others by expressing their own sentiments on various subjects. In this work, we propose an unsupervised \emph{tri-clustering} framework, which analyzes both user-level and tweet-level sentiments through co-clustering of a tripartite graph. A compelling feature of the proposed framework is that the quality of sentiment clustering of tweets, users, and features can be mutually improved by joint clustering. We further investigate the evolution of user-level sentiments and latent feature vectors in an online framework and devise an efficient online algorithm to sequentially update the clustering of tweets, users and features with newly arrived data. The online framework not only provides better quality of both dynamic user-level and tweet-level sentiment analysis, but also improves the computational and storage efficiency. We verified the effectiveness and efficiency of the proposed approaches on the November 2012 California ballot Twitter data.
Modelling the Lexicon in Unsupervised Part of Speech Induction
Venue: arXiv cs.CL 2014
Year: 2014

Automatically inducing the syntactic part-of-speech categories for words in text is a fundamental task in Computational Linguistics. While the performance of unsupervised tagging models has been slowly improving, current state-of-the-art systems make the obviously incorrect assumption that all tokens of a given word type must share a single part-of-speech tag. This one-tag-per-type heuristic counters the tendency of Hidden Markov Model based taggers to over generate tags for a given word type. However, it is clearly incompatible with basic syntactic theory. In this paper we extend a state-of-the-art Pitman-Yor Hidden Markov Model tagger with an explicit model of the lexicon. In doing so we are able to incorporate a soft bias towards inducing few tags per type. We develop a particle filter for drawing samples from the posterior of our model and present empirical results that show that our model is competitive with and faster than the state-of-the-art without making any unrealistic restrictions.
Why Are You More Engaged? Predicting Social Engagement from Word Use
Venue: arXiv cs.SI 2014
Year: 2014

We present a study to analyze how word use can predict social engagement behaviors such as replies and retweets in Twitter. We compute psycholinguistic category scores from word usage, and investigate how people with different scores exhibited different reply and retweet behaviors on Twitter. We also found psycholinguistic categories that show significant correlations with such social engagement behaviors. In addition, we have built predictive models of replies and retweets from such psycholinguistic category based features. Our experiments using a real world dataset collected from Twitter validates that such predictions can be done with reasonable accuracy.
Extending ALCQIO with reachability
Venue: arXiv cs.LO 2014
Year: 2014

We introduce a description logic ALCQIO_{b,Re} which adds reachability assertions to ALCQIO, a sub-logic of the two-variable fragment of first order logic with counting quantifiers. ALCQIO_{b,Re} is well-suited for applications in software verification and shape analysis. Shape analysis requires expressive logics which can express reachability and have good computational properties. We show that ALCQIO_{b,Re} can describe complex data structures with a high degree of sharing and allows compositions such as list of trees. We show that the finite satisfiability and implication problems of ALCQIO_{b,Re}-formulae are polynomial-time reducible to finite satisfiability of ALCQIO-formulae. As a consequence, we get that finite satisfiability and finite implication in ALCQIO_{b,Re} are NEXPTIME-complete. Description logics with transitive closure constructors have been studied before, but ALCQIO_{b,Re} is the first description logic that remains decidable on finite structures while allowing at the same time nominals, inverse roles, counting quantifiers and reachability assertions,
An Optimal Decoding Strategy for Physical-layer Network Coding over Multipath Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

We present an optimal decoder for physical-layer network coding (PNC) in a multipath fading channels. Previous studies on PNC have largely focused on the single path case. For PNC, multipath not only introduces inter-symbol interference (ISI), but also cross-symbol interference (Cross-SI) between signals simultaneously transmitted by multiple users. In this paper, we assume the transmitters do not have channel state information (CSI). The relay in the PNC system, however, has CSI. The relay makes use of a belief propagation (BP) algorithm to decode the multipath-distorted signals received from multiple users into a network-coded packet. We refer to our multipath decoding algorithm as MP-PNC. Our simulation results show that, benchmarked against synchronous PNC over a one-path channel, the bit error rate (BER) performance penalty of MP-PNC under a two-tap ITU channel model can be kept within 0.5dB. Moreover, it outperforms a MUD-XOR algorithm by 3dB -- MUD-XOR decodes the individual information from both users explicitly before performing the XOR network-coding mapping. Although the framework of fading-channel PNC presented in this paper is demonstrated based on two-path and three-path channel models, our algorithm can be easily extended to cases with more than three paths.
Three Experiments to Analyze the Nature of the Heat Spreader
Venue: arXiv cs.OH 2014
Year: 2014

In this paper, we describe ongoing work to investigate the properties of the heat spreader, and its implication on architecture research. In specific, we conduct two experiments to quantify the heat distribution across the surface of a spreader during normal operation. The first experiment uses T-type thermocouples, to find the temperature difference across different points on the spreader. We observe about a 6 degree celsius temperature difference on average. In the second experiment, we try to capture the temperature gradients using an infrared camera. However, this experiment was inconclusive because of some practical constraints such as the low emissivity of the spreader. We conclude that to properly model the spreader, it is necessary to conduct detailed finite element simulations. We describe a method to accurately measure the thermal conductivity of the heat spreader such that it can be used to compute the steady state temperature distribution across the spreader.
A Parallel Memetic Algorithm to Solve the Vehicle Routing Problem with Time Windows
Venue: arXiv cs.DC 2014
Year: 2014

This paper presents a parallel memetic algorithm for solving the vehicle routing problem with time windows (VRPTW). The VRPTW is a well-known NP-hard discrete optimization problem with two objectives. The main objective is to minimize the number of vehicles serving customers scattered on the map, and the second one is to minimize the total distance traveled by the vehicles. Here, the fleet size is minimized in the first phase of the proposed method using the parallel heuristic algorithm (PHA), and the traveled distance is minimized in the second phase by the parallel memetic algorithm (PMA). In both parallel algorithms, the parallel components co-operate periodically in order to exchange the best solutions found so far. An extensive experimental study performed on the Gehring and Homberger's benchmark proves the high convergence capabilities and robustness of both PHA and PMA. Also, we present the speedup analysis of the PMA.
Bounded Delay Scheduling with Packet Dependencies
Venue: arXiv cs.NI 2014
Year: 2014

A common situation occurring when dealing with multimedia traffic is having large data frames fragmented into smaller IP packets, and having these packets sent independently through the network. For real-time multimedia traffic, dropping even few packets of a frame may render the entire frame useless. Such traffic is usually modeled as having {\em inter-packet dependencies}. We study the problem of scheduling traffic with such dependencies, where each packet has a deadline by which it should arrive at its destination. Such deadlines are common for real-time multimedia applications, and are derived from stringent delay constraints posed by the application. The figure of merit in such environments is maximizing the system's {\em goodput}, namely, the number of frames successfully delivered. We study online algorithms for the problem of maximizing goodput of delay-bounded traffic with inter-packet dependencies, and use competitive analysis to evaluate their performance. We present competitive algorithms for the problem, as well as matching lower bounds that are tight up to a constant factor. We further present the results of a simulation study which further validates our algorithmic approach and shows that insights arising from our analysis are indeed manifested in practice.
A Three-State Received Signal Strength Model for Device-free Localization
Venue: arXiv cs.OH 2014
Year: 2014

The indoor radio propagation channel is typically modeled as a two-state time-variant process where one of the states represents the channel when the environment is static, whereas the other state characterizes the medium when it is altered by people. In this paper, the aforementioned process is augmented with an additional state. It is shown that the changes in received signal strength are dictated by: i) electronic noise, when a person is not present in the monitored area; ii) reflection, when a person is moving in the close vicinity of the line-of-sight; iii) shadowing, when a person is obstructing the line-of-sight component of the transmitter-receiver pair. Statistical and spatial models for the three states are derived and the models are empirically validated. Based on the models, a simplistic device-free localization application is designed which aims to: first, estimate the temporal state of the channel using a hidden Markov model; second, track a person using a particle filter. The results suggest that the tracking accuracy is enhanced by at least 65% while the link's sensitivity region is increased by 100% or more with respect to empirical models presented in earlier works.
'Beating the news' with EMBERS: Forecasting Civil Unrest using Open Source Indicators
Venue: arXiv cs.SI 2014
Year: 2014

We describe the design, implementation, and evaluation of EMBERS, an automated, 24x7 continuous system for forecasting civil unrest across 10 countries of Latin America using open source indicators such as tweets, news sources, blogs, economic indicators, and other data sources. Unlike retrospective studies, EMBERS has been making forecasts into the future since Nov 2012 which have been (and continue to be) evaluated by an independent T&E team (MITRE). Of note, EMBERS has successfully forecast the uptick and downtick of incidents during the June 2013 protests in Brazil. We outline the system architecture of EMBERS, individual models that leverage specific data sources, and a fusion and suppression engine that supports trading off specific evaluation criteria. EMBERS also provides an audit trail interface that enables the investigation of why specific predictions were made along with the data utilized for forecasting. Through numerous evaluations, we demonstrate the superiority of EMBERS over baserate methods and its capability to forecast significant societal happenings.
Synthesizing Finite-state Protocols from Scenarios and Requirements
Venue: arXiv cs.FL 2014
Year: 2014

Scenarios, or Message Sequence Charts, offer an intuitive way of describing the desired behaviors of a distributed protocol. In this paper we propose a new way of specifying finite-state protocols using scenarios: we show that it is possible to automatically derive a distributed implementation from a set of scenarios augmented with a set of safety and liveness requirements, provided the given scenarios adequately \emph{cover} all the states of the desired implementation. We first derive incomplete state machines from the given scenarios, and then synthesis corresponds to completing the transition relation of individual processes so that the global product meets the specified requirements. This completion problem, in general, has the same complexity, PSPACE, as the verification problem, but unlike the verification problem, is NP-complete for a constant number of processes. We present two algorithms for solving the completion problem, one based on a heuristic search in the space of possible completions and one based on OBDD-based symbolic fixpoint computation. We evaluate the proposed methodology for protocol specification and the effectiveness of the synthesis algorithms using the classical alternating-bit protocol.
Mathematical Model of Semantic Look - An Efficient Context Driven Search Engine
Venue: arXiv cs.IR 2014
Year: 2014

The WorldWideWeb (WWW) is a huge conservatory of web pages. Search Engines are key applications that fetch web pages for the user query. In the current generation web architecture, search engines treat keywords provided by the user as isolated keywords without considering the context of the user query. This results in a lot of unrelated pages or links being displayed to the user. Semantic Web is based on the current web with a revised framework to display a more precise result set as response to a user query. The current web pages need to be annotated by finding relevant meta data to be added to each of them, so that they become useful to Semantic Web search engines. Semantic Look explores the context of user query by processing the Semantic information recorded in the web pages. It is compared with an existing algorithm called OntoLook and it is shown that Semantic Look is a better optimized search engine by being more than twice as fast as OntoLook.
Sparse Gröbner Bases: the Unmixed Case
Venue: arXiv cs.SC 2014
Year: 2014

Toric (or sparse) elimination theory is a framework developped during the last decades to exploit monomial structures in systems of Laurent polynomials. Roughly speaking, this amounts to computing in a \emph{semigroup algebra}, \emph{i.e.} an algebra generated by a subset of Laurent monomials. In order to solve symbolically sparse systems, we introduce \emph{sparse Gröbner bases}, an analog of classical Gröbner bases for semigroup algebras, and we propose sparse variants of the $F_5$ and FGLM algorithms to compute them. Our prototype "proof-of-concept" implementation shows large speed-ups (more than 100 for some examples) compared to optimized (classical) Gröbner bases software. Moreover, in the case where the generating subset of monomials corresponds to the points with integer coordinates in a normal lattice polytope $\mathcal P\subset\mathbb R^n$ and under regularity assumptions, we prove complexity bounds which depend on the combinatorial properties of $\mathcal P$. These bounds yield new estimates on the complexity of solving $0$-dim systems where all polynomials share the same Newton polytope (\emph{unmixed case}). For instance, we generalize the bound $\min(n_1,n_2)+1$ on the maximal degree in a Gröbner basis of a $0$-dim. bilinear system with blocks of variables of sizes $(n_1,n_2)$ to the multilinear case: $\sum n_i - \max(n_i)+1$. We also propose a variant of Fröberg's conjecture which allows us to estimate the complexity of solving overdetermined sparse systems.
On low treewidth graphs and supertrees
Venue: arXiv cs.DM 2014
Year: 2014

Compatibility of unrooted phylogenetic trees is a well studied problem in phylogenetics. It asks to determine whether for a set of k input trees there exists a larger tree (called a supertree) that contains the topologies of all k input trees. When any such supertree exists we call the instance compatible and otherwise incompatible. It is known that the problem is NP-hard and FPT, although a constructive FPT algorithm is not known. It has been shown that whenever the treewidth of an auxiliary structure known as the display graph is strictly larger than the number of input trees, the instance is incompatible. Here we show that whenever the treewidth of the display graph is at most 2, the instance is compatible. Furthermore, we give a polynomial-time algorithm to construct a supertree in this case. Finally, we demonstrate both compatible and incompatible instances that have display graphs with treewidth 3, highlighting that the treewidth of the display graph is (on its own) not sufficient to determine compatibility.
Optimal Discrete Power Control in Poisson-Clustered Ad Hoc Networks
Venue: arXiv cs.IT 2014
Year: 2014

Power control in a digital handset is practically implemented in a discrete fashion and usually such a discrete power control (DPC) scheme is suboptimal. In this paper, we first show that in a Poison-distributed ad hoc network, if DPC is properly designed with a certain condition satisfied, it can strictly work better than constant power control (i.e. no power control) in terms of average signal-to-interference ratio, outage probability and spatial reuse. This motivates us to propose an $N$-layer DPC scheme in a wireless clustered ad hoc network, where transmitters and their intended receivers in circular clusters are characterized by a Poisson cluster process (PCP) on the plane $\mathbb{R}^2$. The cluster of each transmitter is tessellated into $N$-layer annuli with transmit power $P_i$ adopted if the intended receiver is located at the $i$-th layer. Two performance metrics of transmission capacity (TC) and outage-free spatial reuse factor are redefined based on the $N$-layer DPC. The outage probability of each layer in a cluster is characterized and used to derive the optimal power scaling law $P_i=Θ\left(η_i^{-\fracα{2}}\right)$, with $η_i$ the probability of selecting power $P_i$ and $α$ the path loss exponent. Moreover, the specific design approaches to optimize $P_i$ and $N$ based on $η_i$ are also discussed. Simulation results indicate that the proposed optimal $N$-layer DPC significantly outperforms other existing power control schemes in terms of TC and spatial reuse.
Multicast-aware Caching for Small Cell Networks
Venue: arXiv cs.NI 2014
Year: 2014

The deployment of small cells is expected to gain huge momentum in the near future, as a solution for managing the skyrocketing mobile data demand growth. Local caching of popular files at the small cell base stations has been recently proposed, aiming at reducing the traffic incurred when transferring the requested content from the core network to the users. In this paper, we propose and analyze a novel caching approach that can achieve significantly lower traffic compared to the traditional caching schemes. Our cache design policy carefully takes into account the fact that an operator can serve the requests for the same file that happen at nearby times via a single multicast transmission. The latter incurs less traffic as the requested file is transmitted to the users only once, rather than with many unicast transmissions. Systematic experiments demonstrate the effectiveness of our approach, as compared to the existing caching schemes.
Cayley Analysis of Mechanism Configuration Spaces using CayMos: Software Functionalities and Architecture
Venue: arXiv cs.CG 2014
Year: 2014

For a common class of 2D mechanisms called 1-dof tree decomposable linkages, we present a software CayMos which uses new theoretical results to implement efficient algorithmic solutions for: (a) meaningfully representing and visualizing the connected components in the Euclidean realization space; (b) finding a path of continuous motion between two realizations in the same connected component, with or without restricting the realization type (sometimes called orientation type); (c) finding two ``closest'' realizations in different connected components.
Coordinated Direct and Relay Schemes for Two-Hop Communication in VANETS
Venue: arXiv cs.NI 2014
Year: 2014

In order to accommodate increasing need and offer communication with high performance, both vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) communications are exploited. The advantages of static nodes and vehicular nodes are combined to achieve an optimal routing scheme. In this paper, we consider the communications between a static node and the vehicular nodes moving in an adjacent area of it. The adjacent area is defined as the zone where a vehicular can communicate with the static node within maximum two hops. We only consider single-hop and two-hop transmissions because these transmissions can be considered as building blocks to construct transmissions with a higher number of hops. Different cases in which an uplink or a downlink for the two-hop user combined with an uplink or a downlink for the single-hop user correspond to different CDR schemes. Using side information to intentionally cancel the interference, Network Coding (NC), CDR, overhearing and multi-way schemes aggregate communications flows in order to increase the performance of the network. We apply the mentioned schemes to a V2I network and propose novel schemes to optimally arrange and combine the transmissions.
Some mathematical remarks on the polynomial selection in NFS
Venue: arXiv cs.CR 2014
Year: 2014

In this work, we consider the proportion of smooth (free of large prime factors) values of a binary form $F(X_1,X_2)\in\Z[X_1,X_2]$. In a particular case, we give an asymptotic equivalent for this proportion which depends on $F$. This is related to Murphy's $α$ function, which is known in the cryptographic community, but which has not been studied before from a mathematical point of view. Our result proves that, when $α(F)$ is small, $F$ has a high proportion of smooth values. This has consequences on the first step, called polynomial selection, of the Number Field Sieve, the fastest algorithm of integer factorization.