OpenRaiser/Intern-Atlas huggingface dataset:
Neural Offset Min-Sum Decoding
Venue: arXiv cs.IT 2017
Year: 2017

Recently, it was shown that if multiplicative weights are assigned to the edges of a Tanner graph used in belief propagation decoding, it is possible to use deep learning techniques to find values for the weights which improve the error-correction performance of the decoder. Unfortunately, this approach requires many multiplications, which are generally expensive operations. In this paper, we suggest a more hardware-friendly approach in which offset min-sum decoding is augmented with learnable offset parameters. Our method uses no multiplications and has a parameter count less than half that of the multiplicative algorithm. This both speeds up training and provides a feasible path to hardware architectures. After describing our method, we compare the performance of the two neural decoding algorithms and show that our method achieves error-correction performance within 0.1 dB of the multiplicative approach and as much as 1 dB better than traditional belief propagation for the codes under consideration.
An infinite family of Steiner systems $S(2, 4, 2^m)$ from cyclic codes
Venue: arXiv cs.IT 2017
Year: 2017

Steiner systems are a fascinating topic of combinatorics. The most studied Steiner systems are $S(2, 3, v)$ (Steiner triple systems), $S(3, 4, v)$ (Steiner quadruple systems), and $S(2, 4, v)$. There are a few infinite families of Steiner systems $S(2, 4, v)$ in the literature. The objective of this paper is to present an infinite family of Steiner systems $S(2, 4, 2^m)$ for all $m \equiv 2 \pmod{4} \geq 6$ from cyclic codes. This may be the first coding-theoretic construction of an infinite family of Steiner systems $S(2, 4, v)$. As a by-product, many infinite families of $2$-designs are also reported in this paper.
Observations on Factors Affecting Performance of MapReduce based Apriori on Hadoop Cluster
Venue: arXiv cs.DB 2017
Year: 2017

Designing fast and scalable algorithm for mining frequent itemsets is always being a most eminent and promising problem of data mining. Apriori is one of the most broadly used and popular algorithm of frequent itemset mining. Designing efficient algorithms on MapReduce framework to process and analyze big datasets is contemporary research nowadays. In this paper, we have focused on the performance of MapReduce based Apriori on homogeneous as well as on heterogeneous Hadoop cluster. We have investigated a number of factors that significantly affects the execution time of MapReduce based Apriori running on homogeneous and heterogeneous Hadoop Cluster. Factors are specific to both algorithmic and non-algorithmic improvements. Considered factors specific to algorithmic improvements are filtered transactions and data structures. Experimental results show that how an appropriate data structure and filtered transactions technique drastically reduce the execution time. The non-algorithmic factors include speculative execution, nodes with poor performance, data locality & distribution of data blocks, and parallelism control with input split size. We have applied strategies against these factors and fine tuned the relevant parameters in our particular application. Experimental results show that if cluster specific parameters are taken care of then there is a significant reduction in execution time. Also we have discussed the issues regarding MapReduce implementation of Apriori which may significantly influence the performance.
Bounds and Constructions for Linear Locally Repairable Codes over Binary Fields
Venue: arXiv cs.IT 2017
Year: 2017

For binary $[n,k,d]$ linear locally repairable codes (LRCs), two new upper bounds on $k$ are derived. The first one applies to LRCs with disjoint local repair groups, for general values of $n,d$ and locality $r$, containing some previously known bounds as special cases. The second one is based on solving an optimization problem and applies to LRCs with arbitrary structure of local repair groups. Particularly, an explicit bound is derived from the second bound when $d\geq 5$. A specific comparison shows this explicit bound outperforms the Cadambe-Mazumdar bound for $5\leq d\leq 8$ and large values of $n$. Moreover, a construction of binary linear LRCs with $d\geq6$ attaining our second bound is provided.
On the Capacity for Distributed Index Coding
Venue: arXiv cs.IT 2017
Year: 2017

The distributed index coding problem is studied, whereby multiple messages are stored at different servers to be broadcast to receivers with side information. First, the existing composite coding scheme is enhanced for the centralized (single-server) index coding problem, which is then merged with fractional partitioning of servers to yield a new coding scheme for distributed index coding. New outer bounds on the capacity region are also established. For 213 out of 218 non-isomorphic distributed index coding problems with four messages the achievable sum-rate of the proposed distributed composite coding scheme matches the outer bound, thus establishing the sum-capacity for these problems.
Linear-Complexity Exponentially-Consistent Tests for Universal Outlying Sequence Detection
Venue: arXiv cs.IT 2017
Year: 2017

