OpenRaiser/Intern-Atlas huggingface dataset:
Sorting with Asymmetric Read and Write Costs
Venue: arXiv cs.DS 2016
Year: 2016

Emerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models and algorithms that account for this difference, with a focus on write-efficient sorting algorithms. First, we consider the PRAM model with asymmetric write cost, and show that sorting can be performed in $O\left(n\right)$ writes, $O\left(n \log n\right)$ reads, and logarithmic depth (parallel time). Next, we consider a variant of the External Memory (EM) model that charges $ω> 1$ for writing a block of size $B$ to the secondary memory, and present variants of three EM sorting algorithms (multi-way mergesort, sample sort, and heapsort using buffer trees) that asymptotically reduce the number of writes over the original algorithms, and perform roughly $ω$ block reads for every block write. Finally, we define a variant of the Ideal-Cache model with asymmetric write costs, and present write-efficient, cache-oblivious parallel algorithms for sorting, FFTs, and matrix multiplication. Adapting prior bounds for work-stealing and parallel-depth-first schedulers to the asymmetric setting, these yield parallel cache complexity bounds for machines with private caches or with a shared cache, respectively.
On Euclidean and Hermitian Self-Dual Cyclic Codes over $\mathbb{F}_{2^r}$
Venue: arXiv cs.IT 2016
Year: 2016

Cyclic and self-dual codes are important classes of codes in coding theory. Jia, Ling and Xing \cite{Jia} as well as Kai and Zhu \cite{Kai} proved that Euclidean self-dual cyclic codes of length $n$ over $\mathbb{F}_q$ exist if and only if $n$ is even and $q=2^r$, where $r$ is any positive integer. For $n$ and $q$ even, there always exists an $[n, \frac{n}{2}]$ self-dual cyclic code with generator polynomial $x^{\frac{n}{2}}+1$ called the \textit{trivial self-dual cyclic code}. In this paper we prove the existence of nontrivial self-dual cyclic codes of length $n=2^ν\cdot \bar{n}$, where $\bar{n}$ is odd, over $\mathbb{F}_{2^r}$ in terms of the existence of a nontrivial splitting $(Z, X_0, X_1)$ of $\mathbb{Z}_{\bar{n}}$ by $μ_{-1}$, where $Z, X_0,X_1$ are unions of $2^r$-cyclotomic cosets mod $\bar{n}.$ We also express the formula for the number of cyclic self-dual codes over $\mathbb{F}_{2^r}$ for each $n$ and $r$ in terms of the number of $2^r$-cyclotomic cosets in $X_0$ (or in $X_1$). We also look at Hermitian self-dual cyclic codes and show properties which are analogous to those of Euclidean self-dual cyclic codes. That is, the existence of nontrivial Hermitian self-dual codes over $\mathbb{F}_{2^{2 \ell}}$ based on the existence of a nontrivial splitting $(Z, X_0, X_1)$ of $\mathbb{Z}_{\bar{n}}$ by $μ_{-2^\ell}$, where $Z, X_0,X_1$ are unions of $2^{2 \ell}$-cyclotomic cosets mod $\bar{n}.$ We also determine the lengths at which nontrivial Hermitian self-dual cyclic codes exist and the formula for the number of Hermitian self-dual cyclic codes for each $n$.
A New Approach to Stateless Model Checking of LTL Properties
Venue: arXiv cs.PL 2016
Year: 2016

Verification of large and complicated concurrent programs is an important issue in the software world. Stateless model checking is an appropriate method for systematically and automatically testing of large programs, which has proved its power in verifying code of large programs. Another well-known method in this area is runtime verification. Both stateless model checking and runtime verification are similar in some ways. One common approach in runtime verification is to construct runtime monitors for properties expressed in linear temporal logic. Currently, there are some semantics to check linear temporal logic formulae on finite paths proposed in the field of runtime verification, which can also be applied to stateless model checking. However, existing stateless model checkers do not support LTL formulae. In some settings, it is more advantageous to make use of stateless model checking instead of runtime verification. This paper proposes a novel encoding of one of the recent LTL semantics on finite paths into an actor-based system. We take a truly parallel approach without saving any program states or traces, which not only addresses important problems in runtime verification, but can also be applied to stateless model checking.
The three primary colors of mobile systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we present the notion of "mobile 3C systems in which the "Communications", "Computing", and "Caching" (i.e., 3C) make up the three primary resources/funcationalties, akin to the three primary colors, for a mobile system. We argue that in future mobile networks, the roles of computing and caching are as intrinsic and essential as communications, and only the collective usage of these three primary resources can support the sustainable growth of mobile systems. By defining the 3C resources in their canonical forms, we reveal the important fact that "caching" affects the mobile system performance by introducing non-causality into the system, whereas "computing" achieves capacity gains by performing logical operations across mobile system entities. Many existing capacity-enhancing techniques such as coded multicast, collaborative transmissions, and proactive content pushing can be cast into the native 3C framework for analytical tractability. We further illustrate the mobile 3C concepts with practical examples, including a system on broadcast-unicast convergence for massive media content delivery. The mobile 3C design paradigm opens up new possibilities as well as key research problems bearing academic and practice significance.
Bragg-Williams approximation for the dynamics of prey-predator biological associations
Venue: arXiv cs.CE 2016
Year: 2016

