OpenRaiser/Intern-Atlas huggingface dataset:
Querying Evolving Graphs with Portal
Venue: arXiv cs.DB 2016
Year: 2016

Graphs are used to represent a plethora of phenomena, from the Web and social networks, to biological pathways, to semantic knowledge bases. Arguably the most interesting and important questions one can ask about graphs have to do with their evolution. Which Web pages are showing an increasing popularity trend? How does influence propagate in social networks? How does knowledge evolve? This paper proposes a logical model of an evolving graph called a TGraph, which captures evolution of graph topology and of its vertex and edge attributes. We present a compositional temporal graph algebra TGA, and show a reduction of TGA to temporal relational algebra with graph-specific primitives. We formally study the properties of TGA, and also show that it is sufficient to concisely express a wide range of common use cases. We describe an implementation of our model and algebra in Portal, built on top of Apache Spark / GraphX. We conduct extensive experiments on real datasets, and show that Portal scales.
Spectrum Sharing Between A Surveillance Radar and Secondary Wi-Fi Networks
Venue: arXiv cs.IT 2016
Year: 2016

Co-existence between unlicensed networks that share spectrum spatio-temporally with terrestrial (e.g. Air Traffic Control) and shipborne radars in 3-GHz band is attracting significant interest. Similar to every primary-secondary coexistence scenario, interference from unlicensed devices to a primary receiver must be within acceptable bounds. In this work, we formulate the spectrum sharing problem between a pulsed, search radar (primary) and 802.11 WLAN as the secondary. We compute the protection region for such a search radar for a) a single secondary user (initially) as well as b) a random spatial distribution of multiple secondary users. Furthermore, we also analyze the interference to the WiFi devices from the radar's transmissions to estimate the impact on achievable WLAN throughput as a function of distance to the primary radar.
Spatial Continuum Extensions of Asymmetric Gaussian Channels (Multiple Access and Broadcast)
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a new model called \emph{spatial continuum asymmetric channels} to study the channel capacity region of asymmetric scenarios in which either one source transmits to a spatial density of receivers or a density of transmitters transmit to a unique receiver.This approach is built upon the classical broadcast channel (BC) and multiple access channel (MAC). For the sake of consistency, the study is limited to Gaussian channels with power constraints and is restricted to the asymptotic regime (zero-error capacity).The reference scenario comprises one base station (BS) in Tx or Rx mode, a spatial random distribution of nodes (resp. in Rx or Tx mode) characterized by a probability spatial density $u(x)$ and a request for a quantity of information with no delay constraint. This system is modeled as an $\infty-$user asymmetric channel (BC or MAC). To derive the properties of this model, a spatial discretization is performed and the equivalence with either a BC or MAC is established. A discretization sequence is then defined to refine infinitely the approximation. Achievability and capacity results are obtained in the limit of this sequence. The uniform capacity is then defined as the maximal symmetric achievable rate at which the distributed users can transmit/receive with no delay constraint.The capacity region is also established as the set of information distributions that are achievable. The tightness of these limits and their practical interest are briefly illustrated and discussed.
Interactive Multiple Model Estimation of Doubly-Selective Channels for OFDM systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose an algorithm for channel estimation, acquisition and tracking, for orthogonal frequency division multiplexing (OFDM) systems. The proposed algorithm is suitable for vehicular communications that encounter very high mobility. A preamble sequence is used to derive an initial estimate of the channel using least squares (LS). The temporal variation of the channel within one OFDM symbol is approximated by two complex exponential basis expansion models (CE-BEM). One of the Fourier-based BEMs is intended to capture the low frequencies in the channel (slow variations corresponding to low Doppler), while the other is destined to capture high frequencies (fast variations corresponding to high Doppler). Kalman filtering is employed to track the BEM coefficients iteratively on an OFDM symbol-by-symbol basis. An interactive multiple model (IMM) estimator is implemented to dynamically mix the estimates obtained by the two Kalman filters, each of which matched to one of the BEMs. Extensive numerical simulations are conducted to signify the gain obtained by the proposed combining technique.
Distributed Online Data Aggregation in Dynamic Graphs
Venue: arXiv cs.DC 2016
Year: 2016

