OpenRaiser/Intern-Atlas huggingface dataset:
Container-Based Cloud Virtual Machine Benchmarking
Venue: arXiv cs.DC 2016
Year: 2016

With the availability of a wide range of cloud Virtual Machines (VMs) it is difficult to determine which VMs can maximise the performance of an application. Benchmarking is commonly used to this end for capturing the performance of VMs. Most cloud benchmarking techniques are typically heavyweight - time consuming processes which have to benchmark the entire VM in order to obtain accurate benchmark data. Such benchmarks cannot be used in real-time on the cloud and incur extra costs even before an application is deployed. In this paper, we present lightweight cloud benchmarking techniques that execute quickly and can be used in near real-time on the cloud. The exploration of lightweight benchmarking techniques are facilitated by the development of DocLite - Docker Container-based Lightweight Benchmarking. DocLite is built on the Docker container technology which allows a user-defined portion (such as memory size and the number of CPU cores) of the VM to be benchmarked. DocLite operates in two modes, in the first mode, containers are used to benchmark a small portion of the VM to generate performance ranks. In the second mode, historic benchmark data is used along with the first mode as a hybrid to generate VM ranks. The generated ranks are evaluated against three scientific high-performance computing applications. The proposed techniques are up to 91 times faster than a heavyweight technique which benchmarks the entire VM. It is observed that the first mode can generate ranks with over 90% and 86% accuracy for sequential and parallel execution of an application. The hybrid mode improves the correlation slightly but the first mode is sufficient for benchmarking cloud VMs.
Mining frequent items in the time fading model
Venue: arXiv cs.DS 2016
Year: 2016

We present FDCMSS, a new sketch-based algorithm for mining frequent items in data streams. The algorithm cleverly combines key ideas borrowed from forward decay, the Count-Min and the Space Saving algorithms. It works in the time fading model, mining data streams according to the cash register model. We formally prove its correctness and show, through extensive experimental results, that our algorithm outperforms $λ$-HCount, a recently developed algorithm, with regard to speed, space used, precision attained and error committed on both synthetic and real datasets.
Selection of Most Effective Control Variables for Solving Optimal Power Flow Using Sensitivity Analysis in Particle Swarm Algorithm
Venue: arXiv cs.CE 2016
Year: 2016

Solving the optimal power flow problem is one of the main objectives in electrical power systems analysis and design. The modern optimization algorithms such as the evolutionary algorithms are also adopted to solve this problem, especially when the intermittency nature of generation resources are included, as in wind and solar energy resources, where the models are stochastic and non-linear. This paper uses the particle swarm optimization algorithm for solving the optimal power flow for IEEE-30 bus system. In addition to selection of the most effective control variables based on sensitivity analysis to alleviate the violations and return the system back to its normal state. This adopted strategy would decrease the optimal power flow calculation burden by particle swarm optimization algorithm, especially with large systems.
Sound and Complete Runtime Security Monitor for Application Software
Venue: arXiv cs.CR 2016
Year: 2016

Conventional approaches for ensuring the security of application software at run-time, through monitoring, either produce (high rates of) false alarms (e.g. intrusion detection systems) or limit application performance (e.g. run-time verification). We present a runtime security monitor that detects both known and unknown cyber attacks by checking that the run-time behavior of the application is consistent with the expected behavior modeled in application specification. This is crucial because, even if the implementation is consistent with its specification, the application may still be vulnerable due to flaws in the supporting infrastructure (e.g. the language runtime system, libraries and operating system). This runtime security monitor is sound and complete, eliminating false alarms, as well as efficient, so that it does not limit runtime application performance and so that it supports real-time systems. The security monitor takes as input the application specification and the application implementation, which may be expressed in different languages. The specification language of the application software is formalized based on monadic second order logic and event calculus interpreted over algebraic data structures. This language allows us to express behavior of an application at any desired (and practical) level of abstraction as well as with high degree of modularity. The security monitor detects every attack by systematically comparing the application execution and specification behaviors at runtime, even though they operate at two different levels of abstraction. We define the denotational semantics of the specification language and prove that the monitor is sound and complete. Furthermore, the monitor is efficient because of the modular application specification at appropriate level(s) of abstraction.
Heterogeneous substitution systems revisited
Venue: arXiv cs.LO 2016
Year: 2016

Matthes and Uustalu (TCS 327(1-2):155-174, 2004) presented a categorical description of substitution systems capable of capturing syntax involving binding which is independent of whether the syntax is made up from least or greatest fixed points. We extend this work in two directions: we continue the analysis by creating more categorical structure, in particular by organizing substitution systems into a category and studying its properties, and we develop the proofs of the results of the cited paper and our new ones in UniMath, a recent library of univalent mathematics formalized in the Coq theorem prover.
Secure Information Sharing in an Industrial Internet of Things
Venue: arXiv cs.CR 2016
Year: 2016

