OpenRaiser/Intern-Atlas huggingface dataset:
Symbol-Decision Successive Cancellation List Decoder for Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

Polar codes are of great interests because they provably achieve the capacity of both discrete and continuous memoryless channels while having an explicit construction. Most existing decoding algorithms of polar codes are based on bit-wise hard or soft decisions. In this paper, we propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. First, we propose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination also has a lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arikan's channel transformations also helps to share hardware resources between calculating bit- and symbol-wise channel transition probabilities. Second, a two-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Third, since memory is a significant part of SCL decoders, we propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder. Finally, to evaluate the throughput advantage of our symbol-decision decoders, we design an architecture based on a semi-parallel successive cancellation list decoder. In this architecture, different symbol sizes, sorting implementations, and message scheduling schemes are considered. Our synthesis results show that in terms of area efficiency, our symbol-decision SCL decoders outperform both bit- and symbol-decision SCL decoders.
Robust Face Recognition by Constrained Part-based Alignment
Venue: arXiv cs.CV 2015
Year: 2015

Developing a reliable and practical face recognition system is a long-standing goal in computer vision research. Existing literature suggests that pixel-wise face alignment is the key to achieve high-accuracy face recognition. By assuming a human face as piece-wise planar surfaces, where each surface corresponds to a facial part, we develop in this paper a Constrained Part-based Alignment (CPA) algorithm for face recognition across pose and/or expression. Our proposed algorithm is based on a trainable CPA model, which learns appearance evidence of individual parts and a tree-structured shape configuration among different parts. Given a probe face, CPA simultaneously aligns all its parts by fitting them to the appearance evidence with consideration of the constraint from the tree-structured shape configuration. This objective is formulated as a norm minimization problem regularized by graph likelihoods. CPA can be easily integrated with many existing classifiers to perform part-based face recognition. Extensive experiments on benchmark face datasets show that CPA outperforms or is on par with existing methods for robust face recognition across pose, expression, and/or illumination changes.
Personal Data: Thinking Inside the Box
Venue: arXiv cs.CY 2015
Year: 2015

We propose there is a need for a technical platform enabling people to engage with the collection, management and consumption of personal data; and that this platform should itself be personal, under the direct control of the individual whose data it holds. In what follows, we refer to this platform as the Databox, a personal, networked service that collates personal data and can be used to make those data available. While your Databox is likely to be a virtual platform, in that it will involve multiple devices and services, at least one instance of it will exist in physical form such as on a physical form-factor computing device with associated storage and networking, such as a home hub.
An Alternate Construction of an Access-Optimal Regenerating Code with Optimal Sub-Packetization Level
Venue: arXiv cs.IT 2015
Year: 2015

Given the scale of today's distributed storage systems, the failure of an individual node is a common phenomenon. Various metrics have been proposed to measure the efficacy of the repair of a failed node, such as the amount of data download needed to repair (also known as the repair bandwidth), the amount of data accessed at the helper nodes, and the number of helper nodes contacted. Clearly, the amount of data accessed can never be smaller than the repair bandwidth. In the case of a help-by-transfer code, the amount of data accessed is equal to the repair bandwidth. It follows that a help-by-transfer code possessing optimal repair bandwidth is access optimal. The focus of the present paper is on help-by-transfer codes that employ minimum possible bandwidth to repair the systematic nodes and are thus access optimal for the repair of a systematic node. The zigzag construction by Tamo et al. in which both systematic and parity nodes are repaired is access optimal. But the sub-packetization level required is $r^k$ where $r$ is the number of parities and $k$ is the number of systematic nodes. To date, the best known achievable sub-packetization level for access-optimal codes is $r^{k/r}$ in a MISER-code-based construction by Cadambe et al. in which only the systematic nodes are repaired and where the location of symbols transmitted by a helper node depends only on the failed node and is the same for all helper nodes. Under this set-up, it turns out that this sub-packetization level cannot be improved upon. In the present paper, we present an alternate construction under the same setup, of an access-optimal code repairing systematic nodes, that is inspired by the zigzag code construction and that also achieves a sub-packetization level of $r^{k/r}$.
Relational semantics of linear logic and higher-order model-checking
Venue: arXiv cs.LO 2015
Year: 2015