We consider the problem of aggregating data in a dynamic graph, that is, aggregating the data that originates from all nodes in the graph to a specific node, the sink. We are interested in giving lower bounds for this problem, under different kinds of adversaries. In our model, nodes are endowed with unlimited memory and unlimited computational power. Yet, we assume that communications between nodes are carried out with pairwise interactions, where nodes can exchange control information before deciding whether they transmit their data or not, given that each node is allowed to transmit its data at most once. When a node receives a data from a neighbor, the node may aggregate it with its own data. We consider three possible adversaries: the online adaptive adversary, the oblivious adversary , and the randomized adversary that chooses the pairwise interactions uniformly at random. For the online adaptive and the oblivious adversary, we give impossibility results when nodes have no knowledge about the graph and are not aware of the future. Also, we give several tight bounds depending on the knowledge (be it topology related or time related) of the nodes. For the randomized adversary, we show that the Gathering algorithm, which always commands a node to transmit, is optimal if nodes have no knowledge at all. Also, we propose an algorithm called Waiting Greedy, where a node either waits or transmits depending on some parameter, that is optimal when each node knows its future pairwise interactions with the sink.
Efficient Index for Weighted Sequences
Venue: arXiv cs.DS 2016
Year: 2016

The problem of finding factors of a text string which are identical or similar to a given pattern string is a central problem in computer science. A generalised version of this problem consists in implementing an index over the text to support efficient on-line pattern queries. We study this problem in the case where the text is weighted: for every position of the text and every letter of the alphabet a probability of occurrence of this letter at this position is given. Sequences of this type, also called position weight matrices, are commonly used to represent imprecise or uncertain data. A weighted sequence may represent many different strings, each with probability of occurrence equal to the product of probabilities of its letters at subsequent positions. Given a probability threshold $1/z$, we say that a pattern string $P$ matches a weighted text at position $i$ if the product of probabilities of the letters of $P$ at positions $i,\ldots,i+|P|-1$ in the text is at least $1/z$. In this article, we present an $O(nz)$-time construction of an $O(nz)$-sized index that can answer pattern matching queries in a weighted text in optimal time improving upon the state of the art by a factor of $z \log z$. Other applications of this data structure include an $O(nz)$-time construction of the weighted prefix table and an $O(nz)$-time computation of all covers of a weighted sequence, which improve upon the state of the art by the same factor.
GraphPrints: Towards a Graph Analytic Method for Network Anomaly Detection
Venue: arXiv cs.CR 2016
Year: 2016

This paper introduces a novel graph-analytic approach for detecting anomalies in network flow data called GraphPrints. Building on foundational network-mining techniques, our method represents time slices of traffic as a graph, then counts graphlets -- small induced subgraphs that describe local topology. By performing outlier detection on the sequence of graphlet counts, anomalous intervals of traffic are identified, and furthermore, individual IPs experiencing abnormal behavior are singled-out. Initial testing of GraphPrints is performed on real network data with an implanted anomaly. Evaluation shows false positive rates bounded by 2.84% at the time-interval level, and 0.05% at the IP-level with 100% true positive rates at both.
A Dual Embedding Space Model for Document Ranking
Venue: arXiv cs.IR 2016
Year: 2016

