OpenRaiser/Intern-Atlas huggingface dataset:
A Game-theoretic Perspective on Communication for Omniscience
Venue: arXiv cs.IT 2015
Year: 2015

We propose a coalition game model for the problem of communication for omniscience (CO). In this game model, the core contains all achievable rate vectors for CO with sum-rate being equal to a given value. Any rate vector in the core distributes the sum-rate among users in a way that makes all users willing to cooperate in CO. We give the necessary and sufficient condition for the core to be nonempty. Based on this condition, we derive the expression of the minimum sum-rate for CO and show that this expression is consistent with the results in multivariate mutual information (MMI) and coded cooperative data exchange (CCDE). We prove that the coalition game model is convex if the sum-rate is no less than the minimal value. In this case, the core is non-empty and a rate vector in the core that allocates the sum-rate among the users in a fair manner can be found by calculating the Shapley value.
Towards More Security in Data Exchange: Defining Unparsers with Context-Sensitive Encoders for Context-Free Grammars
Venue: arXiv cs.SE 2015
Year: 2015

To exchange complex data structures in distributed systems, documents written in context-free languages are exchanged among communicating parties. Unparsing these documents correctly is as important as parsing them correctly because errors during unparsing result in injection vulnerabilities such as cross-site scripting (XSS) and SQL injection. Injection attacks are not limited to the web world. Every program that uses input to produce documents in a context-free language may be vulnerable to this class of attack. Even for widely used languages such as HTML and JavaScript, there are few approaches that prevent injection attacks by context-sensitive encoding, and those approaches are tied to the language. Therefore, the aim of this paper is to derive context-sensitive encoder from context-free grammars to provide correct unparsing of maliciously crafted input data for all context-free languages. The presented solution integrates encoder definition into context-free grammars and provides a generator for context-sensitive encoders and decoders that are used during (un)parsing. This unparsing process results in documents where the input data does neither influence the structure of the document nor change their intended semantics. By defining encoding during language definition, developers who use the language are provided with a clean interface for writing and reading documents written in that language, without the need to care about security-relevant encoding.
Extending DIRAC File Management with Erasure-Coding for efficient storage
Venue: arXiv cs.DC 2015
Year: 2015

The state of the art in Grid style data management is to achieve increased resilience of data via multiple complete replicas of data files across multiple storage endpoints. While this is effective, it is not the most space-efficient approach to resilience, especially when the reliability of individual storage endpoints is sufficiently high that only a few will be inactive at any point in time. We report on work performed as part of GridPP\cite{GridPP}, extending the Dirac File Catalogue and file management interface to allow the placement of erasure-coded files: each file distributed as N identically-sized chunks of data striped across a vector of storage endpoints, encoded such that any M chunks can be lost and the original file can be reconstructed. The tools developed are transparent to the user, and, as well as allowing up and downloading of data to Grid storage, also provide the possibility of parallelising access across all of the distributed chunks at once, improving data transfer and IO performance. We expect this approach to be of most interest to smaller VOs, who have tighter bounds on the storage available to them, but larger (WLCG) VOs may be interested as their total data increases during Run 2. We provide an analysis of the costs and benefits of the approach, along with future development and implementation plans in this area. In general, overheads for multiple file transfers provide the largest issue for competitiveness of this approach at present.
The Constant Inapproximability of the Parameterized Dominating Set Problem
Venue: arXiv cs.CC 2015
Year: 2015

We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT= W[1]. Our hardness reduction is built on the second author's recent W[1]-hardness proof of the biclique problem. This yields, among other things, a proof without the PCP machinery that the classical dominating set problem has no polynomial time constant approximation under the exponential time hypothesis.
Incentive Stackelberg Mean-payoff Games
Venue: arXiv cs.GT 2015
Year: 2015

We introduce and study incentive equilibria for multi-player meanpayoff games. Incentive equilibria generalise well-studied solution concepts such as Nash equilibria and leader equilibria (also known as Stackelberg equilibria). Recall that a strategy profile is a Nash equilibrium if no player can improve his payoff by changing his strategy unilaterally. In the setting of incentive and leader equilibria, there is a distinguished player called the leader who can assign strategies to all other players, referred to as her followers. A strategy profile is a leader strategy profile if no player, except for the leader, can improve his payoff by changing his strategy unilaterally, and a leader equilibrium is a leader strategy profile with a maximal return for the leader. In the proposed case of incentive equilibria, the leader can additionally influence the behaviour of her followers by transferring parts of her payoff to her followers. The ability to incentivise her followers provides the leader with more freedom in selecting strategy profiles, and we show that this can indeed improve the payoff for the leader in such games. The key fundamental result of the paper is the existence of incentive equilibria in mean-payoff games. We further show that the decision problem related to constructing incentive equilibria is NP-complete. On a positive note, we show that, when the number of players is fixed, the complexity of the problem falls in the same class as two-player mean-payoff games. We also present an implementation of the proposed algorithms, and discuss experimental results that demonstrate the feasibility of the analysis of medium sized games.
Invisible pushdown languages
Venue: arXiv cs.FL 2015
Year: 2015

