OpenRaiser/Intern-Atlas huggingface dataset:
LITMUS: An Open Extensible Framework for Benchmarking RDF Data Management Solutions
Venue: arXiv cs.PF 2016
Year: 2016

Developments in the context of Open, Big, and Linked Data have led to an enormous growth of structured data on the Web. To keep up with the pace of efficient consumption and management of the data at this rate, many data Management solutions have been developed for specific tasks and applications. We present LITMUS, a framework for benchmarking data management solutions. LITMUS goes beyond classical storage benchmarking frameworks by allowing for analysing the performance of frameworks across query languages. In this position paper we present the conceptual architecture of LITMUS as well as the considerations that led to this architecture.
Semi-Automated SVG Programming via Direct Manipulation
Venue: arXiv cs.HC 2016
Year: 2016

Direct manipulation interfaces provide intuitive and interactive features to a broad range of users, but they often exhibit two limitations: the built-in features cannot possibly cover all use cases, and the internal representation of the content is not readily exposed. We believe that if direct manipulation interfaces were to (a) use general-purpose programs as the representation format, and (b) expose those programs to the user, then experts could customize these systems in powerful new ways and non-experts could enjoy some of the benefits of programmable systems. In recent work, we presented a prototype SVG editor called Sketch-n-Sketch that offered a step towards this vision. In that system, the user wrote a program in a general-purpose lambda-calculus to generate a graphic design and could then directly manipulate the output to indirectly change design parameters (i.e. constant literals) in the program in real-time during the manipulation. Unfortunately, the burden of programming the desired relationships rested entirely on the user. In this paper, we design and implement new features for Sketch-n-Sketch that assist in the programming process itself. Like typical direct manipulation systems, our extended Sketch-n-Sketch now provides GUI-based tools for drawing shapes, relating shapes to each other, and grouping shapes together. Unlike typical systems, however, each tool carries out the user's intention by transforming their general-purpose program. This novel, semi-automated programming workflow allows the user to rapidly create high-level, reusable abstractions in the program while at the same time retaining direct manipulation capabilities. In future work, our approach may be extended with more graphic design features or realized for other application domains.
Liftago On-Demand Transport Dataset and Market Formation Algorithm Based on Machine Learning
Venue: arXiv cs.AI 2016
Year: 2016

This document serves as a technical report for the analysis of on-demand transport dataset. Moreover we show how the dataset can be used to develop a market formation algorithm based on machine learning. Data used in this work comes from Liftago, a Prague based company which connects taxi drivers and customers through a smartphone app. The dataset is analysed from the machine-learning perspective: we give an overview of features available as well as results of feature ranking. Later we propose the SImple Data-driven MArket Formation (SIDMAF) algorithm which aims to improve a relevance while connecting customers with relevant drivers. We compare the heuristics currently used by Liftago with SIDMAF using two key performance indicators.
Syntactically Informed Text Compression with Recurrent Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

We present a self-contained system for constructing natural language models for use in text compression. Our system improves upon previous neural network based models by utilizing recent advances in syntactic parsing -- Google's SyntaxNet -- to augment character-level recurrent neural networks. RNNs have proven exceptional in modeling sequence data such as text, as their architecture allows for modeling of long-term contextual information.
Escaping Local Optima using Crossover with Emergent or Reinforced Diversity
Venue: arXiv cs.NE 2016
Year: 2016

Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for the ($μ$+1) GA and the $\text{Jump}_k$ test function. We show that the interplay of crossover and mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order $Ω(n/\log n)$ compared to mutation-only algorithms like (1+1) EA. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to speedups of order $Ω(n)$. We also compare seven commonly used diversity mechanisms and evaluate their impact on runtime bounds for the ($μ$+1) GA. All previous results in this context only hold for unrealistically low crossover probability $p_c=O(k/n)$, while we give analyses for the setting of constant $p_c < 1$ in all but one case. For the typical case of constant $k > 2$ and constant $p_c$, we can compare the resulting expected runtimes for different diversity mechanisms assuming an optimal choice of $μ$: $O(n^{k-1})$ for duplicate elimination/minim., $O(n^2\log n)$ for maximising the convex hull, $O(n\log n)$ for deterministic crowding (assuming $p_c = k/n$), $O(n\log n)$ for maximising Hamming distance, $O(n\log n)$ for fitness sharing, $O(n\log n)$ for single-receiver island model. This proves a sizeable advantage of all variants of the ($μ$+1) GA compared to (1+1) EA, which requires time $Θ(n^k)$. Experiments complement our theoretical findings and further highlight the benefits of crossover and diversity on $\text{Jump}_k$.
A Note on the Expressiveness of BIP
Venue: arXiv cs.DC 2016
Year: 2016