A fundamental goal of search engines is to identify, given a query, documents that have relevant text. This is intrinsically difficult because the query and the document may use different vocabulary, or the document may contain query words without being relevant. We investigate neural word embeddings as a source of evidence in document ranking. We train a word2vec embedding model on a large unlabelled query corpus, but in contrast to how the model is commonly used, we retain both the input and the output projections, allowing us to leverage both the embedding spaces to derive richer distributional relationships. During ranking we map the query words into the input space and the document words into the output space, and compute a query-document relevance score by aggregating the cosine similarities across all the query-document word pairs. We postulate that the proposed Dual Embedding Space Model (DESM) captures evidence on whether a document is about a query term in addition to what is modelled by traditional term-frequency based approaches. Our experiments show that the DESM can re-rank top documents returned by a commercial Web search engine, like Bing, better than a term-matching based signal like TF-IDF. However, when ranking a larger set of candidate documents, we find the embeddings-based approach is prone to false positives, retrieving documents that are only loosely related to the query. We demonstrate that this problem can be solved effectively by ranking based on a linear mixture of the DESM and the word counting features.
Synthesizing a Lego Forklift Controller in GR(1): A Case Study
Venue: arXiv cs.SE 2016
Year: 2016

Reactive synthesis is an automated procedure to obtain a correct-by-construction reactive system from a given specification. GR(1) is a well-known fragment of linear temporal logic (LTL) where synthesis is possible using a polynomial symbolic algorithm. We conducted a case study to learn about the challenges that software engineers may face when using GR(1) synthesis for the development of a reactive robotic system. In the case study we developed two variants of a forklift controller, deployed on a Lego robot. The case study employs LTL specification patterns as an extension of the GR(1) specification language, an examination of two specification variants for execution scheduling, traceability from the synthesized controller to constraints in the specification, and generated counter strategies to support understanding reasons for unrealizability. We present the specifications we developed, our observations, and challenges faced during the case study.
Specification Format for Reactive Synthesis Problems
Venue: arXiv cs.LO 2016
Year: 2016

Automatic synthesis from a given specification automatically constructs correct implementation. This frees the user from the mundane implementation work, but still requires the specification. But is specifying easier than implementing? In this paper, we propose a user-friendly format to ease the specification work, in particularly, that of specifying partial implementations. Also, we provide scripts to convert specifications in the new format into the SYNTCOMP format, thus benefiting from state of the art synthesizers.
GECKA3D: A 3D Game Engine for Commonsense Knowledge Acquisition
Venue: arXiv cs.MM 2016
Year: 2016

Commonsense knowledge representation and reasoning is key for tasks such as artificial intelligence and natural language understanding. Since commonsense consists of information that humans take for granted, gathering it is an extremely difficult task. In this paper, we introduce a novel 3D game engine for commonsense knowledge acquisition (GECKA3D) which aims to collect commonsense from game designers through the development of serious games. GECKA3D integrates the potential of serious games and games with a purpose. This provides a platform for the acquisition of re-usable and multi-purpose knowledge, and also enables the development of games that can provide entertainment value and teach players something meaningful about the actual world they live in.
Discriminative Sparse Neighbor Approximation for Imbalanced Learning
Venue: arXiv cs.CV 2016
Year: 2016

Data imbalance is common in many vision tasks where one or more classes are rare. Without addressing this issue conventional methods tend to be biased toward the majority class with poor predictive accuracy for the minority class. These methods further deteriorate on small, imbalanced data that has a large degree of class overlap. In this study, we propose a novel discriminative sparse neighbor approximation (DSNA) method to ameliorate the effect of class-imbalance during prediction. Specifically, given a test sample, we first traverse it through a cost-sensitive decision forest to collect a good subset of training examples in its local neighborhood. Then we generate from this subset several class-discriminating but overlapping clusters and model each as an affine subspace. From these subspaces, the proposed DSNA iteratively seeks an optimal approximation of the test sample and outputs an unbiased prediction. We show that our method not only effectively mitigates the imbalance issue, but also allows the prediction to extrapolate to unseen data. The latter capability is crucial for achieving accurate prediction on small dataset with limited samples. The proposed imbalanced learning method can be applied to both classification and regression tasks at a wide range of imbalance levels. It significantly outperforms the state-of-the-art methods that do not possess an imbalance handling mechanism, and is found to perform comparably or even better than recent deep learning methods by using hand-crafted features only.
Locally rewritable codes for resistive memories
Venue: arXiv cs.IT 2016
Year: 2016

