OpenRaiser/Intern-Atlas huggingface dataset:
Node Repair for Distributed Storage Systems over Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

Distributed storage systems and associated storage codes can efficiently store a large amount of data while ensuring that data is retrievable in case of node failure. The study of such systems, particularly the design of storage codes over finite fields, assumes that the physical channel through which the nodes communicate is error-free. This is not always the case, for example, in a wireless storage system. We study the probability that a subpacket is repaired incorrectly during node repair in a distributed storage system, in which the nodes communicate over an AWGN or Rayleigh fading channels. The asymptotic probability (as SNR increases) that a node is repaired incorrectly is shown to be completely determined by the repair locality of the DSS and the symbol error rate of the wireless channel. Lastly, we propose some design criteria for physical layer coding in this scenario, and use it to compute optimally rotated QAM constellations for use in wireless distributed storage systems.
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
Venue: arXiv cs.CC 2014
Year: 2014

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan -- an assignment of tasks to authorized users -- such that all constraints are satisfied. The WSP is, in fact, the conservative Constraint Satisfaction Problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, NP-complete. It was observed by Wang and Li (2010) that the number k of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of WSP regarding parameter k. We take a more detailed look at the kernelization complexity of WSP(Γ) when Γ denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in Γ are regular: (1) We are able to reduce the number n of users to n' <= k. This entails a kernelization to size poly(k) for finite Γ, and, under mild technical conditions, to size poly(k+m) for infinite Γ, where m denotes the number of constraints. (2) Already WSP(R) for some R \in Γ allows no polynomial kernelization in k+m unless the polynomial hierarchy collapses.
A Study on the Sectors of Economy serviced by Pre-industry System Developers among companies in Metro Manila: A Tool for Business Reengineering
Venue: arXiv cs.CY 2014
Year: 2014

In the emergence of transformative global economy, information system has became a necessity in businesses to obtain organizations operational excellence, adaptation to new business models, improved decision making and providing exceptional customer service, and eventual competitive advantage of the enterprise setting while keeping business alliances. This paper presents sectors of economy serviced by the pre-industry developers, explores the evolution of computer-based information system designed and developed by pre-industry system developers, and examine the effects of an information system in business to countervail indentified recurring problems. Nineteen of forty-six identified sectors of economy falls in the categories of primary, secondary, tertiary, quarternary and quinary were the recipient of computer-based system designed and developed. There have been several effects of computer-based systems to organizations, including the implied relevance to their business processes, continuum process improvement, business process reengineering, business driver and facilitator, and customer satisfaction.
Stream quantiles via maximal entropy histograms
Venue: arXiv cs.DS 2014
Year: 2014

We address the problem of estimating the running quantile of a data stream when the memory for storing observations is limited. We (i) highlight the limitations of approaches previously described in the literature which make them unsuitable for non-stationary streams, (ii) describe a novel principle for the utilization of the available storage space, and (iii) introduce two novel algorithms which exploit the proposed principle. Experiments on three large real-world data sets demonstrate that the proposed methods vastly outperform the existing alternatives.
Estimating the pattern frequency spectrum inside the browser
Venue: arXiv cs.DB 2014
Year: 2014

We present a browser application for estimating the number of frequent patterns, in particular itemsets, as well as the pattern frequency spectrum. The pattern frequency spectrum is defined as the function that shows for every value of the frequency threshold $σ$ the number of patterns that are frequent in a given dataset. Our demo implements a recent algorithm proposed by the authors for finding the spectrum. The demo is 100% JavaScript, and runs in all modern browsers. We observe that modern JavaScript engines can deliver performance that makes it viable to run non-trivial data analysis algorithms in browser applications.
An Analysis of Publication Venues for Automatic Differentiation Research
Venue: arXiv cs.DL 2014
Year: 2014

We present the results of our analysis of publication venues for papers on automatic differentiation (AD), covering academic journals and conference proceedings. Our data are collected from the AD publications database maintained by the autodiff.org community website. The database is purpose-built for the AD field and is expanding via submissions by AD researchers. Therefore, it provides a relatively noise-free list of publications relating to the field. However, it does include noise in the form of variant spellings of journal and conference names. We handle this by manually correcting and merging these variants under the official names of corresponding venues. We also share the raw data we get after these corrections.
A Semidefinite Programming Based Search Strategy for Feature Selection with Mutual Information Measure
Venue: arXiv cs.LG 2014
Year: 2014

