OpenRaiser/Intern-Atlas huggingface dataset:
A Stitch in Time Saves Nine -- SPARQL querying of Property Graphs using Gremlin Traversals
Venue: arXiv cs.DB 2018
Year: 2018

Knowledge graphs have become popular over the past years and frequently rely on the Resource Description Framework (RDF) or Property Graphs (PG) as underlying data models. However, the query languages for these two data models -- SPARQL for RDF and Gremlin for property graph traversal -- are lacking interoperability. We present Gremlinator, a novel SPARQL to Gremlin translator. Gremlinator translates SPARQL queries to Gremlin traversals for executing graph pattern matching queries over graph databases. This allows to access and query a wide variety of Graph Data Management Systems (DMS) using the W3C standardized SPARQL query language and avoid the learning curve of a new Graph Query Language. Gremlin is a system-agnostic traversal language covering both OLTP graph database or OLAP graph processors, thus making it a desirable choice for supporting interoperability wrt. querying Graph DMSs. We present a comprehensive empirical evaluation of Gremlinator and demonstrate its validity and applicability by executing SPARQL queries on top of the leading graph stores Neo4J, Sparksee, and Apache TinkerGraph and compare the performance with the RDF stores Virtuoso, 4Store and JenaTDB. Our evaluation demonstrates the substantial performance gain obtained by the Gremlin counterparts of the SPARQL queries, especially for star-shaped and complex queries.
Multi-threaded Sparse Matrix-Matrix Multiplication for Many-Core and GPU Architectures
Venue: arXiv cs.DC 2018
Year: 2018

Sparse Matrix-Matrix multiplication is a key kernel that has applications in several domains such as scientific computing and graph analysis. Several algorithms have been studied in the past for this foundational kernel. In this paper, we develop parallel algorithms for sparse matrix-matrix multiplication with a focus on performance portability across different high performance computing architectures. The performance of these algorithms depend on the data structures used in them. We compare different types of accumulators in these algorithms and demonstrate the performance difference between these data structures. Furthermore, we develop a meta-algorithm, kkSpGEMM, to choose the right algorithm and data structure based on the characteristics of the problem. We show performance comparisons on three architectures and demonstrate the need for the community to develop two phase sparse matrix-matrix multiplication implementations for efficient reuse of the data structures involved.
Game of Drones - Detecting Streamed POI from Encrypted FPV Channel
Venue: arXiv cs.CR 2018
Year: 2018

Drones have created a new threat to people's privacy. We are now in an era in which anyone with a drone equipped with a video camera can use it to invade a subject's privacy by streaming the subject in his/her private space over an encrypted first person view (FPV) channel. Although many methods have been suggested to detect nearby drones, they all suffer from the same shortcoming: they cannot identify exactly what is being captured, and therefore they fail to distinguish between the legitimate use of a drone (for example, to use a drone to film a selfie from the air) and illegitimate use that invades someone's privacy (when the same operator uses the drone to stream the view into the window of his neighbor's apartment), a distinction that in some cases depends on the orientation of the drone's video camera rather than on the drone's location. In this paper we shatter the commonly held belief that the use of encryption to secure an FPV channel prevents an interceptor from extracting the POI that is being streamed. We show methods that leverage physical stimuli to detect whether the drone's camera is directed towards a target in real time. We investigate the influence of changing pixels on the FPV channel (in a lab setup). Based on our observations we demonstrate how an interceptor can perform a side-channel attack to detect whether a target is being streamed by analyzing the encrypted FPV channel that is transmitted from a real drone (DJI Mavic) in two use cases: when the target is a private house and when the target is a subject.
Resolving zero-divisors using Hensel lifting
Venue: arXiv cs.SC 2018
Year: 2018