In this article, we develop a new and somewhat unexpected connection between higher-order model-checking and linear logic. Our starting point is the observation that once embedded in the relational semantics of linear logic, the Church encoding of any higher-order recursion scheme (HORS) comes together with a dual Church encoding of an alternating tree automata (ATA) of the same signature. Moreover, the interaction between the relational interpretations of the HORS and of the ATA identifies the set of accepting states of the tree automaton against the infinite tree generated by the recursion scheme. We show how to extend this result to alternating parity automata (APT) by introducing a parametric version of the exponential modality of linear logic, capturing the formal properties of colors (or priorities) in higher-order model-checking. We show in particular how to reunderstand in this way the type-theoretic approach to higher-order model-checking developed by Kobayashi and Ong. We briefly explain in the end of the paper how his analysis driven by linear logic results in a new and purely semantic proof of decidability of the formulas of the monadic second-order logic for higher-order recursion schemes.
i2MapReduce: Incremental MapReduce for Mining Evolving Big Data
Venue: arXiv cs.DC 2015
Year: 2015

As new data and updates are constantly arriving, the results of data mining applications become stale and obsolete over time. Incremental processing is a promising approach to refreshing mining results. It utilizes previously saved states to avoid the expense of re-computation from scratch. In this paper, we propose i2MapReduce, a novel incremental processing extension to MapReduce, the most widely used framework for mining big data. Compared with the state-of-the-art work on Incoop, i2MapReduce (i) performs key-value pair level incremental processing rather than task level re-computation, (ii) supports not only one-step computation but also more sophisticated iterative computation, which is widely used in data mining applications, and (iii) incorporates a set of novel techniques to reduce I/O overhead for accessing preserved fine-grain computation states. We evaluate i2MapReduce using a one-step algorithm and three iterative algorithms with diverse computation characteristics. Experimental results on Amazon EC2 show significant performance improvements of i2MapReduce compared to both plain and iterative MapReduce performing re-computation.
Optimal Energy Allocation Policy for Wireless Networks in the Sky
Venue: arXiv cs.NI 2015
Year: 2015

Google's Project Loon was launched in 2013 with the aim of providing Internet access to rural and remote areas. In the Loon network, balloons travel around the Earth and bring access points to the users who cannot connect directly to the global wired Internet. The signals from the users will be transmitted through the balloon network to the base stations connected to the Internet service provider (ISP) on Earth. The process of transmitting and receiving data consume a certain amount of energy from the balloon, while the energy on balloons cannot be supplied by stable power source or by replacing batteries frequently. Instead, the balloons can harvest energy from natural energy sources, e.g., solar energy, or from radio frequency energy by equipping with appropriate circuits. However, such kinds of energy sources are often dynamic and thus how to use this energy efficiently is the main goal of this paper. In this paper, we study the optimal energy allocation problem for the balloons such that network performance is optimized and the revenue for service providers is maximized. We first formulate the stochastic optimization problem as a Markov decision process and then apply a learning algorithm based on simulation-based method to obtain optimal policies for the balloons. Numerical results obtained by extensive simulations clearly show the efficiency and convergence of the proposed learning algorithm.
Memoization for Unary Logic Programming: Characterizing PTIME
Venue: arXiv cs.LO 2015
Year: 2015

We give a characterization of deterministic polynomial time computation based on an algebraic structure called the resolution semiring, whose elements can be understood as logic programs or sets of rewriting rules over first-order terms. More precisely, we study the restriction of this framework to terms (and logic programs, rewriting rules) using only unary symbols. We prove it is complete for polynomial time computation, using an encoding of pushdown automata. We then introduce an algebraic counterpart of the memoization technique in order to show its PTIME soundness. We finally relate our approach and complexity results to complexity of logic programming. As an application of our techniques, we show a PTIME-completeness result for a class of logic programming queries which use only unary function symbols.
An Algebra to Merge Heterogeneous Classifiers
Venue: arXiv cs.DM 2015
Year: 2015

In distributed classification, each learner observes its environment and deduces a classifier. As a learner has only a local view of its environment, classifiers can be exchanged among the learners and integrated, or merged, to improve accuracy. However, the operation of merging is not defined for most classifiers. Furthermore, the classifiers that have to be merged may be of different types in settings such as ad-hoc networks in which several generations of sensors may be creating classifiers. We introduce decision spaces as a framework for merging possibly different classifiers. We formally study the merging operation as an algebra, and prove that it satisfies a desirable set of properties. The impact of time is discussed for the two main data mining settings. Firstly, decision spaces can naturally be used with non-stationary distributions, such as the data collected by sensor networks, as the impact of a model decays over time. Secondly, we introduce an approach for stationary distributions, such as homogeneous databases partitioned over different learners, which ensures that all models have the same impact. We also present a method that uses storage flexibly to achieve different types of decay for non-stationary distributions. Finally, we show that the algebraic approach developed for merging can also be used to analyze the behaviour of other operators.
Formal requirement and architecture specifications of a multi-agent robotic system
Venue: arXiv cs.SE 2015
Year: 2015