This paper investigates how secure information sharing with external vendors can be achieved in an Industrial Internet of Things (IIoT). It also identifies necessary security requirements for secure information sharing based on identified security challenges stated by the industry. The paper then proposes a roadmap for improving security in IIoT which investigates both short-term and long-term solutions for protecting IIoT devices. The short-term solution is mainly based on integrating existing good practices. The paper also outlines a long term solution for protecting IIoT devices with fine-grained access control for sharing data between external entities that would support cloud-based data storage.
Feedback from Nature: Simple Randomised Distributed Algorithms for Maximal Independent Set Selection and Greedy Colouring
Venue: arXiv cs.DC 2016
Year: 2016

We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance in a simple and novel way. Our algorithm for maximal independent set selection operates on a network of identical anonymous processors. The processor at each node has no prior information about the network. At each time step, each node can only broadcast a single bit to all its neighbours, or remain silent. Each node can detect whether one or more neighbours have broadcast, but cannot tell how many of its neighbours have broadcast, or which ones. We build on recent work of Afek et al. which was inspired by studying the development of a network of cells in the fruit fly~\cite{Afek2011a}. However we incorporate for the first time another important feature of the biological system: varying the probability value used at each node based on local feedback from neighbouring nodes. Given any $n$-node network, our algorithm achieves the optimal expected time complexity of $O(\log n)$ rounds and the optimal expected message complexity of $O(1)$ single-bit messages broadcast by each node.We also show that the previous approach, without feedback, cannot achieve better than $Ω(\log^2 n)$ expected time complexity, whatever global scheme is used to choose the probabilities. Our algorithm for distributed greedy colouring works under similar harsh conditions: each identical node has no prior information about the network, can only broadcast a single message to all neighbours at each time step representing a desired colour, and can only detect whether at least one neighbour has broadcast each colour value. We show that our algorithm has an expected time complexity of $O(Δ+\log n)$, where $Δ$ is the maximum degree of the network, and expected message complexity of $O(1)$ messages broadcast by each node.
Learning the kernel matrix via predictive low-rank approximations
Venue: arXiv cs.LG 2016
Year: 2016

Efficient and accurate low-rank approximations of multiple data sources are essential in the era of big data. The scaling of kernel-based learning algorithms to large datasets is limited by the O(n^2) computation and storage complexity of the full kernel matrix, which is required by most of the recent kernel learning algorithms. We present the Mklaren algorithm to approximate multiple kernel matrices learn a regression model, which is entirely based on geometrical concepts. The algorithm does not require access to full kernel matrices yet it accounts for the correlations between all kernels. It uses Incomplete Cholesky decomposition, where pivot selection is based on least-angle regression in the combined, low-dimensional feature space. The algorithm has linear complexity in the number of data points and kernels. When explicit feature space induced by the kernel can be constructed, a mapping from the dual to the primal Ridge regression weights is used for model interpretation. The Mklaren algorithm was tested on eight standard regression datasets. It outperforms contemporary kernel matrix approximation approaches when learning with multiple kernels. It identifies relevant kernels, achieving highest explained variance than other multiple kernel learning methods for the same number of iterations. Test accuracy, equivalent to the one using full kernel matrices, was achieved with at significantly lower approximation ranks. A difference in run times of two orders of magnitude was observed when either the number of samples or kernels exceeds 3000.
Rate Maximization of Decode-and-Forward Relaying Systems with RF Energy Harvesting
Venue: arXiv cs.IT 2016
Year: 2016

We consider a three-node decode-and-forward (DF) half-duplex relaying system, where the source first harvests RF energy from the relay, and then uses this energy to transmit information to the destination via the relay. We assume that the information transfer and wireless power transfer phases alternate over time in the same frequency band, and their {\it time fraction} (TF) may change or be fixed from one transmission epoch (fading state) to the next. For this system, we maximize the achievable average data rate. Thereby, we propose two schemes: (1) jointly optimal power and TF allocation, and (2) optimal power allocation with fixed TF. Due to the small amounts of harvested power at the source, the two schemes achieve similar information rates, but yield significant performance gains compared to a benchmark system with fixed power and fixed TF allocation.
On Competitive Algorithms for Approximations of Top-k-Position Monitoring of Distributed Streams
Venue: arXiv cs.DS 2016
Year: 2016