Algorithms which compute modulo triangular sets must respect the presence of zero-divisors. We present Hensel lifting as a tool for dealing with them. We give an application: a modular algorithm for computing GCDs of univariate polynomials with coefficients modulo a radical triangular set over the rationals. Our modular algorithm naturally generalizes previous work from algebraic number theory. We have implemented our algorithm using Maple's RECDEN package. We compare our implementation with the procedure RegularGcd in the RegularChains package.
NP-Completeness and Inapproximability of the Virtual Network Embedding Problem and Its Variants
Venue: arXiv cs.NI 2018
Year: 2018

Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): the problem of finding a mapping of a request graph (describing a workload) onto a substrate graph (describing the physical infrastructure). Applications range from mapping testbeds (from where the problem originated), over the embedding of batch-processing workloads (virtual clusters) to the embedding of service function chains. The different applications come with their own specific requirements and constraints, including node mapping constraints, routing policies, and latency constraints. While the VNEP has been studied intensively over the last years, complexity results are only known for specific models and we lack a comprehensive understanding of its hardness. This paper charts the complexity landscape of the VNEP by providing a systematic analysis of the hardness of a wide range of VNEP variants, using a unifying and rigorous proof framework. In particular, we show that the problem of finding a feasible embedding is NP-complete in general, and, hence, the VNEP cannot be approximated under any objective, unless P=NP holds. Importantly, we derive NP-completeness results also for finding approximate embeddings, which may violate, e.g., capacity constraints by certain factors. Lastly, we prove that our results still pertain when restricting the request graphs to planar or degree-bounded graphs.
Paranom: A Parallel Anomaly Dataset Generator
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we present Paranom, a parallel anomaly dataset generator. We discuss its design and provide brief experimental results demonstrating its usefulness in improving the classification correctness of LSTM-AD, a state-of-the-art anomaly detection model.
Greenhouse: A Zero-Positive Machine Learning System for Time-Series Anomaly Detection
Venue: arXiv cs.AI 2018
Year: 2018

This short paper describes our ongoing research on Greenhouse - a zero-positive machine learning system for time-series anomaly detection.
Precision and Recall for Range-Based Anomaly Detection
Venue: arXiv cs.AI 2018
Year: 2018

Classical anomaly detection is principally concerned with point-based anomalies, anomalies that occur at a single data point. In this paper, we present a new mathematical model to express range-based anomalies, anomalies that occur over a range (or period) of time.
Asymptotically Optimal Scheduling for Compute-and-Forward
Venue: arXiv cs.IT 2018
Year: 2018

Consider a Compute and Forward (CF) relay network with $L$ users and a single relay. The relay tries to decode a linear function of the transmitted signals. For such a network, letting all $L$ users transmit simultaneously, especially when $L$ is large, causes a significant degradation in the rate in which the relay is able to decode. In fact, the rate goes to zero very fast with $L$. Therefore, in each transmission phase only a fixed number of users should transmit, i.e., users should be scheduled. In this work, we examine the problem of scheduling for CF and lay the foundations for identifying the optimal schedule which, to date, lacks a clear understanding. Specifically, we start with insights why when the number of users is large, good scheduling opportunities can be found. Then, we provide an asymptotically optimal, polynomial time scheduling algorithm and analyze it's performance. We conclude that scheduling under CF provides a gain in the system sum-rate, up to the optimal scaling law of $O(\log{\log{L}})$.
A First Look at Identity Management Schemes on the Blockchain
Venue: arXiv cs.CR 2018
Year: 2018

The emergence of distributed ledger technology (DLT) based upon a blockchain data structure, has given rise to new approaches to identity management that aim to upend dominant approaches to providing and consuming digital identities. These new approaches to identity management (IdM) propose to enhance decentralisation, transparency and user control in transactions that involve identity information; but, given the historical challenge to design IdM, can these new DLT-based schemes deliver on their lofty goals? We introduce the emerging landscape of DLT-based IdM, and evaluate three representative proposals: uPort; ShoCard; and Sovrin; using the analytic lens of a seminal framework that characterises the nature of successful IdM schemes.
Distribution of the absolute indicator of random Boolean functions
Venue: arXiv cs.IT 2018
Year: 2018