We propose locally rewritable codes (LWC) for resistive memories inspired by locally repairable codes (LRC) for distributed storage systems. Small values of repair locality of LRC enable fast repair of a single failed node since the lost data in the failed node can be recovered by accessing only a small fraction of other nodes. By using rewriting locality, LWC can improve endurance limit and power consumption which are major challenges for resistive memories. We point out the duality between LRC and LWC, which indicates that existing construction methods of LRC can be applied to construct LWC.
Maintenance of Automated Test Suites in Industry: An Empirical study on Visual GUI Testing
Venue: arXiv cs.SE 2016
Year: 2016

Context: Verification and validation (V&V) activities make up 20 to 50 percent of the total development costs of a software system in practice. Test automation is proposed to lower these V&V costs but available research only provides limited empirical data from industrial practice about the maintenance costs of automated tests and what factors affect these costs. In particular, these costs and factors are unknown for automated GUI-based testing. Objective: This paper addresses this lack of knowledge through analysis of the costs and factors associated with the maintenance of automated GUI-based tests in industrial practice. Method: An empirical study at two companies, Siemens and Saab, is reported where interviews about, and empirical work with, Visual GUI Testing is performed to acquire data about the technique's maintenance costs and feasibility. Results: 13 factors are observed that affect maintenance, e.g. tester knowledge/experience and test case complexity. Further, statistical analysis shows that developing new test scripts is costlier than maintenance but also that frequent maintenance is less costly than infrequent, big bang maintenance. In addition a cost model, based on previous work, is presented that estimates the time to positive return on investment (ROI) of test automation compared to manual testing. Conclusions: It is concluded that test automation can lower overall software development costs of a project whilst also having positive effects on software quality. However, maintenance costs can still be considerable and the less time a company currently spends on manual testing, the more time is required before positive, economic, ROI is reached after automation.
How proofs are prepared at Camelot
Venue: arXiv cs.DS 2016
Year: 2016