The dynamics of an association of interactive biological species is studied theoretically. We explore a mean field approximation to describe the temporal evolution of an ecological system with the basic prey-predator interspecies relation, as well as an approximation to introduce time correlations in the dynamics. We start by discussing the solution of the Volterra-Lotka model in a mean field approximation based in an analogy with the Weiss solution to the Ising model for ferromagnetic materials. In order to explore the effects of long-range time correlations, we describe the time evolution of the system within a kind of Bragg-Williams approximation. This approach allows us to evaluate a characteristic life-time of the ecosystem. This quantity could be very useful to discuss the time evolution of the system under a wide diversity of environmental conditions of the ecosystem which is not usually considered. We discuss the general trends of the temporal evolution of the association with some data from real ecosystems.
Learning from Imbalanced Multiclass Sequential Data Streams Using Dynamically Weighted Conditional Random Fields
Venue: arXiv cs.LG 2016
Year: 2016

The present study introduces a method for improving the classification performance of imbalanced multiclass data streams from wireless body worn sensors. Data imbalance is an inherent problem in activity recognition caused by the irregular time distribution of activities, which are sequential and dependent on previous movements. We use conditional random fields (CRF), a graphical model for structured classification, to take advantage of dependencies between activities in a sequence. However, CRFs do not consider the negative effects of class imbalance during training. We propose a class-wise dynamically weighted CRF (dWCRF) where weights are automatically determined during training by maximizing the expected overall F-score. Our results based on three case studies from a healthcare application using a batteryless body worn sensor, demonstrate that our method, in general, improves overall and minority class F-score when compared to other CRF based classifiers and achieves similar or better overall and class-wise performance when compared to SVM based classifiers under conditions of limited training data. We also confirm the performance of our approach using an additional battery powered body worn sensor dataset, achieving similar results in cases of high class imbalance.
Learning Gaze Transitions from Depth to Improve Video Saliency Estimation
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we introduce a novel Depth-Aware Video Saliency approach to predict human focus of attention when viewing RGBD videos on regular 2D screens. We train a generative convolutional neural network which predicts a saliency map for a frame, given the fixation map of the previous frame. Saliency estimation in this scenario is highly important since in the near future 3D video content will be easily acquired and yet hard to display. This can be explained, on the one hand, by the dramatic improvement of 3D-capable acquisition equipment. On the other hand, despite the considerable progress in 3D display technologies, most of the 3D displays are still expensive and require wearing special glasses. To evaluate the performance of our approach, we present a new comprehensive database of eye-fixation ground-truth for RGBD videos. Our experiments indicate that integrating depth into video saliency calculation is beneficial. We demonstrate that our approach outperforms state-of-the-art methods for video saliency, achieving 15% relative improvement.
Demonstrating the Feasibility of Automatic Game Balancing
Venue: arXiv cs.HC 2016
Year: 2016

Game balancing is an important part of the (computer) game design process, in which designers adapt a game prototype so that the resulting gameplay is as entertaining as possible. In industry, the evaluation of a game is often based on costly playtests with human players. It suggests itself to automate this process using surrogate models for the prediction of gameplay and outcome. In this paper, the feasibility of automatic balancing using simulation- and deck-based objectives is investigated for the card game top trumps. Additionally, the necessity of a multi-objective approach is asserted by a comparison with the only known (single-objective) method. We apply a multi-objective evolutionary algorithm to obtain decks that optimise objectives, e.g. win rate and average number of tricks, developed to express the fairness and the excitement of a game of top trumps. The results are compared with decks from published top trumps decks using simulation-based objectives. The possibility to generate decks better or at least as good as decks from published top trumps decks in terms of these objectives is demonstrated. Our results indicate that automatic balancing with the presented approach is feasible even for more complex games such as real-time strategy games.
On the Petras algorithm for verified integration of piecewise analytic functions
Venue: arXiv cs.NA 2016
Year: 2016