The absolute indicator is one of the measures used to determine the resistance offered by a Boolean function when used in the design of a symmetric cryptosystem. It was proposed along with the sum of square indicator to evaluate the quality of the diffusion property of block ciphers and hash functions. While the behaviour of the sum of square of random Boolean functions was already known, what remained was the study of the comportment of the absolute indicator of random Boolean functions. As an application, we show that the absolute indicator can distinguish a nonrandom binary sequence from a random one.
Quantitative Analysis of Smart Contracts
Venue: arXiv cs.PL 2018
Year: 2018

Smart contracts are computer programs that are executed by a network of mutually distrusting agents, without the need of an external trusted authority. Smart contracts handle and transfer assets of considerable value (in the form of crypto-currency like Bitcoin). Hence, it is crucial that their implementation is bug-free. We identify the utility (or expected payoff) of interacting with such smart contracts as the basic and canonical quantitative property for such contracts. We present a framework for such quantitative analysis of smart contracts. Such a formal framework poses new and novel research challenges in programming languages, as it requires modeling of game-theoretic aspects to analyze incentives for deviation from honest behavior and modeling utilities which are not specified as standard temporal properties such as safety and termination. While game-theoretic incentives have been analyzed in the security community, their analysis has been restricted to the very special case of stateless games. However, to analyze smart contracts, stateful analysis is required as it must account for the different program states of the protocol. Our main contributions are as follows: we present (i)~a simplified programming language for smart contracts; (ii)~an automatic translation of the programs to state-based games; (iii)~an abstraction-refinement approach to solve such games; and (iv)~experimental results on real-world-inspired smart contracts.
On Maximally Recoverable Codes for Product Topologies
Venue: arXiv cs.IT 2018
Year: 2018

Given a topology of local parity-check constraints, a maximally recoverable code (MRC) can correct all erasure patterns that are information-theoretically correctable. In a grid-like topology, there are $a$ local constraints in every column forming a column code, $b$ local constraints in every row forming a row code, and $h$ global constraints in an $(m \times n)$ grid of codeword. Recently, Gopalan et al. initiated the study of MRCs under grid-like topology, and derived a necessary and sufficient condition, termed as the regularity condition, for an erasure pattern to be recoverable when $a=1, h=0$. In this paper, we consider MRCs for product topology ($h=0$). First, we construct a certain bipartite graph based on the erasure pattern satisfying the regularity condition for product topology (any $a, b$, $h=0$) and show that there exists a complete matching in this graph. We then present an alternate direct proof of the sufficient condition when $a=1, h=0$. We later extend our technique to study the topology for $a=2, h=0$, and characterize a subset of recoverable erasure patterns in that case. For both $a=1, 2$, our method of proof is uniform, i.e., by constructing tensor product $G_{\text{col}} \otimes G_{\text{row}}$ of generator matrices of column and row codes such that certain square sub-matrices retain full rank. The full-rank condition is proved by resorting to the matching identified earlier and also another set of matchings in erasure sub-patterns.
Structure Entropy and Resistor Graphs
Venue: arXiv cs.DM 2018
Year: 2018

We propose the notion of {\it resistance of a graph} as an accompanying notion of the structure entropy to measure the force of the graph to resist cascading failure of strategic virus attacks. We show that for any connected network $G$, the resistance of $G$ is $\mathcal{R}(G)=\mathcal{H}^1(G)-\mathcal{H}^2(G)$, where $\mathcal{H}^1(G)$ and $\mathcal{H}^2(G)$ are the one- and two-dimensional structure entropy of $G$, respectively. According to this, we define the notion of {\it security index of a graph} to be the normalized resistance, that is, $θ(G)=\frac{\mathcal{R}(G)}{\mathcal{H}^1(H)}$. We say that a connected graph is an $(n,θ)$-{\it resistor graph}, if $G$ has $n$ vertices and has security index $θ(G)\geqθ$. We show that trees and grid graphs are $(n,θ)$-resistor graphs for large constant $θ$, that the graphs with bounded degree $d$ and $n$ vertices, are $(n,\frac{2}{d}-o(1))$-resistor graphs, and that for a graph $G$ generated by the security model \cite{LLPZ2015, LP2016}, with high probability, $G$ is an $(n,θ)$-resistor graph, for a constant $θ$ arbitrarily close to $1$, provided that $n$ is sufficiently large. To the opposite side, we show that expander graphs are not good resistor graphs, in the sense that, there is a global constant $θ_0<1$ such that expander graphs cannot be $(n,θ)$-resistor graph for any $θ\geqθ_0$. In particular, for the complete graph $G$, the resistance of $G$ is a constant $O(1)$, and hence the security index of $G$ is $θ(G)=o(1)$. Finally, we show that for any simple and connected graph $G$, if $G$ is an $(n, 1-o(1))$-resistor graph, then there is a large $k$ such that the $k$-th largest eigenvalue of the Laplacian of $G$ is $o(1)$, giving rise to an algebraic characterization for the graphs that are secure against intentional virus attack.
Numerical Analysis of Automodel Solutions for Superdiffusive Transport
Venue: arXiv cs.NA 2018
Year: 2018