The problem of universal outlying sequence detection is studied, where the goal is to detect outlying sequences among $M$ sequences of samples. A sequence is considered as outlying if the observations therein are generated by a distribution different from those generating the observations in the majority of the sequences. In the universal setting, we are interested in identifying all the outlying sequences without knowing the underlying generating distributions. In this paper, a class of tests based on distribution clustering is proposed. These tests are shown to be exponentially consistent with linear time complexity in $M$. Numerical results demonstrate that our clustering-based tests achieve similar performance to existing tests, while being considerably more computationally efficient.
From LTL and Limit-Deterministic Büchi Automata to Deterministic Parity Automata
Venue: arXiv cs.LO 2017
Year: 2017

Controller synthesis for general linear temporal logic (LTL) objectives is a challenging task. The standard approach involves translating the LTL objective into a deterministic parity automaton (DPA) by means of the Safra-Piterman construction. One of the challenges is the size of the DPA, which often grows very fast in practice, and can reach double exponential size in the length of the LTL formula. In this paper we describe a single exponential translation from limit-deterministic Büchi automata (LDBA) to DPA, and show that it can be concatenated with a recent efficient translation from LTL to LDBA to yield a double exponential, \enquote{Safraless} LTL-to-DPA construction. We also report on an implementation, a comparison with the SPOT library, and performance on several sets of formulas, including instances from the 2016 SyntComp competition.
Image Compression with SVD : A New Quality Metric Based On Energy Ratio
Venue: arXiv cs.CV 2017
Year: 2017

Digital image compression is a technique that allows to reduce the size of an image in order to increase the capacity storage devices and to optimize the use of network bandwidth. The quality of compressed images with the techniques based on the discrete cosine transform or the wavelet transform is generally measured with PSNR or SSIM. Theses metrics are not suitable to images compressed with the singular values decomposition. This paper presents a new metric based on the energy ratio to measure the quality of the images coded with the SVD. A series of tests on 512 * 512 pixels images show that, for a rank k = 40 corresponding to a SSIM = 0,94 or PSNR = 35 dB, 99,9% of the energy are restored. Three areas of image quality assessments were identified. This new metric is also very accurate and could overcome the weaknesses of PSNR and SSIM.
Mining Shopping Patterns for Divergent Urban Regions by Incorporating Mobility Data
Venue: arXiv cs.SI 2017
Year: 2017

What people buy is an important aspect or view of lifestyles. Studying people's shopping patterns in different urban regions can not only provide valuable information for various commercial opportunities, but also enable a better understanding about urban infrastructure and urban lifestyle. In this paper, we aim to predict city-wide shopping patterns. This is a challenging task due to the sparsity of the available data -- over 60% of the city regions are unknown for their shopping records. To address this problem, we incorporate another important view of human lifestyles, namely mobility patterns. With information on "where people go", we infer "what people buy". Moreover, to model the relations between regions, we exploit spatial interactions in our method. To that end, Collective Matrix Factorization (CMF) with an interaction regularization model is applied to fuse the data from multiple views or sources. Our experimental results have shown that our model outperforms the baseline methods on two standard metrics. Our prediction results on multiple shopping patterns reveal the divergent demands in different urban regions, and thus reflect key functional characteristics of a city. Furthermore, we are able to extract the connection between the two views of lifestyles, and achieve a better or novel understanding of urban lifestyles.
Detection and Analysis of 2016 US Presidential Election Related Rumors on Twitter
Venue: arXiv cs.SI 2017
Year: 2017

The 2016 U.S. presidential election has witnessed the major role of Twitter in the year's most important political event. Candidates used this social media platform extensively for online campaigns. Meanwhile, social media has been filled with rumors, which might have had huge impacts on voters' decisions. In this paper, we present a thorough analysis of rumor tweets from the followers of two presidential candidates: Hillary Clinton and Donald Trump. To overcome the difficulty of labeling a large amount of tweets as training data, we detect rumor tweets by matching them with verified rumor articles. We analyze over 8 million tweets collected from the followers of the two candidates. Our results provide answers to several primary concerns about rumors in this election, including: which side of the followers posted the most rumors, who posted these rumors, what rumors they posted, and when they posted these rumors. The insights of this paper can help us understand the online rumor behaviors in American politics.
Plexus: An Interactive Visualization Tool for Analyzing Public Emotions from Twitter Data
Venue: arXiv cs.HC 2017
Year: 2017

Social media is often used by researchers as an approach to obtaining real-time data on people's activities and thoughts. Twitter, as one of the most popular social networking services nowadays, provides copious information streams on various topics and events. Mining and analyzing Tweets enable us to find public reactions and emotions to activities or objects. This paper presents an interactive visualization tool that identifies and visualizes people's emotions on any two related topics by streaming and processing data from Twitter. The effectiveness of this visualization was evaluated and demonstrated by a feasibility study with 14 participants.
Stay-point Identification as Curve Extrema
Venue: arXiv cs.OH 2017
Year: 2017