Consider the continuous distributed monitoring model in which $n$ distributed nodes, receiving individual data streams, are connected to a designated server. The server is asked to continuously monitor a function defined over the values observed across all streams while minimizing the communication. We study a variant in which the server is equipped with a broadcast channel and is supposed to keep track of an approximation of the set of nodes currently observing the $k$ largest values. Such an approximate set is exact except for some imprecision in an $\varepsilon$-neighborhood of the $k$-th largest value. This approximation of the Top-$k$-Position Monitoring Problem is of interest in cases where marginal changes (e.g. due to noise) in observed values can be ignored so that monitoring an approximation is sufficient and can reduce communication. This paper extends our results from [IPDPS'15], where we have developed a filter-based online algorithm for the (exact) Top-k-Position Monitoring Problem. There we have presented a competitive analysis of our algorithm against an offline adversary that also is restricted to filter-based algorithms. Our new algorithms as well as their analyses use new methods. We analyze their competitiveness against adversaries that use both exact and approximate filter-based algorithms, and observe severe differences between the respective powers of these adversaries.
Second-Order and Moderate Deviation Asymptotics for Successive Refinement
Venue: arXiv cs.IT 2016
Year: 2016

We derive the optimal second-order coding region and moderate deviations constant for successive refinement source coding with a joint excess-distortion probability constraint. We consider two scenarios: (i) a discrete memoryless source (DMS) and arbitrary distortion measures at the decoders and (ii) a Gaussian memoryless source (GMS) and quadratic distortion measures at the decoders. For a DMS with arbitrary distortion measures, we prove an achievable second-order coding region, using type covering lemmas by Kanlis and Narayan and by No, Ingber and Weissman. We prove the converse using the perturbation approach by Gu and Effros. When the DMS is successively refinable, the expressions for the second-order coding region and the moderate deviations constant are simplified and easily computable. For this case, we also obtain new insights on the second-order behavior compared to the scenario where separate excess-distortion proabilities are considered. For example, we describe a DMS, for which the optimal second-order region transitions from being characterizable by a bivariate Gaussian to a univariate Gaussian, as the distortion levels are varied. We then consider a GMS with quadratic distortion measures. To prove the direct part, we make use of the sphere covering theorem by Verger-Gaugry, together with appropriately-defined Gaussian type classes. To prove the converse, we generalize Kostina and Verdú's one-shot converse bound for point-to-point lossy source coding. We remark that this proof is applicable to general successively refinable sources. In the proofs of the moderate deviations results for both scenarios, we follow a strategy similar to that for the second-order asymptotics and use the moderate deviations principle.
Predicting human mobility through the assimilation of social media traces into mobility models
Venue: arXiv cs.SI 2016
Year: 2016

Predicting human mobility flows at different spatial scales is challenged by the heterogeneity of individual trajectories and the multi-scale nature of transportation networks. As vast amounts of digital traces of human behaviour become available, an opportunity arises to improve mobility models by integrating into them proxy data on mobility collected by a variety of digital platforms and location-aware services. Here we propose a hybrid model of human mobility that integrates a large-scale publicly available dataset from a popular photo-sharing system with the classical gravity model, under a stacked regression procedure. We validate the performance and generalizability of our approach using two ground-truth datasets on air travel and daily commuting in the United States: using two different cross-validation schemes we show that the hybrid model affords enhanced mobility prediction at both spatial scales.
Solutions to the Problem of K-SAT / K-COL Phase Transition Location
Venue: arXiv cs.CC 2016
Year: 2016

As general theories, currently there are concentration inequalities (of random walk) only for the cases of independence and martingale differences. In this paper, the concentration inequalities are extended to more general situations. In terms of the theory presented in the paper, the condition of independence is $\frac { \partial y } {\partial t}=$ constant and martingale difference's is $\frac { \partial y } {\partial t} = 0 $. This paper relaxes these conditions to $\frac { \partial^2 y } {\partial u_i \partial t} \le L$; i.e. $\frac { \partial y } {\partial t}$ can vary. Further, the concentration inequalities are extended to branching random walk, the applications of which solve some long standing open problems, including the well known problems of K-SAT and K-COL phase transition locations, among others.
Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems
Venue: arXiv cs.DC 2016
Year: 2016

The atomic register is certainly the most basic object of computing science. Its implementation on top of an n-process asynchronous message-passing system has received a lot of attention. It has been shown that t \textless{} n/2 (where t is the maximal number of processes that may crash) is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous message-passing system. Considering such a context, this paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm. Its time-efficiency is measured according to two different underlying synchrony assumptions. Whatever this assumption, a write operation always costs a round-trip delay, while a read operation costs always a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the one of the famous ABD algorithm (proposed by Attiya, Bar-Noy, and Dolev).
Analyzing Locality of Mobile Messaging Traffic using the MATAdOR Framework
Venue: arXiv cs.NI 2016
Year: 2016

Mobile messaging services have gained a large share in global telecommunications. Unlike conventional services like phone calls, text messages or email, they do not feature a standardized environment enabling a federated and potentially local service architecture. We present an extensive and large-scale analysis of communication patterns for four popular mobile messaging services between 28 countries and analyze the locality of communication and the resulting impact on user privacy. We show that server architectures for mobile messaging services are highly centralized in single countries. This forces messages to drastically deviate from a direct communication path, enabling hosting and transfer countries to potentially intercept and censor traffic. To conduct this work, we developed a measurement framework to analyze traffic of such mobile messaging services. It allows to conduct automated experiments with mobile messaging applications, is transparent to those applications and does not require any modifications to the applications.
A Closed-Form Solution to Tensor Voting: Theory and Applications
Venue: arXiv cs.CV 2016
Year: 2016

We prove a closed-form solution to tensor voting (CFTV): given a point set in any dimensions, our closed-form solution provides an exact, continuous and efficient algorithm for computing a structure-aware tensor that simultaneously achieves salient structure detection and outlier attenuation. Using CFTV, we prove the convergence of tensor voting on a Markov random field (MRF), thus termed as MRFTV, where the structure-aware tensor at each input site reaches a stationary state upon convergence in structure propagation. We then embed structure-aware tensor into expectation maximization (EM) for optimizing a single linear structure to achieve efficient and robust parameter estimation. Specifically, our EMTV algorithm optimizes both the tensor and fitting parameters and does not require random sampling consensus typically used in existing robust statistical techniques. We performed quantitative evaluation on its accuracy and robustness, showing that EMTV performs better than the original TV and other state-of-the-art techniques in fundamental matrix estimation for multiview stereo matching. The extensions of CFTV and EMTV for extracting multiple and nonlinear structures are underway. An addendum is included in this arXiv version.
Traffic Confirmation Attacks Despite Noise
Venue: arXiv cs.CR 2016
Year: 2016

We propose a traffic confirmation attack on low-latency mix networks based on computing robust real-time binary hashes of network traffic flows. Firstly, we adapt the Coskun-Memon Algorithm to construct hashes that can withstand network impairments to allow fast matching of network flows. The resulting attack has a low startup cost and achieves a true positive match rate of 80% when matching one flow out of 9000 with less than 2% false positives, showing traffic confirmation attacks can be highly accurate even when only part of the network traffic flow is seen. Secondly, we attack probabilistic padding schemes achieving a match rate of over 90% from 9000 network traffic flows, showing advanced padding techniques are still vulnerable to traffic confirmation attacks.
Graded Entailment for Compositional Distributional Semantics
Venue: arXiv cs.CL 2016
Year: 2016

The categorical compositional distributional model of natural language provides a conceptually motivated procedure to compute the meaning of sentences, given grammatical structure and the meanings of its words. This approach has outperformed other models in mainstream empirical language processing tasks. However, until recently it has lacked the crucial feature of lexical entailment -- as do other distributional models of meaning. In this paper we solve the problem of entailment for categorical compositional distributional semantics. Taking advantage of the abstract categorical framework allows us to vary our choice of model. This enables the introduction of a notion of entailment, exploiting ideas from the categorical semantics of partial knowledge in quantum computation. The new model of language uses density matrices, on which we introduce a novel robust graded order capturing the entailment strength between concepts. This graded measure emerges from a general framework for approximate entailment, induced by any commutative monoid. Quantum logic embeds in our graded order. Our main theorem shows that entailment strength lifts compositionally to the sentence level, giving a lower bound on sentence entailment. We describe the essential properties of graded entailment such as continuity, and provide a procedure for calculating entailment strength.
Polar Codes and Polar Lattices for Independent Fading Channels
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we design polar codes and polar lattices for i.i.d. fading channels when the channel state information is only available to the receiver. For the binary input case, we propose a new design of polar codes through single-stage polarization to achieve the ergodic capacity. For the non-binary input case, polar codes are further extended to polar lattices to achieve the egodic Poltyrev capacity, i.e., the capacity without power limit. When the power constraint is taken into consideration, we show that polar lattices with lattice Gaussian shaping achieve the egodic capacity of fading channels. The coding and shaping are both explicit, and the overall complexity of encoding and decoding is $O(N \log^2 N)$.