The distributed computing analysis of the accuracy of automodel solutions for the Green's function of a wide class of superdiffusive transport of perturbation on a uniform background is carried out. The approximate automodel solutions have been suggested for the 1D transport equation with a model long-tailed step-length probability distribution function (PDF) with various power-law exponents. These PDFs describe the transport dominated by the Lévy flights. Massive computing experiments were done to verify automodel solutions. The Everest distributed computing platform and the cluster at NRC Kurchatov Institute were used. The results verify the high accuracy of automodel solutions in a wide range of space-time variables and suggest extending the developed method of automodel solutions to a wider class of stochastic phenomena.
Focus: Querying Large Video Datasets with Low Latency and Low Cost
Venue: arXiv cs.DB 2018
Year: 2018

Large volumes of videos are continuously recorded from cameras deployed for traffic control and surveillance with the goal of answering "after the fact" queries: identify video frames with objects of certain classes (cars, bags) from many days of recorded video. While advancements in convolutional neural networks (CNNs) have enabled answering such queries with high accuracy, they are too expensive and slow. We build Focus, a system for low-latency and low-cost querying on large video datasets. Focus uses cheap ingestion techniques to index the videos by the objects occurring in them. At ingest-time, it uses compression and video-specific specialization of CNNs. Focus handles the lower accuracy of the cheap CNNs by judiciously leveraging expensive CNNs at query-time. To reduce query time latency, we cluster similar objects and hence avoid redundant processing. Using experiments on video streams from traffic, surveillance and news channels, we see that Focus uses 58X fewer GPU cycles than running expensive ingest processors and is 37X faster than processing all the video at query time.
Multi-Scale Attention with Dense Encoder for Handwritten Mathematical Expression Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Handwritten mathematical expression recognition is a challenging problem due to the complicated two-dimensional structures, ambiguous handwriting input and variant scales of handwritten math symbols. To settle this problem, we utilize the attention based encoder-decoder model that recognizes mathematical expression images from two-dimensional layouts to one-dimensional LaTeX strings. We improve the encoder by employing densely connected convolutional networks as they can strengthen feature extraction and facilitate gradient propagation especially on a small training set. We also present a novel multi-scale attention model which is employed to deal with the recognition of math symbols in different scales and save the fine-grained details that will be dropped by pooling operations. Validated on the CROHME competition task, the proposed method significantly outperforms the state-of-the-art methods with an expression recognition accuracy of 52.8% on CROHME 2014 and 50.1% on CROHME 2016, by only using the official training dataset.
An evolutionary algorithm for online, resource constrained, multi-vehicle sensing mission planning
Venue: arXiv cs.RO 2018
Year: 2018