Feature subset selection, as a special case of the general subset selection problem, has been the topic of a considerable number of studies due to the growing importance of data-mining applications. In the feature subset selection problem there are two main issues that need to be addressed: (i) Finding an appropriate measure function than can be fairly fast and robustly computed for high-dimensional data. (ii) A search strategy to optimize the measure over the subset space in a reasonable amount of time. In this article mutual information between features and class labels is considered to be the measure function. Two series expansions for mutual information are proposed, and it is shown that most heuristic criteria suggested in the literature are truncated approximations of these expansions. It is well-known that searching the whole subset space is an NP-hard problem. Here, instead of the conventional sequential search algorithms, we suggest a parallel search strategy based on semidefinite programming (SDP) that can search through the subset space in polynomial time. By exploiting the similarities between the proposed algorithm and an instance of the maximum-cut problem in graph theory, the approximation ratio of this algorithm is derived and is compared with the approximation ratio of the backward elimination method. The experiments show that it can be misleading to judge the quality of a measure solely based on the classification accuracy, without taking the effect of the non-optimum search strategy into account.
An Analysis on Selection for High-Resolution Approximations in Many-Objective Optimization
Venue: arXiv cs.NE 2014
Year: 2014

This work studies the behavior of three elitist multi- and many-objective evolutionary algorithms generating a high-resolution approximation of the Pareto optimal set. Several search-assessment indicators are defined to trace the dynamics of survival selection and measure the ability to simultaneously keep optimal solutions and discover new ones under different population sizes, set as a fraction of the size of the Pareto optimal set.
Optimized Compressed Sensing Matrix Design for Noisy Communication Channels
Venue: arXiv cs.IT 2014
Year: 2014

We investigate a power-constrained sensing matrix design problem for a compressed sensing framework. We adopt a mean square error (MSE) performance criterion for sparse source reconstruction in a system where the source-to-sensor channel and the sensor-to-decoder communication channel are noisy. Our proposed sensing matrix design procedure relies upon minimizing a lower-bound on the MSE. Under certain conditions, we derive closed-form solutions to the optimization problem. Through numerical experiments, by applying practical sparse reconstruction algorithms, we show the strength of the proposed scheme by comparing it with other relevant methods. We discuss the computational complexity of our design method, and develop an equivalent stochastic optimization method to the problem of interest that can be solved approximately with a significantly less computational burden. We illustrate that the low-complexity method still outperforms the popular competing methods.
Semi-supervised Classification for Natural Language Processing
Venue: arXiv cs.CL 2014
Year: 2014

Semi-supervised classification is an interesting idea where classification models are learned from both labeled and unlabeled data. It has several advantages over supervised classification in natural language processing domain. For instance, supervised classification exploits only labeled data that are expensive, often difficult to get, inadequate in quantity, and require human experts for annotation. On the other hand, unlabeled data are inexpensive and abundant. Despite the fact that many factors limit the wide-spread use of semi-supervised classification, it has become popular since its level of performance is empirically as good as supervised classification. This study explores the possibilities and achievements as well as complexity and limitations of semi-supervised classification for several natural langue processing tasks like parsing, biomedical information processing, text classification, and summarization.
Missing data in multiplex networks: a preliminary study
Venue: arXiv cs.SI 2014
Year: 2014

A basic problem in the analysis of social networks is missing data. When a network model does not accurately capture all the actors or relationships in the social system under study, measures computed on the network and ultimately the final outcomes of the analysis can be severely distorted. For this reason, researchers in social network analysis have characterised the impact of different types of missing data on existing network measures. Recently a lot of attention has been devoted to the study of multiple-network systems, e.g., multiplex networks. In these systems missing data has an even more significant impact on the outcomes of the analyses. However, to the best of our knowledge, no study has focused on this problem yet. This work is a first step in the direction of understanding the impact of missing data in multiple networks. We first discuss the main reasons for missingness in these systems, then we explore the relation between various types of missing information and their effect on network properties. We provide initial experimental evidence based on both real and synthetic data.
Similarity-based matching meets Malware Diversity
Venue: arXiv cs.CR 2014
Year: 2014

Similarity metrics, e.g., signatures as used by anti-virus products, are the dominant technique to detect if a given binary is malware. The underlying assumption of this approach is that all instances of a malware (or even malware family) will be similar to each other. Software diversification is a probabilistic technique that uses code and data randomization and expressiveness in the target instruction set to generate large amounts of functionally equivalent but different binaries. Malware diversity builds on software diversity and ensures that any two diversified instances of the same malware have low similarity (according to a set of similarity metrics). An LLVM-based prototype implementation diversifies both code and data of binaries and our evaluation shows that signatures based on similarity only match one or few instances in a pool of diversified binaries generated from the same source code.
Audio Surveillance: a Systematic Review
Venue: arXiv cs.SD 2014
Year: 2014