We consider the algorithm for verified integration of piecewise analytic functions given by Petras. The analysis of the algorithm contained in Patras' paper is limited to a narrow class of functions and gives upper bounds only. We present an estimation of the complexity (measured by a number of evaluations of an integrand) of the algorithm, both upper and lower bounds, for a wider class of functions. We show examples with complexity $Θ(|\ln\eps|/\eps^{p-1})$, for any $p >1$, where $\eps$ is the desired accuracy of the computed integral.
Statistical Distribution of Intensity Fluctuations for Underwater Wireless Optical Channels in the Presence of Air Bubbles
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we experimentally investigate the statistical distribution of intensity fluctuations for underwater wireless optical channels under different channel conditions, namely fresh and salty underwater channels with and without air bubbles. To do so, we first measure the received optical signal with a large number of samples. Based on the normalized acquired data the channel coherence time and the fluctuations probability density function (PDF) are obtained for different channel scenarios. Our experimental results show that salt attenuates the received signal while air bubbles mainly introduce severe intensity fluctuations. Moreover, we observe that log-normal distribution precisely fits the acquired data PDF for scintillation index ($σ^2_I$) values less than $0.1$, while Gamma-Gamma and K distributions aptly predict the intensity fluctuations for $σ^2_I>1$. Since neither of these distributions are capable of predicting the received irradiance for $0.1<σ^2_I<1$, we propose a combination of an exponential and a log-normal distributions to perfectly describe the acquired data PDF for such regimes of scintillation index.
A comprehensive study of sparse codes on abnormality detection
Venue: arXiv cs.CV 2016
Year: 2016

Sparse representation has been applied successfully in abnormal event detection, in which the baseline is to learn a dictionary accompanied by sparse codes. While much emphasis is put on discriminative dictionary construction, there are no comparative studies of sparse codes regarding abnormality detection. We comprehensively study two types of sparse codes solutions - greedy algorithms and convex L1-norm solutions - and their impact on abnormality detection performance. We also propose our framework of combining sparse codes with different detection methods. Our comparative experiments are carried out from various angles to better understand the applicability of sparse codes, including computation time, reconstruction error, sparsity, detection accuracy, and their performance combining various detection methods. Experiments show that combining OMP codes with maximum coordinate detection could achieve state-of-the-art performance on the UCSD dataset [14].
A Stochastic Approach to STDP
Venue: arXiv cs.NE 2016
Year: 2016

We present a digital implementation of the Spike Timing Dependent Plasticity (STDP) learning rule. The proposed digital implementation consists of an exponential decay generator array and a STDP adaptor array. On the arrival of a pre- and post-synaptic spike, the STDP adaptor will send a digital spike to the decay generator. The decay generator will then generate an exponential decay, which will be used by the STDP adaptor to perform the weight adaption. The exponential decay, which is computational expensive, is efficiently implemented by using a novel stochastic approach, which we analyse and characterise here. We use a time multiplexing approach to achieve 8192 (8k) virtual STDP adaptors and decay generators with only one physical implementation of each. We have validated our stochastic STDP approach with measurement results of a balanced excitation/inhibition experiment. Our stochastic approach is ideal for implementing the STDP learning rule in large-scale spiking neural networks running in real time.
Causal Consistency: Beyond Memory
Venue: arXiv cs.DC 2016
Year: 2016

In distributed systems where strong consistency is costly when not impossible, causal consistency provides a valuable abstraction to represent program executions as partial orders. In addition to the sequential program order of each computing entity, causal order also contains the semantic links between the events that affect the shared objects -- messages emission and reception in a communication channel , reads and writes on a shared register. Usual approaches based on semantic links are very difficult to adapt to other data types such as queues or counters because they require a specific analysis of causal dependencies for each data type. This paper presents a new approach to define causal consistency for any abstract data type based on sequential specifications. It explores, formalizes and studies the differences between three variations of causal consistency and highlights them in the light of PRAM, eventual consistency and sequential consistency: weak causal consistency, that captures the notion of causality preservation when focusing on convergence ; causal convergence that mixes weak causal consistency and convergence; and causal consistency, that coincides with causal memory when applied to shared memory.
Wireless Content Caching for Small Cell and D2D Networks
Venue: arXiv cs.IT 2016
Year: 2016