Mobile robotic platforms are an indispensable tool for various scientific and industrial applications. Robots are used to undertake missions whose execution is constrained by various factors, such as the allocated time or their remaining energy. Existing solutions for resource constrained multi-robot sensing mission planning provide optimal plans at a prohibitive computational complexity for online application [1],[2],[3]. A heuristic approach exists for an online, resource constrained sensing mission planning for a single vehicle [4]. This work proposes a Genetic Algorithm (GA) based heuristic for the Correlated Team Orienteering Problem (CTOP) that is used for planning sensing and monitoring missions for robotic teams that operate under resource constraints. The heuristic is compared against optimal Mixed Integer Quadratic Programming (MIQP) solutions. Results show that the quality of the heuristic solution is at the worst case equal to the 5% optimal solution. The heuristic solution proves to be at least 300 times more time efficient in the worst tested case. The GA heuristic execution required in the worst case less than a second making it suitable for online execution.
Group Communication Analysis: A Computational Linguistics Approach for Detecting Sociocognitive Roles in Multi-Party Interactions
Venue: arXiv cs.CL 2018
Year: 2018

Roles are one of the most important concepts in understanding human sociocognitive behavior. During group interactions, members take on different roles within the discussion. Roles have distinct patterns of behavioral engagement (i.e., active or passive, leading or following), contribution characteristics (i.e., providing new information or echoing given material), and social orientation (i.e., individual or group). Different combinations of these roles can produce characteristically different group outcomes, being either less or more productive towards collective goals. In online collaborative learning environments, this can lead to better or worse learning outcomes for the individual participants. In this study, we propose and validate a novel approach for detecting emergent roles from the participants' contributions and patterns of interaction. Specifically, we developed a group communication analysis (GCA) by combining automated computational linguistic techniques with analyses of the sequential interactions of online group communication. The GCA was applied to three large collaborative interaction datasets (participant N = 2,429; group N = 3,598). Cluster analyses and linear mixed-effects modeling were used to assess the validity of the GCA approach and the influence of learner roles on student and group performance. The results indicate that participants' patterns in linguistic coordination and cohesion are representative of the roles that individuals play in collaborative discussions. More broadly, GCA provides a framework for researchers to explore the micro intra- and interpersonal patterns associated with the participants' roles and the sociocognitive processes related to successful collaboration.
Task parallel implementation of a solver for electromagnetic scattering problems
Venue: arXiv cs.CE 2018
Year: 2018

Electromagnetic computations, where the wavelength is small in relation to the geometry of interest, become computationally demanding. In order to manage computations for realistic problems like electromagnetic scattering from aircraft, the use of parallel computing is essential. In this paper, we describe how a solver based on a hierarchical nested equivalent source approximation can be implemented in parallel using a task based programming model. We show that the effort for moving from the serial implementation to a parallel implementation is modest due to the task based programming paradigm, and that the performance achieved on a multicore system is excellent provided that the task size, depending on the method parameters, is large enough.
Conversational AI: The Science Behind the Alexa Prize
Venue: arXiv cs.AI 2018
Year: 2018

Conversational agents are exploding in popularity. However, much work remains in the area of social conversation as well as free-form conversation over a broad range of domains and topics. To advance the state of the art in conversational AI, Amazon launched the Alexa Prize, a 2.5-million-dollar university competition where sixteen selected university teams were challenged to build conversational agents, known as socialbots, to converse coherently and engagingly with humans on popular topics such as Sports, Politics, Entertainment, Fashion and Technology for 20 minutes. The Alexa Prize offers the academic community a unique opportunity to perform research with a live system used by millions of users. The competition provided university teams with real user conversational data at scale, along with the user-provided ratings and feedback augmented with annotations by the Alexa team. This enabled teams to effectively iterate and make improvements throughout the competition while being evaluated in real-time through live user interactions. To build their socialbots, university teams combined state-of-the-art techniques with novel strategies in the areas of Natural Language Understanding, Context Modeling, Dialog Management, Response Generation, and Knowledge Acquisition. To support the efforts of participating teams, the Alexa Prize team made significant scientific and engineering investments to build and improve Conversational Speech Recognition, Topic Tracking, Dialog Evaluation, Voice User Experience, and tools for traffic management and scalability. This paper outlines the advances created by the university teams as well as the Alexa Prize team to achieve the common goal of solving the problem of Conversational AI.