Despite surveillance systems are becoming increasingly ubiquitous in our living environment, automated surveillance, currently based on video sensory modality and machine intelligence, lacks most of the time the robustness and reliability required in several real applications. To tackle this issue, audio sensory devices have been taken into account, both alone or in combination with video, giving birth, in the last decade, to a considerable amount of research. In this paper audio-based automated surveillance methods are organized into a comprehensive survey: a general taxonomy, inspired by the more widespread video surveillance field, is proposed in order to systematically describe the methods covering background subtraction, event classification, object tracking and situation analysis. For each of these tasks, all the significant works are reviewed, detailing their pros and cons and the context for which they have been proposed. Moreover, a specific section is devoted to audio features, discussing their expressiveness and their employment in the above described tasks. Differently, from other surveys on audio processing and analysis, the present one is specifically targeted to automated surveillance, highlighting the target applications of each described methods and providing the reader tables and schemes useful to retrieve the most suited algorithms for a specific requirement.
How good is the Shapley value-based approach to the influence maximization problem?
Venue: arXiv cs.AI 2014
Year: 2014

The Shapley value has been recently advocated as a method to choose the seed nodes for the process of information diffusion. Intuitively, since the Shapley value evaluates the average marginal contribution of a player to the coalitional game, it can be used in the network context to evaluate the marginal contribution of a node in the process of information diffusion given various groups of already 'infected' nodes. Although the above direction of research seems promising, the current liter- ature is missing a throughout assessment of its performance. The aim of this work is to provide such an assessment of the existing Shapley value-based approaches to information diffusion.
Distributed Reception with Spatial Multiplexing: MIMO Systems for the Internet of Things
Venue: arXiv cs.IT 2014
Year: 2014

The Internet of things (IoT) holds much commercial potential and could facilitate distributed multiple-input multiple-output (MIMO) communication in future systems. We study a distributed reception scenario in which a transmitter equipped with multiple antennas sends multiple streams via spatial multiplexing to a large number of geographically separated single antenna receive nodes. The receive nodes then quantize their received signals and forward the quantized received signals to a receive fusion center. With global channel knowledge and forwarded quantized information from the receive nodes, the fusion center attempts to decode the transmitted symbols. We assume the transmit vector consists of phase shift keying (PSK) constellation points, and each receive node quantizes its received signal with one bit for each of the real and imaginary parts of the signal to minimize the transmission overhead between the receive nodes and the fusion center. Fusing this data is a non-trivial problem because the receive nodes cannot decode the transmitted symbols before quantization. Instead, each receive node processes a single quantity, i.e., the received signal, regardless of the number of transmitted symbols. We develop an optimal maximum likelihood (ML) receiver and a low-complexity zero-forcing (ZF)-type receiver at the fusion center. Despite its suboptimality, the ZF-type receiver is simple to implement and shows comparable performance with the ML receiver in the low signal-to-noise ratio (SNR) regime but experiences an error rate floor at high SNR. It is shown that this error floor can be overcome by increasing the number of receive nodes. Hence, the ZF-type receiver would be a practical solution for distributed reception with spatial multiplexing in the era of the IoT where we can easily have a large number of receive nodes.
Is your EPL attractive? Classification of publications through download statistics
Venue: arXiv cs.DL 2014
Year: 2014

Here we consider the download statistics of EPL publications. We find that papers in the journal are characterised by fast accumulations of downloads during the first couple of months after publication, followed by slower rates thereafter, behaviour which can be represented by a model with predictive power. We also find that individual papers can be classified in various ways, allowing us to compare categories for open-access and non-open-access papers. For example, for the latter publications, which comprise the bulk of EPL papers, a small proportion (2%) display intense bursts of download activity, possibly following an extended period of less remarkable behaviour. About 18% have an especially high degree of attractiveness over and above what is typical for the journal. One can also classify the ageing of attractiveness by examining download half-lives. Approximately 18% have strong interest initially, waning in time. A further 20% exhibit "delayed recognition" with relatively late spurs in download activity. Although open-access papers enjoy more downloads on average, the proportions falling into each category are similar.
A network-dependent rewarding system: proof-of-mining
Venue: arXiv cs.CY 2014
Year: 2014