Context free languages allow one to express data with hierarchical structure, at the cost of losing some of the useful properties of languages recognized by finite automata on words. However, it is possible to restore some of these properties by making the structure of the tree visible, such as is done by visibly pushdown languages, or finite automata on trees. In this paper, we show that the structure given by such approaches remains invisible when it is read by a finite automaton (on word). In particular, we show that separability with a regular language is undecidable for visibly pushdown languages, just as it is undecidable for general context free languages.
Privacy Preserving Driving Style Recognition
Venue: arXiv cs.CR 2015
Year: 2015

In order to better manage the premiums and encourage safe driving, many commercial insurance companies (e.g., Geico, Progressive) are providing options for their customers to install sensors on their vehicles which collect individual vehicle's traveling data. The driver's insurance is linked to his/her driving behavior. At the other end, through analyzing the historical traveling data from a large number of vehicles, the insurance company could build a classifier to predict a new driver's driving style: aggressive or defensive. However, collection of such vehicle traveling data explicitly breaches the drivers' personal privacy. To tackle such privacy concerns, this paper presents a privacy-preserving driving style recognition technique to securely predict aggressive and defensive drivers for the insurance company without compromising the privacy of all the participating parties. The insurance company cannot learn any private information from the vehicles, and vice-versa. Finally, the effectiveness and efficiency of the privacy-preserving driving style recognition technique are validated with experimental results.
ZenLDA: An Efficient and Scalable Topic Model Training System on Distributed Data-Parallel Platform
Venue: arXiv cs.DC 2015
Year: 2015

This paper presents our recent efforts, zenLDA, an efficient and scalable Collapsed Gibbs Sampling system for Latent Dirichlet Allocation training, which is thought to be challenging that both data parallelism and model parallelism are required because of the Big sampling data with up to billions of documents and Big model size with up to trillions of parameters. zenLDA combines both algorithm level improvements and system level optimizations. It first presents a novel CGS algorithm that balances the time complexity, model accuracy and parallelization flexibility. The input corpus in zenLDA is represented as a directed graph and model parameters are annotated as the corresponding vertex attributes. The distributed training is parallelized by partitioning the graph that in each iteration it first applies CGS step for all partitions in parallel, followed by synchronizing the computed model each other. In this way, both data parallelism and model parallelism are achieved by converting them to graph parallelism. We revisited the tradeoff between system efficiency and model accuracy and presented approximations such as unsynchronized model, sparse model initialization and "converged" token exclusion. zenLDA is built on GraphX in Spark that provides distributed data abstraction (RDD) and expressive APIs to simplify the programming efforts and simultaneously hides the system complexities. This enables us to implement other CGS algorithm with a few lines of code change. To better fit in distributed data-parallel framework and achieve comparable performance with contemporary systems, we also presented several system level optimizations to push the performance limit. zenLDA was evaluated it against web-scale corpus, and the result indicates that zenLDA can achieve about much better performance than other CGS algorithm we implemented, and simultaneously achieve better model accuracy.
Autonomous smartphone apps: self-compilation, mutation, and viral spreading
Venue: arXiv cs.CY 2015
Year: 2015

We present the first smart phone tool that is capable of self-compilation, mutation and viral spreading. Our autonomous app does not require a host computer to alter its functionality, change its appearance and lacks the normal necessity of a central app store to spread among hosts. We pioneered survival skills for mobile software in order to overcome disrupted Internet access due to natural disasters and human made interference, like Internet kill switches or censored networks. Internet kill switches have proven to be an effective tool to eradicate open Internet access and all forms of digital communication within an hour on a country-wide basis. We present the first operational tool that is capable of surviving such digital eradication.
Optimal Vector Linear Index Codes for Some Symmetric Side Information Problems
Venue: arXiv cs.IT 2015
Year: 2015