We study a design framework for robust, independently verifiable, and workload-balanced distributed algorithms working on a common input. An algorithm based on the framework is essentially a distributed encoding procedure for a Reed--Solomon code, which enables (a) robustness against byzantine failures with intrinsic error-correction and identification of failed nodes, and (b) independent randomized verification to check the entire computation for correctness, which takes essentially no more resources than each node individually contributes to the computation. The framework builds on recent Merlin--Arthur proofs of batch evaluation of Williams~[{\em Electron.\ Colloq.\ Comput.\ Complexity}, Report TR16-002, January 2016] with the observation that {\em Merlin's magic is not needed} for batch evaluation---mere Knights can prepare the proof, in parallel, and with intrinsic error-correction. The contribution of this paper is to show that in many cases the verifiable batch evaluation framework admits algorithms that match in total resource consumption the best known sequential algorithm for solving the problem. As our main result, we show that the $k$-cliques in an $n$-vertex graph can be counted {\em and} verified in per-node $O(n^{(ω+ε)k/6})$ time and space on $O(n^{(ω+ε)k/6})$ compute nodes, for any constant $ε>0$ and positive integer $k$ divisible by $6$, where $2\leqω<2.3728639$ is the exponent of matrix multiplication. This matches in total running time the best known sequential algorithm, due to Ne{š}et{ř}il and Poljak [{\em Comment.~Math.~Univ.~Carolin.}~26 (1985) 415--419], and considerably improves its space usage and parallelizability. Further results include novel algorithms for counting triangles in sparse graphs, computing the chromatic polynomial of a graph, and computing the Tutte polynomial of a graph.
Biclustering Readings and Manuscripts via Non-negative Matrix Factorization, with Application to the Text of Jude
Venue: arXiv cs.LG 2016
Year: 2016

The text-critical practice of grouping witnesses into families or texttypes often faces two obstacles: Contamination in the manuscript tradition, and co-dependence in identifying characteristic readings and manuscripts. We introduce non-negative matrix factorization (NMF) as a simple, unsupervised, and efficient way to cluster large numbers of manuscripts and readings simultaneously while summarizing contamination using an easy-to-interpret mixture model. We apply this method to an extensive collation of the New Testament epistle of Jude and show that the resulting clusters correspond to human-identified textual families from existing research.
Universality of causal graph dynamics
Venue: arXiv cs.DM 2016
Year: 2016

Causal Graph Dynamics generalize Cellular Automata, extending them to bounded degree, time varying graphs. The dynamics rewrite the graph at each time step with respect to two physics-like symmetries: causality (bounded speed of information) and homogeneity (the rewriting acts the same everywhere on the graph, at every time step). Universality is the ability simulating every other instances of another (or the same) model of computation. In this work, we study three different notions of simulation for Causal Graph Dynamics, each of them leading to a definition of universality.
Inv-ASKIT: A Parallel Fast Diret Solver for Kernel Matrices
Venue: arXiv cs.NA 2016
Year: 2016

We present a parallel algorithm for computing the approximate factorization of an $N$-by-$N$ kernel matrix. Once this factorization has been constructed (with $N \log^2 N $ work), we can solve linear systems with this matrix with $N \log N $ work. Kernel matrices represent pairwise interactions of points in metric spaces. They appear in machine learning, approximation theory, and computational physics. Kernel matrices are typically dense (matrix multiplication scales quadratically with $N$) and ill-conditioned (solves can require 100s of Krylov iterations). Thus, fast algorithms for matrix multiplication and factorization are critical for scalability. Recently we introduced ASKIT, a new method for approximating a kernel matrix that resembles N-body methods. Here we introduce INV-ASKIT, a factorization scheme based on ASKIT. We describe the new method, derive complexity estimates, and conduct an empirical study of its accuracy and scalability. We report results on real-world datasets including "COVTYPE" ($0.5$M points in 54 dimensions), "SUSY" ($4.5$M points in 8 dimensions) and "MNIST" (2M points in 784 dimensions) using shared and distributed memory parallelism. In our largest run we approximately factorize a dense matrix of size 32M $\times$ 32M (generated from points in 64 dimensions) on 4,096 Sandy-Bridge cores. To our knowledge these results improve the state of the art by several orders of magnitude.
Finding the different patterns in buildings data using bag of words representation with clustering
Venue: arXiv cs.AI 2016
Year: 2016

The understanding of the buildings operation has become a challenging task due to the large amount of data recorded in energy efficient buildings. Still, today the experts use visual tools for analyzing the data. In order to make the task realistic, a method has been proposed in this paper to automatically detect the different patterns in buildings. The K Means clustering is used to automatically identify the ON (operational) cycles of the chiller. In the next step the ON cycles are transformed to symbolic representation by using Symbolic Aggregate Approximation (SAX) method. Then the SAX symbols are converted to bag of words representation for hierarchical clustering. Moreover, the proposed technique is applied to real life data of adsorption chiller. Additionally, the results from the proposed method and dynamic time warping (DTW) approach are also discussed and compared.
Optimal De-Anonymization in Random Graphs with Community Structure
Venue: arXiv cs.SI 2016
Year: 2016

Anonymized social network graphs published for academic or advertisement purposes are subject to de-anonymization attacks by leveraging side information in the form of a second, public social network graph correlated with the anonymized graph. This is because the two are from the same underlying graph of true social relationships. In this paper, we (i) characterize the maximum a posteriori (MAP) estimates of user identities for the anonymized graph and (ii) provide sufficient conditions for successful de-anonymization for underlying graphs with community structure. Our results generalize prior work that assumed underlying graphs of Erdős-Rényi type, in addition to proving the optimality of the attack strategy adopted in the prior work.