We extend our previous algebraic formalisation of the notion of component-based framework in order to formally define two forms, strong and weak, of the notion of full expressiveness. Our earlier result shows that the BIP (Behaviour-Interaction-Priority) framework does not possess the strong full expressiveness. In this paper, we show that BIP has the weak form of this notion and provide results detailing weak and strong full expressiveness for classical BIP and several modifications, obtained by relaxing the constraints imposed on priority models.
A Mid-level Planning System for Object Reorientation
Venue: arXiv cs.RO 2016
Year: 2016

This paper presents a mid-level planning system for object reorientation. It includes a grasp planner, a placement planner, and a regrasp sequence solver. Given the initial and goal poses of an object, the mid-level planning system finds a sequence of hand configurations that reorient the object from the initial to the goal. This mid-level planning system is open to low-level motion planning algorithm by providing two end-effector poses as the input. It is also open to high-level symbolic planners by providing interface functions like placing an object to a given position at a given rotation. The planning system is demonstrated with several simulation examples and real-robot executions using a Kawada Hiro robot and Robotiq 85 grippers.
Energy-Efficient Small Cell with Spectrum-Power Trading
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate spectrum-power trading between a small cell (SC) and a macro cell (MC), where the SC consumes power to serve the macro cell users (MUs) in exchange for some bandwidth from the MC. Our goal is to maximize the system energy efficiency (EE) of the SC while guaranteeing the quality of service of each MU as well as small cell users (SUs). Specifically, given the minimum data rate requirement and the bandwidth provided by the MC, the SC jointly optimizes MU selection, bandwidth allocation, and power allocation while guaranteeing its own minimum required system data rate. The problem is challenging due to the binary MU selection variables and the fractional- form objective function. We first show that the bandwidth of an MU is shared with at most one SU in the SC. Then, for a given MU selection, the optimal bandwidth and power allocation is obtained by exploiting the fractional programming. To perform MU selection, we first introduce the concept of the trading EE to characterize the data rate obtained as well as the power consumed for serving an MU. We then reveal a sufficient and necessary condition for serving an MU without considering the total power constraint and the minimum data rate constraint: the trading EE of the MU should be higher than the system EE of the SC. Based on this insight, we propose a low complexity MU selection method and also investigate the optimality condition. Simulation results verify our theoretical findings and demonstrate that the proposed resource allocation achieves near-optimal performance.
Instagram photos reveal predictive markers of depression
Venue: arXiv cs.SI 2016
Year: 2016