This paper deals with vector linear index codes for multiple unicast index coding problems where there is a source with K messages and there are K receivers each wanting a unique message and having symmetric (with respect to the receiver index) two-sided antidotes (side information). Optimal scalar linear index codes for several such instances of this class of problems for one-sided antidotes(not necessarily adjacent) have already been reported. These codes can be viewed as special cases of the symmetric unicast index coding problems discussed by Maleki, Cadambe and Jafar with one sided adjacent antidotes. In this paper, starting from a given multiple unicast index coding problem with with K messages and one-sided adjacent antidotes for which a scalar linear index code $\mathfrak{C}$ is known, we give a construction procedure which constructs a sequence (indexed by m) of multiple unicast index problems with two-sided adjacent antidotes (for the same source) for all of which a vector linear code $\mathfrak{C}^{(m)}$ is obtained from $\mathfrak{C}.$ Also, it is shown that if $\mathfrak{C}$ is optimal then $\mathfrak{C}^{(m)}$ is also optimal for all $m.$ We illustrate our construction for some of the known optimal scalar linear codes.
Distance Spectrum of Fixed-Rate Raptor Codes with Linear Random Precoders
Venue: arXiv cs.IT 2015
Year: 2015

Raptor code ensembles with linear random outer codes in a fixed-rate setting are considered. An expression for the average distance spectrum is derived and this expression is used to obtain the asymptotic exponent of the weight distribution. The asymptotic growth rate analysis is then exploited to develop a necessary and sufficient condition under which the fixed-rate Raptor code ensemble exhibits a strictly positive typical minimum distance. The condition involves the rate of the outer code, the rate of the inner fixed-rate Luby Transform (LT) code and the LT code degree distribution. Additionally, it is shown that for ensembles fulfilling this condition, the minimum distance of a code randomly drawn from the ensemble has a linear growth with the block length. The analytical results can be used to make accurate predictions of the performance of finite length Raptor codes. These results are particularly useful for fixed-rate Raptor codes under maximum likelihood erasure decoding, whose performance is driven by their weight distribution.
Network Security Threats and Protection Models
Venue: arXiv cs.CR 2015
Year: 2015

In a brave new age of global connectivity and e-commerce, interconnections via networks have heightened, creating for both individuals and organizations, a state of complete dependence upon vulnerable systems for storage and transfer of information. Never before, have so many people had power in their own hands. The power to deface websites, access personal mail accounts, and worse more the potential to bring down entire governments, and financial corporations through openly documented software codes. This paper discusses the possible exploits on typical network components, it will cite real life scenarios, and propose practical measures that can be taken as safeguard. Then, it describes some of the key efforts done by the research community to prevent such attacks, mainly by using Firewall and Intrusion Detection Systems.
Proactive Demand Response for Data Centers: A Win-Win Solution
Venue: arXiv cs.SY 2015
Year: 2015

In order to reduce the energy cost of data centers, recent studies suggest distributing computation workload among multiple geographically dispersed data centers, by exploiting the electricity price difference. However, the impact of data center load redistribution on the power grid is not well understood yet. This paper takes the first step towards tackling this important issue, by studying how the power grid can take advantage of the data centers' load distribution proactively for the purpose of power load balancing. We model the interactions between power grid and data centers as a two-stage problem, where the utility company chooses proper pricing mechanisms to balance the electric power load in the first stage, and the data centers seek to minimize their total energy cost by responding to the prices in the second stage. We show that the two-stage problem is a bilevel quadratic program, which is NP-hard and cannot be solved using standard convex optimization techniques. We introduce benchmark problems to derive upper and lower bounds for the solution of the two-stage problem. We further propose a branch and bound algorithm to attain the globally optimal solution, and propose a heuristic algorithm with low computational complexity to obtain an alternative close-to-optimal solution. We also study the impact of background load prediction error using the theoretical framework of robust optimization. The simulation results demonstrate that our proposed scheme can not only improve the power grid reliability but also reduce the energy cost of data centers.
Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games
Venue: arXiv cs.GT 2015
Year: 2015

We study the randomized query complexity of approximate Nash equilibria (ANE) in large games. We prove that, for some constant $ε>0$, any randomized oracle algorithm that computes an $ε$-ANE in a binary-action, $n$-player game must make $2^{Ω(n/\log n)}$ payoff queries. For the stronger solution concept of well-supported Nash equilibria (WSNE), Babichenko previously gave an exponential $2^{Ω(n)}$ lower bound for the randomized query complexity of $ε$-WSNE, for some constant $ε>0$; the same lower bound was shown to hold for $ε$-ANE, but only when $ε=O(1/n)$. Our result answers an open problem posed by Hart and Nisan and Babichenko and is very close to the trivial upper bound of $2^n$. Our proof relies on a generic reduction from the problem of finding an $ε$-WSNE to the problem of finding an $ε/(4α)$-ANE, in large games with $α$ actions, which might be of independent interest.
The (3,1)-ordering for 4-connected planar triangulations
Venue: arXiv cs.CG 2015
Year: 2015