A soft control of the network activity through varying reward in a proof-of-work (PoW) cryptocurrency is reported. Rewards are the necessity to incent the contributors activities (i.e., mining) in order to maintain the PoW network. Contrary to constant rewarding in a certain period implemented in most of cryptocurrency, such as bitcoin, we propose a network-dependent rewarding model system, primarily including two phases: 1) activities encouraging phase in which higher rewards are issued at higher network activities; and 2) discouraging further increase of activities by reducing rewards. The advantages of this system include 1) fair distribution of rewards among a variety of contributors, and 2) enforcing a limit to the network activity and hence the cost of maintaining the PoW network. This mechanism requires network contributors to show their participation in order to earn maximum rewards, i.e., proof-of-mining.
An ECG-on-Chip for Wearable Cardiac Monitoring Devices
Venue: arXiv cs.AR 2014
Year: 2014

This paper describes a highly integrated, low power chip solution for ECG signal processing in wearable devices. The chip contains an instrumentation amplifier with programmable gain, a band-pass filter, a 12-bit SAR ADC, a novel QRS detector, 8K on-chip SRAM, and relevant control circuitry and CPU interfaces. The analog front end circuits accurately senses and digitizes the raw ECG signal, which is then filtered to extract the QRS. The sampling frequency used is 256 Hz. ECG samples are buffered locally on an asynchronous FIFO and is read out using a faster clock, as and when it is required by the host CPU via an SPI interface. The chip was designed and implemented in 0.35um standard CMOS process. The analog core operates at 1V while the digital circuits and SRAM operate at 3.3V. The chip total core area is 5.74 mm^2 and consumes 9.6uW. Small size and low power consumption make this design suitable for usage in wearable heart monitoring devices.
Efficient high-quality motion planning by fast all-pairs r-nearest-neighbors
Venue: arXiv cs.RO 2014
Year: 2014

Sampling-based motion-planning algorithms typically rely on nearest-neighbor (NN) queries when constructing a roadmap. Recent results suggest that in various settings NN queries may be the computational bottleneck of such algorithms. Moreover, in several asymptotically-optimal algorithms these NN queries are of a specific form: Given a set of points and a radius r report all pairs of points whose distance is at most r. This calls for an application-specific NN data structure tailored to efficiently answering this type of queries. Randomly transformed grids (RTG) were recently proposed by Aiger et al. as a tool to answer such queries and have been shown to outperform common implementations of NN data structures in this context. In this work we employ RTG for sampling-based motion-planning algorithms and describe an efficient implementation of the approach. We show that for motion-planning, RTG allow for faster convergence to high-quality solutions when compared with existing NN data structures. Additionally, RTG enable significantly shorter construction times for batched-PRM variants; specifically, we demonstrate a speedup by a factor of two to three for some scenarios.
The Maximum k-Differential Coloring Problem
Venue: arXiv cs.DM 2014
Year: 2014

Given an $n$-vertex graph $G$ and two positive integers $d,k \in \mathbb{N}$, the ($d,kn$)-differential coloring problem asks for a coloring of the vertices of $G$ (if one exists) with distinct numbers from 1 to $kn$ (treated as \emph{colors}), such that the minimum difference between the two colors of any adjacent vertices is at least $d$. While it was known that the problem of determining whether a general graph is ($2,n$)-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit ($2,kn$)-differential colorings. For practical reasons, we consider also color ranges larger than $n$, i.e., $k > 1$. We show that it is NP-complete to determine whether a graph admits a ($3,2n$)-differential coloring. The same negative result holds for the ($\lfloor 2n/3 \rfloor, 2n$-differential coloring problem, even in the case where the input graph is planar.
Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes
Venue: arXiv cs.IT 2014
Year: 2014

We give a polynomial time attack on the McEliece public key cryptosystem based on subcodes of algebraic geometry (AG) codes. The proposed attack reposes on the distinguishability of such codes from random codes using the Schur product. Wieschebrink treated the genus zero case a few years ago but his approach cannot be extent straightforwardly to other genera. We address this problem by introducing and using a new notion, which we call the t-closure of a code.
MetaCache: Efficient Metadata Caching in Linux file system
Venue: arXiv cs.SY 2014
Year: 2014

Nowadays, Linux file systems have to manage millions of tiny files for different applications, and face with higher metadata operations. So how to provide such high metadata performance with such enormous number of files and large scale directories is a big challenge for Linux file system. We viewed that metadata lookup operations dominate metadata workload and incur low metadata performance. In this paper, we present a metadata cache to accelerate metadata access for Linux file system. Through this optimization, the Linux file system (such as EXT2, EXT4, BTRFS, etc.) can gain improvement in read rates as well as write rates.