One of the most challenging tasks in specification engineering for a multi-agent robotic system is to formally specify and architect the system, especially as a multi-agent robotic system is concurrent having concurrent processing, and often having dynamic environment. The formal requirement and architecture specifications along with step-wise refinement from abstract to concrete concepts play major role in formalizing the system. This paper proposes the formal requirement and architecture specifications aspects of an approach that supports analysis with respect to functional as well as non-functional properties by step-wise refinement from abstract to concrete specifications and formal architecture definition. These formal specifications have been exemplified by a case study. As formal specification techniques are getting more mature, our capability to build a correct complex multi-agent robotic system also grows quickly.
Multi Stage based Time Series Analysis of User Activity on Touch Sensitive Surfaces in Highly Noise Susceptible Environments
Venue: arXiv cs.HC 2015
Year: 2015

This article proposes a multistage framework for time series analysis of user activity on touch sensitive surfaces in noisy environments. Here multiple methods are put together in multi stage framework; including moving average, moving median, linear regression, kernel density estimation, partial differential equations and Kalman filter. The proposed three stage filter consisting of partial differential equation based denoising, Kalman filter and moving average method provides ~25% better noise reduction than other methods according to Mean Squared Error (MSE) criterion in highly noise susceptible environments. Apart from synthetic data, we also obtained real world data like hand writing, finger/stylus drags etc. on touch screens in the presence of high noise such as unauthorized charger noise or display noise and validated our algorithms. Furthermore, the proposed algorithm performs qualitatively better than the existing solutions for touch panels of the high end hand held devices available in the consumer electronics market qualitatively.
Handwritten Devanagari Script Segmentation: A non-linear Fuzzy Approach
Venue: arXiv cs.CV 2015
Year: 2015

The paper concentrates on improvement of segmentation accuracy by addressing some of the key challenges of handwritten Devanagari word image segmentation technique. In the present work, we have developed a new feature based approach for identification of Matra pixels from a word image, design of a non-linear fuzzy membership functions for headline estimation and finally design of a non-linear fuzzy functions for identifying segmentation points on the Matra. The segmentation accuracy achieved by the current technique is 94.8%. This shows an improvement of performance by 1.8% over the previous technique [1] on a 300-word dataset, used for the current experiment.
Permanent versus determinant: not via saturations
Venue: arXiv cs.CC 2015
Year: 2015

Let Det_n denote the closure of the GL_{n^2}(C)-orbit of the determinant polynomial det_n with respect to linear substitution. The highest weights (partitions) of irreducible GL_{n^2}(C)-representations occurring in the coordinate ring of Det_n form a finitely generated monoid S(Det_n). We prove that the saturation of S(Det_n) contains all partitions lambda with length at most n and size divisible by n. This implies that representation theoretic obstructions for the permanent versus determinant problem must be holes of the monoid S(Det_n).
Mespotine-RLE-basic v0.9 - An overhead-reduced and improved Run-Length-Encoding Method
Venue: arXiv cs.DS 2015
Year: 2015