Canonical orderings of planar graphs have frequently been used in graph drawing and other graph algorithms. In this paper we introduce the notion of an $(r,s)$-canonical order, which unifies many of the existing variants of canonical orderings. We then show that $(3,1)$-canonical ordering for 4-connected triangulations always exist; to our knowledge this variant of canonical ordering was not previously known. We use it to give much simpler proofs of two previously known graph drawing results for 4-connected planar triangulations, namely, rectangular duals and rectangle-of-influence drawings.
Datalog Rewritings of Regular Path Queries using Views
Venue: arXiv cs.DB 2015
Year: 2015

We consider query answering using views on graph databases, i.e. databases structured as edge-labeled graphs. We mainly consider views and queries specified by Regular Path Queries (RPQ). These are queries selecting pairs of nodes in a graph database that are connected via a path whose sequence of edge labels belongs to some regular language. We say that a view V determines a query Q if for all graph databases D, the view image V(D) always contains enough information to answer Q on D. In other words, there is a well defined function from V(D) to Q(D). Our main result shows that when this function is monotone, there exists a rewriting of Q as a Datalog query over the view instance V(D). In particular the rewriting query can be evaluated in time polynomial in the size of V(D). Moreover this implies that it is decidable whether an RPQ query can be rewritten in Datalog using RPQ views.
Detecting Clusters of Anomalies on Low-Dimensional Feature Subsets with Application to Network Traffic Flow Data
Venue: arXiv cs.NI 2015
Year: 2015

In a variety of applications, one desires to detect groups of anomalous data samples, with a group potentially manifesting its atypicality (relative to a reference model) on a low-dimensional subset of the full measured set of features. Samples may only be weakly atypical individually, whereas they may be strongly atypical when considered jointly. What makes this group anomaly detection problem quite challenging is that it is a priori unknown which subset of features jointly manifests a particular group of anomalies. Moreover, it is unknown how many anomalous groups are present in a given data batch. In this work, we develop a group anomaly detection (GAD) scheme to identify the subset of samples and subset of features that jointly specify an anomalous cluster. We apply our approach to network intrusion detection to detect BotNet and peer-to-peer flow clusters. Unlike previous studies, our approach captures and exploits statistical dependencies that may exist between the measured features. Experiments on real world network traffic data demonstrate the advantage of our proposed system, and highlight the importance of exploiting feature dependency structure, compared to the feature (or test) independence assumption made in previous studies.
Robust Large-Scale Localization in 3D Point Clouds Revisited
Venue: arXiv cs.CV 2015
Year: 2015

We tackle the problem of getting a full 6-DOF pose estimation of a query image inside a given point cloud. This technical report re-evaluates the algorithms proposed by Y. Li et al. "Worldwide Pose Estimation using 3D Point Cloud". Our code computes poses from 3 or 4 points, with both known and unknown focal length. The results can easily be displayed and analyzed with Meshlab. We found both advantages and shortcomings of the methods proposed. Furthermore, additional priors and parameters for point selection, RANSAC and pose quality estimate (inlier test) are proposed and applied.
Cell identification in whole-brain multiview images of neural activation
Venue: arXiv cs.CV 2015
Year: 2015

We present a scalable method for brain cell identification in multiview confocal light sheet microscopy images. Our algorithmic pipeline includes a hierarchical registration approach and a novel multiview version of semantic deconvolution that simultaneously enhance visibility of fluorescent cell bodies, equalize their contrast, and fuses adjacent views into a single 3D images on which cell identification is performed with mean shift. We present empirical results on a whole-brain image of an adult Arc-dVenus mouse acquired at 4micron resolution. Based on an annotated test volume containing 3278 cells, our algorithm achieves an $F_1$ measure of 0.89.
Towards a tracking algorithm based on the clustering of spatio-temporal clouds of points
Venue: arXiv cs.CV 2015
Year: 2015

The interest in 3D dynamical tracking is growing in fields such as robotics, biology and fluid dynamics. Recently, a major source of progress in 3D tracking has been the study of collective behaviour in biological systems, where the trajectories of individual animals moving within large and dense groups need to be reconstructed to understand the behavioural interaction rules. Experimental data in this field are generally noisy and at low spatial resolution, so that individuals appear as small featureless objects and trajectories must be retrieved by making use of epipolar information only. Moreover, optical occlusions often occur: in a multi-camera system one or more objects become indistinguishable in one view, potentially jeopardizing the conservation of identity over long-time trajectories. The most advanced 3D tracking algorithms overcome optical occlusions making use of set-cover techniques, which however have to solve NP-hard optimization problems. Moreover, current methods are not able to cope with occlusions arising from actual physical proximity of objects in 3D space. Here, we present a new method designed to work directly in 3D space and time, creating (3D+1) clouds of points representing the full spatio-temporal evolution of the moving targets. We can then use a simple connected components labeling routine, which is linear in time, to solve optical occlusions, hence lowering from NP to P the complexity of the problem. Finally, we use normalized cut spectral clustering to tackle 3D physical proximity.