In a nutshell, stay-points are locations that a person has stopped for some amount of time. Previous work depends mainly on stay-point identification methods using experimentally fine tuned threshold values. These behave well on their experimental datasets but may exhibit reduced performance on other datasets. In this work, we demonstrate the potential of a geometry-based method for stay-point extraction. This is accomplished by transforming the user's trajectory path to a two-dimensional discrete time series curve that in turn transforms the stay-points to the local minima of the first derivative of this curve. To demonstrate the soundness of the proposed method, we evaluated it on raw, noisy trajectory data acquired over the period of 28 different days using four different techniques. The results demonstrate, among others, that given a good trajectory tracking technique, we can identify correctly 86% to 98% of the stay-points.
Lazy Automata Techniques for WS1S
Venue: arXiv cs.LO 2017
Year: 2017

We present a new decision procedure for the logic WS1S. It originates from the classical approach, which first builds an automaton accepting all models of a formula and then tests whether its language is empty. The main novelty is to test the emptiness on the fly, while constructing a symbolic, term-based representation of the automaton, and prune the constructed state space from parts irrelevant to the test. The pruning is done by a generalization of two techniques used in antichain-based language inclusion and universality checking of finite automata: subsumption and early termination. The richer structure of the WS1S decision problem allows us, however, to elaborate on these techniques in novel ways. Our experiments show that the proposed approach can in many cases significantly outperform the classical decision procedure (implemented in the MONA tool) as well as recently proposed alternatives.
Distributed Unknown-Input-Observers for Cyber Attack Detection and Isolation in Formation Flying UAVs
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, cyber attack detection and isolation is studied on a network of UAVs in a formation flying setup. As the UAVs communicate to reach consensus on their states while making the formation, the communication network among the UAVs makes them vulnerable to a potential attack from malicious adversaries. Two types of attacks pertinent to a network of UAVs have been considered: a node attack on the UAVs and a deception attack on the communication between the UAVs. UAVs formation control presented using a consensus algorithm to reach a pre-specified formation. A node and a communication path deception cyber attacks on the UAV's network are considered with their respective models in the formation setup. For these cyber attacks detection, a bank of Unknown Input Observer (UIO) based distributed fault detection scheme proposed to detect and identify the compromised UAV in the formation. A rule based on the residuals generated using the bank of UIOs are used to detect attacks and identify the compromised UAV in the formation. Further, an algorithm developed to remove the faulty UAV from the network once an attack detected and the compromised UAV isolated while maintaining the formation flight with a missing UAV node.
SCW Codes for Optimal CSI-Free Detection in Diffusive Molecular Communications
Venue: arXiv cs.IT 2017
Year: 2017

Instantaneous or statistical channel state information (CSI) is needed for most detection schemes developed in the molecular communication (MC) literature. Since the MC channel changes, e.g., due to variations in the velocity of flow, the temperature, or the distance between transmitter and receiver, CSI acquisition has to be conducted repeatedly to keep track of CSI variations. Frequent CSI acquisition may entail a large overhead whereas infrequent CSI acquisition may result in a low CSI estimation quality. To cope with these issues, we design codes which facilitate maximum likelihood sequence detection at the receiver without instantaneous or statistical CSI. In particular, assuming concentration shift keying modulation, we show that a class of codes, referred to as strongly constant-weight (SCW) codes, enables optimal CSI-free sequence detection at the cost of decreasing the data rate. For the proposed SCW codes, we analyze the code rate and the error rate. Simulation results verify our analytical derivations and reveal that the proposed CSI-free detector for SCW codes outperforms the baseline coherent and non-coherent detectors for uncoded transmission.
User Activity Detection via Group Testing and Coded Computation
Venue: arXiv cs.IT 2017
Year: 2017

Inspired by group testing algorithms and the coded computation paradigm, we propose and analyze a novel multiple access scheme for detecting active users in large-scale networks. The scheme consists of a simple randomized detection algorithm that uses computation coding as intermediate steps for computing logical disjunction functions over the multiple access channel (MAC). First we show that given an efficient MAC code for disjunction computation the algorithm requires $O(k \log (\frac{N}{k }))$ decision steps for detecting $k$ active users out of $N+k$ users. Subsequently we present a simple suboptimal code for a class of MACs with arbitrarily varying sub-gaussian noise that uniformly requires $O (k \log (N) \max \{ \log k , \log \log N \} )$ channel uses for solving the activity detection problem. This shows that even in the presence of noise an efficient detection of active users is possible. Our approach reveals that the true crux of the matter lies in constructing efficient codes for computing disjunctions over a MAC.
Using Convolutional Neural Networks to Count Palm Trees in Satellite Images
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we propose a supervised learning system for counting and localizing palm trees in high-resolution, panchromatic satellite imagery (40cm/pixel to 1.5m/pixel). A convolutional neural network classifier trained on a set of palm and no-palm images is applied across a satellite image scene in a sliding window fashion. The resultant confidence map is smoothed with a uniform filter. A non-maximal suppression is applied onto the smoothed confidence map to obtain peaks. Trained with a small dataset of 500 images of size 40x40 cropped from satellite images, the system manages to achieve a tree count accuracy of over 99%.
Nearest-Neighbor Based Non-Parametric Probabilistic Forecasting with Applications in Photovoltaic Systems
Venue: arXiv cs.SY 2017
Year: 2017