The fifth generation wireless networks must provide fast and reliable connectivity while coping with the ongoing traffic growth. It is of paramount importance that the required resources, such as energy and bandwidth, do not scale with traffic. While the aggregate network traffic is growing at an unprecedented rate, users tend to request the same popular contents at different time instants. Therefore, caching the most popular contents at the network edge is a promising solution to reduce the traffic and the energy consumption over the backhaul links. In this paper, two scenarios are considered, where caching is performed either at a small base station, or directly at the user terminals, which communicate using \ac{D2D} communications. In both scenarios, joint design of the transmission and caching policies is studied when the user demands are known in advance. This joint design offers two different caching gains, namely, the \textit{pre-downloading} and \textit{local caching gains}. It is shown that the finite cache capacity limits the attainable gains, and creates an inherent tradeoff between the two types of gains. In this context, a continuous time optimization problem is formulated to determine the optimal transmission and caching policies that minimize a generic cost function, such as energy, bandwidth, or throughput. The jointly optimal solution is obtained by demonstrating that caching files at a constant rate is optimal, which allows to reformulate the problem as a finite-dimensional convex program. The numerical results show that the proposed joint transmission and caching policy dramatically reduces the total cost, which is particularised to the total energy consumption at the \ac{MBS}, as well as to the total economical cost for the service provider, when users demand economical incentives for delivering content to other users over the D2D links.
Adaptive Mitigation of Multi-Virus Propagation: A Passivity-Based Approach
Venue: arXiv cs.SY 2016
Year: 2016

Malware propagation poses a growing threat to networked systems such as computer networks and cyber-physical systems. Current approaches to defending against malware propagation are based on patching or filtering susceptible nodes at a fixed rate. When the propagation dynamics are unknown or uncertain, however, the static rate that is chosen may be either insufficient to remove all viruses or too high, incurring additional performance cost. In this paper, we formulate adaptive strategies for mitigating multiple malware epidemics when the propagation rate is unknown, using patching and filtering-based defense mechanisms. In order to identify conditions for ensuring that all viruses are asymptotically removed, we show that the malware propagation, patching, and filtering processes can be modeled as coupled passive dynamical systems. We prove that the patching rate required to remove all viruses is bounded above by the passivity index of the coupled system, and formulate the problem of selecting the minimum-cost mitigation strategy. Our results are evaluated through numerical study.
Linear Sum Assignment with Edition
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of transforming a set of elements into another by a sequence of elementary edit operations, namely substitutions, removals and insertions of elements. Each possible edit operation is penalized by a non-negative cost and the cost of a transformation is measured by summing the costs of its operations. A solution to this problem consists in defining a transformation having a minimal cost, among all possible transformations. To compute such a solution, the classical approach consists in representing removal and insertion operations by augmenting the two sets so that they get the same size. This allows to express the problem as a linear sum assignment problem (LSAP), which thus finds an optimal bijection (or permutation, perfect matching) between the two augmented sets. While the LSAP is known to be efficiently solvable in polynomial time complexity, for instance with the Hungarian algorithm, useless time and memory are spent to treat the elements which have been added to the initial sets. In this report, we show that the problem can be formalized as an extension of the LSAP which considers only one additional element in each set to represent removal and insertion operations. A solution to the problem is no longer represented as a bijection between the two augmented sets. We show that the considered problem is a binary linear program (BLP) very close to the LSAP. While it can be solved by any BLP solver, we propose an adaptation of the Hungarian algorithm which improves the time and memory complexities previously obtained by the approach based on the LSAP. The importance of the improvement increases as the size of the two sets and their absolute difference increase. Based on the analysis of the problem presented in this report, other classical algorithms can be adapted.
Criteria of efficiency for conformal prediction
Venue: arXiv cs.LG 2016
Year: 2016

We study optimal conformity measures for various criteria of efficiency of classification in an idealised setting. This leads to an important class of criteria of efficiency that we call probabilistic; it turns out that the most standard criteria of efficiency used in literature on conformal prediction are not probabilistic unless the problem of classification is binary. We consider both unconditional and label-conditional conformal prediction.
Distinguishing between Topical and Non-topical Information Diffusion Mechanisms in Social Media
Venue: arXiv cs.SI 2016
Year: 2016

A number of recent studies of information diffusion in social media, both empirical and theoretical, have been inspired by viral propagation models derived from epidemiology. These studies model the propagation of memes, i.e., pieces of information, between users in a social network similarly to the way diseases spread in human society. Importantly, one would expect a meme to spread in a social network amongst the people who are interested in the topic of that meme. Yet, the importance of topicality for information diffusion has been less explored in the literature. Here, we study empirical data about two different types of memes (hashtags and URLs) spreading through the Twitter's online social network. For every meme, we infer its topics and for every user, we infer her topical interests. To analyze the impact of such topics on the propagation of memes, we introduce a novel theoretical framework of information diffusion. Our analysis identifies two distinct mechanisms, namely topical and non-topical, of information diffusion. The non-topical information diffusion resembles disease spreading as in simple contagion. In contrast, the topical information diffusion happens between users who are topically aligned with the information and has characteristics of complex contagion. Non-topical memes spread broadly among all users and end up being relatively popular. Topical memes spread narrowly among users who have interests topically aligned with them and are diffused more readily after multiple exposures. Our results show that the topicality of memes and users' interests are essential for understanding and predicting information diffusion.