Run Length Encoding(RLE) is one of the oldest algorithms for data-compression available, a method used for compression of large data into smaller and therefore more compact data. It compresses by looking at the data for repetitions of the same character in a row and storing the amount(called run) and the respective character(called run_value) as target-data. Unfortunately it only compresses within strict and special cases. Outside of these cases, it increases the data-size, even doubles the size in worst cases compared to the original, unprocessed data. In this paper, we will discuss modifications to RLE, with which we will only store the run for characters, that are actually compressible, getting rid of a lot of useless data like the runs of the characters, that are uncompressible in the first place. This will be achieved by storing the character first and the run second. Additionally we create a bit-list of 256 positions(one for every possible ASCII-character), in which we will store, if a specific (ASCII-)character is compressible(1) or not(0). Using this list, we can now say, if a character is compressible (store [the character]+[it's run]) or if it is not compressible (store [the character] only and the next character is NOT a run, but the following character instead). Using this list, we can also successfully decode the data(if the character is compressible, the next character is a run, if not compressible, the next character is a normal character). With that, we store runs only for characters, that are compressible in the first place. In fact, in the worst case scenario, the encoded data will create always just an overhead of the size of the bit-list itself. With an alphabet of 256 different characters(i.e. ASCII) it would be only a maximum of 32 bytes, no matter how big the original data was. [...]
Using a Big Data Database to Identify Pathogens in Protein Data Space
Venue: arXiv cs.DB 2015
Year: 2015

Current metagenomic analysis algorithms require significant computing resources, can report excessive false positives (type I errors), may miss organisms (type II errors / false negatives), or scale poorly on large datasets. This paper explores using big data database technologies to characterize very large metagenomic DNA sequences in protein space, with the ultimate goal of rapid pathogen identification in patient samples. Our approach uses the abilities of a big data databases to hold large sparse associative array representations of genetic data to extract statistical patterns about the data that can be used in a variety of ways to improve identification algorithms.
Int{é}gration d'une mesure d'ind{é}pendance pour la fusion d'informations
Venue: arXiv cs.AI 2015
Year: 2015

Many information sources are considered into data fusion in order to improve the decision in terms of uncertainty and imprecision. For each technique used for data fusion, the asumption on independance is usually made. We propose in this article an approach to take into acount an independance measure befor to make the combination of information in the context of the theory of belief functions.
System M: A Program Logic for Code Sandboxing and Identification
Venue: arXiv cs.CR 2015
Year: 2015

Security-sensitive applications that execute untrusted code often check the code's integrity by comparing its syntax to a known good value or sandbox the code to contain its effects. System M is a new program logic for reasoning about such security-sensitive applications. System M extends Hoare Type Theory (HTT) to trace safety properties and, additionally, contains two new reasoning principles. First, its type system internalizes logical equality, facilitating reasoning about applications that check code integrity. Second, a confinement rule assigns an effect type to a computation based solely on knowledge of the computation's sandbox. We prove the soundness of system M relative to a step-indexed trace-based semantic model. We illustrate both new reasoning principles of system M by verifying the main integrity property of the design of Memoir, a previously proposed trusted computing system for ensuring state continuity of isolated security-sensitive applications.
Joint Channel Direction Information Quantization For Spatially Correlated 3D MIMO Channels
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes a codebook for jointly quantizing channel direction information (CDI) of spatially correlated three-dimensional (3D) multi-input-multi-output (MIMO) channels. To reduce the dimension for quantizing the CDI of large antenna arrays, we introduce a special structure to the codewords by using Tucker decomposition to exploit the unique features of 3D MIMO channels. Specifically, the codeword consists of four parts each with low dimension individually targeting at a different type of information: statistical CDIs in horizontal direction and in vertical direction, statistical power coupling, and instantaneous CDI. The proposed codebook avoids the redundancy led by existing independent CDI quantization. Analytical results provide a sufficient condition on 3D MIMO channels to show that the proposed codebook can achieve the same quantization performance as the well-known rotated codebook applied to the global channel CDI, but with significant reduction in the required statistical channel information. Simulation results validate our analysis and demonstrate that the proposed joint CDI quantization provides substantial performance gain over independent CDI quantization.
A scalable architecture for distributed receive beamforming: analysis and experimental demonstration
Venue: arXiv cs.IT 2015
Year: 2015

We propose, analyze and demonstrate an architecture for scalable cooperative reception. In a cluster of N + 1 receive nodes, one node is designated as the final receiver, and the N other nodes act as amplify-and-forward relays which adapt their phases such that the relayed signals add up constructively at the designated receiver. This yields received SNR scaling linearly with N, while avoiding the linear increase in overhead incurred by a direct approach in which received signals are separately quantized and transmitted for centralized processing. By transforming the task of long-distance distributed receive beamforming into one of local distributed transmit beamforming, we can leverage a scalable one-bit feedback algorithm for phase synchronization. We show that time division between the long-distance and local links eliminates the need for explicit frequency synchronization. We provide an analytical framework, whose results closely match Monte Carlo simulations, to evaluate the impact of phase noise due to relaying delay on the performance of the one-bit feedback algorithm. Experimental results from our prototype implementation on software-defined radios demonstrate the expected gains in received signal strength despite significant oscillator drift, and are consistent with results from our analytical framework.
Filtered Channel Features for Pedestrian Detection
Venue: arXiv cs.CV 2015
Year: 2015

This paper starts from the observation that multiple top performing pedestrian detectors can be modelled by using an intermediate layer filtering low-level features in combination with a boosted decision forest. Based on this observation we propose a unifying framework and experimentally explore different filter families. We report extensive results enabling a systematic analysis. Using filtered channel features we obtain top performance on the challenging Caltech and KITTI datasets, while using only HOG+LUV as low-level features. When adding optical flow features we further improve detection quality and report the best known results on the Caltech dataset, reaching 93% recall at 1 FPPI.