The present contribution offers a simple methodology for the obtainment of data-driven interval forecasting models by combining pairs of quantile regressions. Those regressions are created without the usage of the non-differentiable pinball-loss function, but through a k-nearest-neighbors based training set transformation and traditional regression approaches. By leaving the underlying training algorithms of the data mining techniques unchanged, the presented approach simplifies the creation of quantile regressions with more complex techniques (e.g. artificial neural networks). The quality of the presented methodology is tested on the usecase of photovoltaic power forecasting, for which quantile regressions using polynomial models as well as artificial neural networks and support vector regressions are created. From the resulting evaluation values it can be concluded that acceptable interval forecasting models are created.
Proving uniformity and independence by self-composition and coupling
Venue: arXiv cs.PL 2017
Year: 2017

Proof by coupling is a classical proof technique for establishing probabilistic properties of two probabilistic processes, like stochastic dominance and rapid mixing of Markov chains. More recently, couplings have been investigated as a useful abstraction for formal reasoning about relational properties of probabilistic programs, in particular for modeling reduction-based cryptographic proofs and for verifying differential privacy. In this paper, we demonstrate that probabilistic couplings can be used for verifying non-relational probabilistic properties. Specifically, we show that the program logic pRHL---whose proofs are formal versions of proofs by coupling---can be used for formalizing uniformity and probabilistic independence. We formally verify our main examples using the EasyCrypt proof assistant.
Correcting Two Deletions and Insertions in Racetrack Memory
Venue: arXiv cs.IT 2017
Year: 2017

Racetrack memory is a non-volatile memory engineered to provide both high density and low latency, that is subject to synchronization or shift errors. This paper describes a fast coding solution, in which delimiter bits assist in identifying the type of shift error, and easily implementable graph-based codes are used to correct the error, once identified. A code that is able to detect and correct double shift errors is described in detail.
On the Robustness of Coordinated Beamforming to Uncoordinated Interference and CSI Uncertainty
Venue: arXiv cs.IT 2017
Year: 2017

As network deployments become denser, interference arises as a dominant performance degradation factor. To confront with this trend, Long Term Evolution (LTE) incorporated features aiming at enabling cooperation among different base stations, a technique termed as Coordinated Multi Point (CoMP). Recent field trial results and theoretical studies of the performance of CoMP schemes revealed, however, that their gains are not as high as initially expected, despite their large coordination overhead. In this paper, we review recent advanced Coordinated Beamforming (CB) schemes, a special family of CoMP that reduces the coordination overhead through a joint choice of transmit and receive linear filters. We focus on assessing their resilience to uncoordinated interference and Channel State Information (CSI) imperfections, which both severely limit the performance gains of all CoMP schemes. We present a simple yet encompassing system model that aims at incorporating different parameters of interest in the relative interference power and CSI errors, and then utilize it for the performance evaluation of the state-of-the-art in CB schemes. It is shown that blindly applying CB in all system scenarios can indeed be counter-productive.
Joint Optimization of Scheduling and Power Control in Wireless Networks: Multi-Dimensional Modeling and Decomposition
Venue: arXiv cs.NI 2017
Year: 2017

The energy efficiency of future networks is becoming a significant and urgent issue, calling for greener network designs. At the same time, rapid development of wireless networks shows a trend of increasing complexity in network structure and resource space, leading to that optimizing the energy efficiency of such networks requires a joint solution over multi-dimensional resource space. However, the coupled resource dimensions and growing problem scales bring great challenges in obtaining the optimal solutions. In this paper, we develop a multi-dimensional network model on the basis of tuple-links associated with transmission patterns (TPs) and formulate the optimization problem as a TP based scheduling problem which jointly solves transmission scheduling, routing, power control, radio and channel assignment. In order to tackle the complexity issues raised from coupled resource dimensions, we propose a novel algorithm that decomposes the coupling scheduling and power control by exploiting the delay column generation technique to recursively solve a master problem for scheduling and a sub-problem for power allocation. Further, we theoretically prove that the performance gap between the proposed algorithm and the optimum is upper bounded by that for the sub-problem solution, where the latter is derived by solving a relaxed version of the sub-problem. Numerical results demonstrate the effectiveness of the multi-dimensional framework and the benefit of the proposed joint optimization in improving network energy efficiency.