Using Instagram data from 166 individuals, we applied machine learning tools to successfully identify markers of depression. Statistical features were computationally extracted from 43,950 participant Instagram photos, using color analysis, metadata components, and algorithmic face detection. Resulting models outperformed general practitioners' average diagnostic success rate for depression. These results held even when the analysis was restricted to posts made before depressed individuals were first diagnosed. Photos posted by depressed individuals were more likely to be bluer, grayer, and darker. Human ratings of photo attributes (happy, sad, etc.) were weaker predictors of depression, and were uncorrelated with computationally-generated features. These findings suggest new avenues for early screening and detection of mental illness.
Tight Network Topology Dependent Bounds on Rounds of Communication
Venue: arXiv cs.CC 2016
Year: 2016

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent such results on total communication that have received some attention. We also present some applications to distributed graph computation problems. Our main contribution is a proof technique that allows us to reduce the problem on a general graph topology to a relevant two-party communication complexity problem. However, unlike many previous works that also used the same high level strategy, we do not reason about a two-party communication problem that is induced by a cut in the graph. To `stitch' back the various lower bounds from the two party communication problems, we use the notion of timed graph that has seen prior use in network coding. Our reductions use some tools from Steiner tree packing and multi-commodity flow problems that have a delay constraint.
An Erlang Implementation of Multiparty Session Actors
Venue: arXiv cs.PL 2016
Year: 2016

By requiring co-ordination to take place using explicit message passing instead of relying on shared memory, actor-based programming languages have been shown to be effective tools for building reliable and fault-tolerant distributed systems. Although naturally communication-centric, communication patterns in actor-based applications remain informally specified, meaning that errors in communication are detected late, if at all. Multiparty session types are a formalism to describe, at a global level, the interactions between multiple communicating entities. This article describes the implementation of a prototype framework for monitoring Erlang/OTP gen_server applications against multiparty session types, showing how previous work on multiparty session actors can be adapted to a purely actor-based language, and how monitor violations and termination of session participants can be reported in line with the Erlang mantra of "let it fail". Finally, the framework is used to implement two case studies: an adaptation of a freely-available DNS server, and a chat server.
Enabling My Robot To Play Pictionary : Recurrent Neural Networks For Sketch Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Freehand sketching is an inherently sequential process. Yet, most approaches for hand-drawn sketch recognition either ignore this sequential aspect or exploit it in an ad-hoc manner. In our work, we propose a recurrent neural network architecture for sketch object recognition which exploits the long-term sequential and structural regularities in stroke data in a scalable manner. Specifically, we introduce a Gated Recurrent Unit based framework which leverages deep sketch features and weighted per-timestep loss to achieve state-of-the-art results on a large database of freehand object sketches across a large number of object categories. The inherently online nature of our framework is especially suited for on-the-fly recognition of objects as they are being drawn. Thus, our framework can enable interesting applications such as camera-equipped robots playing the popular party game Pictionary with human players and generating sparsified yet recognizable sketches of objects.
Distributed Association and Relaying with Fairness in Millimeter Wave Networks
Venue: arXiv cs.NI 2016
Year: 2016

Millimeter wave (mmWave) systems are emerging as an essential technology to enable extremely high data rate wireless communications. The main limiting factors of mmWave systems are blockage (high penetration loss) and deafness (misalignment between the beams of the transmitter and receiver). To alleviate these problems, it is imperative to incorporate efficient association and relaying between terminals and access points. Unfortunately, the existing association techniques are designed for the traditional interference-limited networks, and thus are highly suboptimal for mmWave communications due to narrow-beam operations and the resulting non-negligible interference-free behavior. This paper introduces a distributed approach that solves the joint association and relaying problem in mmWave networks considering the load balancing at access points. The problem is posed as a novel stochastic optimization problem, which is solved by distributed auction algorithms where the clients and relays act asynchronously to achieve optimal client-relay-access point association. It is shown that the algorithms provably converge to a solution that maximizes the aggregate logarithmic utility within a desired bound. Numerical results allow to quantify the performance enhancements introduced by the relays, and the substantial improvements of the network throughput and fairness among the clients by the proposed association method as compared to standard approaches. It is concluded that mmWave communications with proper association and relaying mechanisms can support extremely high data rates, connection reliability, and fairness among the clients.
Dynamic routing for social information sharing
Venue: arXiv cs.GT 2016
Year: 2016

Today mobile users are intensively interconnected thanks to the emerging mobile social networks, where they share location-based information with each other when traveling on different routes and visit different areas of the city. In our model the information collected is aggregated over all users' trips and made publicly available as a public good. Due to information overlap, the total useful content amount increases with the diversity in path choices made by the users, and it is crucial to motivate selfish users to choose different paths despite the potentially higher costs associated with their trips. In this paper we combine the benefits from social information sharing with the fundamental routing problem where a unit mass of non-atomic selfish users decide their trips in a non-cooperative game by choosing between a high-cost and a low-cost path. To remedy the inefficient low-content equilibrium where all users choose to explore a single path (the low-cost path), we propose and analyse two new incentive mechanisms that can be used by the social network application, one based on side payments and the other on restricting access to content for users that choose the low cost path. We also obtain interesting price of anarchy results that show some fundamental tradeoffs between achieving path diversity and maintaining greater user participation, motivating a combined mechanism to further increase the social welfare. Our model extends classical dynamic routing in the case of externalities caused from traffic on different paths of the network.
DiskFiltration: Data Exfiltration from Speakerless Air-Gapped Computers via Covert Hard Drive Noise
Venue: arXiv cs.CR 2016
Year: 2016

Air-gapped computers are disconnected from the Internet physically and logically. This measure is taken in order to prevent the leakage of sensitive data from secured networks. In the past, it has been shown that malware can exfiltrate data from air-gapped computers by transmitting ultrasonic signals via the computer's speakers. However, such acoustic communication relies on the availability of speakers on a computer. In this paper, we present 'DiskFiltration,' a covert channel which facilitates the leakage of data from an air-gapped compute via acoustic signals emitted from its hard disk drive (HDD). Our method is unique in that, unlike other acoustic covert channels, it doesn't require the presence of speakers or audio hardware in the air-gapped computer. A malware installed on a compromised machine can generate acoustic emissions at specific audio frequencies by controlling the movements of the HDD's actuator arm. Digital Information can be modulated over the acoustic signals and then be picked up by a nearby receiver (e.g., smartphone, smartwatch, laptop, etc.). We examine the HDD anatomy and analyze its acoustical characteristics. We also present signal generation and detection, and data modulation and demodulation algorithms. Based on our proposed method, we developed a transmitter on a personal computer and a receiver on a smartphone, and we provide the design and implementation details. We also evaluate our covert channel on various types of internal and external HDDs in different computer chassis and at various distances. With DiskFiltration we were able to covertly transmit data (e.g., passwords, encryption keys, and keylogging data) between air-gapped computers to a smartphone at an effective bit rate of 180 bits/minute (10,800 bits/hour) and a distance of up to two meters (six feet).
QPass: a Merit-based Evaluation of Soccer Passes
Venue: arXiv cs.AI 2016
Year: 2016

Quantitative analysis of soccer players' passing ability focuses on descriptive statistics without considering the players' real contribution to the passing and ball possession strategy of their team. Which player is able to help the build-up of an attack, or to maintain the possession of the ball? We introduce a novel methodology called QPass to answer questions like these quantitatively. Based on the analysis of an entire season, we rank the players based on the intrinsic value of their passes using QPass. We derive an album of pass trajectories for different gaming styles. Our methodology reveals a quite counterintuitive paradigm: losing the ball possession could lead to better chances to win a game.
The statistical trade-off between word order and word structure - large-scale evidence for the principle of least effort
Venue: arXiv cs.CL 2016
Year: 2016

Languages employ different strategies to transmit structural and grammatical information. While, for example, grammatical dependency relationships in sentences are mainly conveyed by the ordering of the words for languages like Mandarin Chinese, or Vietnamese, the word ordering is much less restricted for languages such as Inupiatun or Quechua, as those languages (also) use the internal structure of words (e.g. inflectional morphology) to mark grammatical relationships in a sentence. Based on a quantitative analysis of more than 1,500 unique translations of different books of the Bible in more than 1,100 different languages that are spoken as a native language by approximately 6 billion people (more than 80% of the world population), we present large-scale evidence for a statistical trade-off between the amount of information conveyed by the ordering of words and the amount of information conveyed by internal word structure: languages that rely more strongly on word order information tend to rely less on word structure information and vice versa. In addition, we find that - despite differences in the way information is expressed - there is also evidence for a trade-off between different books of the biblical canon that recurs with little variation across languages: the more informative the word order of the book, the less informative its word structure and vice versa. We argue that this might suggest that, on the one hand, languages encode information in very different (but efficient) ways. On the other hand, content-related and stylistic features are statistically encoded in very similar ways.
Downlink Performance of Pilot-Reused HetNet with Large-Scale Antenna Arrays
Venue: arXiv cs.IT 2016
Year: 2016

Considering a heterogeneous network (HetNet) where both macro base station (BS) and small cell (SC) nodes are equipped with massive antennas, this paper studies the performance for multiple-input multiple-output (MIMO) downlinks when the macro and small cells share the same spectrum and hence interfere with each other. Suppose that the large-scale antenna arrays at both macro BS and SC nodes employ maximum-ratio transmission (MRT) or zero-forcing transmission (ZFT) precoding, and transmit data streams to the served users simultaneously. A new pilot reuse pattern among SCs is proposed for channel estimation. Taking into account imperfect channel state information (CSI), capacity lower bounds for MRT and ZFT are derived, respectively, in closed-form expressions involving only statistical CSI. Then asymptotic analyses for massive arrays are presented under specific power scaling laws. Subsequently, two user scheduling algorithms, greedy scheduling algorithm and asymptotical scheduling algorithm (ASA), are proposed based on derived capacity lower bounds and asymptotic analyses, respectively. ASA is demonstrated to be a near optimal in the asymptotic regime and has low complexity. Finally, the derived closed-form expressions are verified to be accurate predictors of the system performance by Monte-Carlo simulations. Numerical results demonstrate the effectiveness of asymptotic analysis and proposed user scheduling schemes.