OpenRaiser/Intern-Atlas huggingface dataset:
Testing probability distributions underlying aggregated data
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and cumulative dual access models, in which the algorithm $A$ can both sample from $D$ and respectively, for any $i\in[n]$, - query the probability mass $D(i)$ (query access); or - get the total mass of $\{1,\dots,i\}$, i.e. $\sum_{j=1}^i D(j)$ (cumulative access) These two models, by generalizing the previously studied sampling and query oracle models, allow us to bypass the strong lower bounds established for a number of problems in these settings, while capturing several interesting aspects of these problems -- and providing new insight on the limitations of the models. Finally, we show that while the testing algorithms can be in most cases strictly more efficient, some tasks remain hard even with this additional power.
An Empirical Study on Software Defect Prediction with a Simplified Metric Set
Venue: arXiv cs.SE 2014
Year: 2014

Software defect prediction plays a crucial role in estimating the most defect-prone components of software, and a large number of studies have pursued improving prediction accuracy within a project or across projects. However, the rules for making an appropriate decision between within- and cross-project defect prediction when available historical data are insufficient remain unclear. The objective of this work is to validate the feasibility of the predictor built with a simplified metric set for software defect prediction in different scenarios, and to investigate practical guidelines for the choice of training data, classifier and metric subset of a given project. First, based on six typical classifiers, we constructed three types of predictors using the size of software metric set in three scenarios. Then, we validated the acceptable performance of the predictor based on Top-k metrics in terms of statistical methods. Finally, we attempted to minimize the Top-k metric subset by removing redundant metrics, and we tested the stability of such a minimum metric subset with one-way ANOVA tests. The experimental results indicate that (1) the choice of training data should depend on the specific requirement of prediction accuracy; (2) the predictor built with a simplified metric set works well and is very useful in case limited resources are supplied; (3) simple classifiers (e.g., Naive Bayes) also tend to perform well when using a simplified metric set for defect prediction; and (4) in several cases, the minimum metric subset can be identified to facilitate the procedure of general defect prediction with acceptable loss of prediction precision in practice. The guideline for choosing a suitable simplified metric set in different scenarios is presented in Table 12.
Representative Sets of Product Families
Venue: arXiv cs.DS 2014
Year: 2014

A subfamily ${\cal F}'$ of a set family ${\cal F}$ is said to $q$-{\em represent} ${\cal F}$ if for every $A \in {\cal F}$ and $B$ of size $q$ such that $A \cap B = \emptyset$ there exists a set $A' \in {\cal F}'$ such that $A' \cap B = \emptyset$. In this paper, we consider the efficient computation of $q$-representative sets for {\em product} families ${\cal F}$. A family ${\cal F}$ is a product family if there exist families ${\cal A}$ and ${\cal B}$ such that ${\cal F} = \{A \cup B~:~A \in {\cal A}, B \in {\cal B}, A \cap B = \emptyset\}$. Our main technical contribution is an algorithm which given ${\cal A}$, ${\cal B}$ and $q$ computes a $q$-representative family ${\cal F}'$ of ${\cal F}$. The running time of our algorithm is sublinear in $|{\cal F}|$ for many choices of ${\cal A}$, ${\cal B}$ and $q$ which occur naturally in several dynamic programming algorithms. We also give an algorithm for the computation of $q$-representative sets for product families ${\cal F}$ in the more general setting where $q$-representation also involves independence in a matroid in addition to disjointness. This algorithm considerably outperforms the naive approach where one first computes ${\cal F}$ from ${\cal A}$ and ${\cal B}$, and then computes the $q$-representative family ${\cal F}'$ from ${\cal F}$. We give two applications of our new algorithms for computing $q$-representative sets for product families. The first is a $3.8408^{k}n^{O(1)}$ deterministic algorithm for the Multilinear Monomial Detection ($k$-MlD) problem. The second is a significant improvement of deterministic dynamic programming algorithms for "connectivity problems" on graphs of bounded treewidth.
Analysis of Personalized Information Service System for Digital Libraries
Venue: arXiv cs.DL 2014
Year: 2014

Along with the rapid development of digital library, digital library of the third generation, taking the main characteristics of the personalized service, has already become the mainstream today. This article first analyzes the concept and characteristics of digital library, then elaborates the inevitability of personalized service as well as the necessity of its development and based on the Propose of establishing interested knowledge-base, enumerates several ways of personalized service, at last according to individualized service, this paper proposes the model of "learningoriented individual digital library" and prospects the trends of digital library.
Dimensionality reduction with subgaussian matrices: a unified theory
Venue: arXiv cs.IT 2014
Year: 2014

We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson-Lindenstrauss type results obtained earlier for specific data sets. In particular, we recover and, in several cases, improve results for sets of sparse and structured sparse vectors, low-rank matrices and tensors, and smooth manifolds. In addition, we establish a new Johnson-Lindenstrauss embedding for data sets taking the form of an infinite union of subspaces of a Hilbert space.
Application of the Ring Theory in the Segmentation of Digital Images
Venue: arXiv cs.CV 2014
Year: 2014

Ring theory is one of the branches of the abstract algebra that has been broadly used in images. However, ring theory has not been very related with image segmentation. In this paper, we propose a new index of similarity among images using Zn rings and the entropy function. This new index was applied as a new stopping criterion to the Mean Shift Iterative Algorithm with the goal to reach a better segmentation. An analysis on the performance of the algorithm with this new stopping criterion is carried out. The obtained results proved that the new index is a suitable tool to compare images.
Generalized Area Spectral Efficiency: An Effective Performance Metric for Green Wireless Communications
Venue: arXiv cs.NI 2014
Year: 2014

Area spectral efficiency (ASE) was introduced as a metric to quantify the spectral utilization efficiency of cellular systems. Unlike other performance metrics, ASE takes into account the spatial property of cellular systems. In this paper, we generalize the concept of ASE to study arbitrary wireless transmissions. Specifically, we introduce the notion of affected area to characterize the spatial property of arbitrary wireless transmissions. Based on the definition of affected area, we define the performance metric, generalized area spectral efficiency (GASE), to quantify the spatial spectral utilization efficiency as well as the greenness of wireless transmissions. After illustrating its evaluation for point-to-point transmission, we analyze the GASE performance of several different transmission scenarios, including dual-hop relay transmission, three-node cooperative relay transmission and underlay cognitive radio transmission. We derive closed-form expressions for the GASE metric of each transmission scenario under Rayleigh fading environment whenever possible. Through mathematical analysis and numerical examples, we show that the GASE metric provides a new perspective on the design and optimization of wireless transmissions, especially on the transmitting power selection. We also show that introducing relay nodes can greatly improve the spatial utilization efficiency of wireless systems. We illustrate that the GASE metric can help optimize the deployment of underlay cognitive radio systems.
Energy-efficient algorithms for non-preemptive speed-scaling
Venue: arXiv cs.DS 2014
Year: 2014

We improve complexity bounds for energy-efficient speed scheduling problems for both the single processor and multi-processor cases. Energy conservation has become a major concern, so revisiting traditional scheduling problems to take into account the energy consumption has been part of the agenda of the scheduling community for the past few years. We consider the energy minimizing speed scaling problem introduced by Yao et al. where we wish to schedule a set of jobs, each with a release date, deadline and work volume, on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the $α$th power of its speed. The objective is then to find a feasible schedule which minimizes the total energy used. We show that in the setting with an arbitrary number of processors where all work volumes are equal, there is a $2(1+\varepsilon)(5(1+\varepsilon))^{α-1}\tilde{B}_α=O_α(1)$ approximation algorithm, where $\tilde{B}_α$ is the generalized Bell number. This is the first constant factor algorithm for this problem. This algorithm extends to general unequal processor-dependent work volumes, up to losing a factor of $(\frac{(1+r)r}{2})^α$ in the approximation, where $r$ is the maximum ratio between two work volumes. We then show this latter problem is APX-hard, even in the special case when all release dates and deadlines are equal and $r$ is 4. In the single processor case, we introduce a new linear programming formulation of speed scaling and prove that its integrality gap is at most $12^{α-1}$. As a corollary, we obtain a $(12(1+\varepsilon))^{α-1}$ approximation algorithm where there is a single processor, improving on the previous best bound of $2^{α-1}(1+\varepsilon)^α\tilde{B}_α$ when $α\ge 25$.
Fine-grained Patches for Java Software Upgrades
Venue: arXiv cs.SE 2014
Year: 2014

We present a novel methodology for deriving fine-grained patches of Java software. We consider an abstract-syntax tree (AST) representation of Java classes compiled to the Java Virtual Machine (JVM) format, and a difference analysis over the AST representation to derive patches. The AST representation defines an appropriate abstraction level for analyzing differences, yielding compact patches that correlate modularly to actual source code changes. The approach contrasts to other common, coarse-grained approaches, like plain binary differences, which may easily lead to disproportionately large patches. We present the main traits of the methodology, a prototype tool called aspa that implements it, and a case-study analysis on the use of aspa to derive patches for the Java 2 SE API. The case-study results illustrate that aspa patches have a significantly smaller size than patches derived by binary differencing tools.
Learning Natural Coding Conventions
Venue: arXiv cs.SE 2014
Year: 2014

Every programmer has a characteristic style, ranging from preferences about identifier naming to preferences about object relationships and design patterns. Coding conventions define a consistent syntactic style, fostering readability and hence maintainability. When collaborating, programmers strive to obey a project's coding conventions. However, one third of reviews of changes contain feedback about coding conventions, indicating that programmers do not always follow them and that project members care deeply about adherence. Unfortunately, programmers are often unaware of coding conventions because inferring them requires a global view, one that aggregates the many local decisions programmers make and identifies emergent consensus on style. We present NATURALIZE, a framework that learns the style of a codebase, and suggests revisions to improve stylistic consistency. NATURALIZE builds on recent work in applying statistical natural language processing to source code. We apply NATURALIZE to suggest natural identifier names and formatting conventions. We present four tools focused on ensuring natural code during development and release management, including code review. NATURALIZE achieves 94% accuracy in its top suggestions for identifier names and can even transfer knowledge about conventions across projects, leveraging a corpus of 10,968 open source projects. We used NATURALIZE to generate 18 patches for 5 open source projects: 14 were accepted.
Distributed Storage over Unidirectional Ring Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study distributed storage problems over unidirectional ring networks, whose storage nodes form a directed ring and data is transmitted along the same direction. The original data is distributed to store on these nodes. Each user can connect one and only one storage node to download the total data. A lower bound on the reconstructing bandwidth to recover the original data for each user is proposed, and it is achievable for arbitrary parameters. If a distributed storage scheme can achieve this lower bound with equality for every user, we say it an optimal reconstructing distributed storage scheme (ORDSS). Furthermore, the repair problem for a failed storage node in ORDSSes is under consideration and a tight lower bound on the repair bandwidth is obtained. In particular, we indicate the fact that for any ORDSS, every storage node can be repaired with repair bandwidth achieving the lower bound with equality. In addition, we present two constructions for ORDSSes of arbitrary parameters, called MDS construction and ED construction, respectively. Particularly, ED construction, by using the concept of Euclidean division, is more efficient by our analysis in detail.
On the properties of $α$-unchaining single linkage hierarchical clustering
Venue: arXiv cs.LG 2014
Year: 2014

In the election of a hierarchical clustering method, theoretic properties may give some insight to determine which method is the most suitable to treat a clustering problem. Herein, we study some basic properties of two hierarchical clustering methods: $α$-unchaining single linkage or $SL(α)$ and a modified version of this one, $SL^*(α)$. We compare the results with the properties satisfied by the classical linkage-based hierarchical clustering methods.
Communication and Interference Coordination
Venue: arXiv cs.IT 2014
Year: 2014

We study the problem of controlling the interference created to an external observer by a communication processes. We model the interference in terms of its type (empirical distribution), and we analyze the consequences of placing constraints on the admissible type. Considering a single interfering link, we characterize the communication-interference capacity region. Then, we look at a scenario where the interference is jointly created by two users allowed to coordinate their actions prior to transmission. In this case, the trade-off involves communication and interference as well as coordination. We establish an achievable communication-interference region and show that efficiency is significantly improved by coordination.
An Elementary Completeness Proof for Secure Two-Party Computation Primitives
Venue: arXiv cs.CR 2014
Year: 2014

In the secure two-party computation problem, two parties wish to compute a (possibly randomized) function of their inputs via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own input and output. For semi-honest parties and information-theoretic security guarantees, it is well-known that, if only noiseless communication is available, only a limited set of functions can be securely computed; however, if interaction is also allowed over general communication primitives (multi-input/output channels), there are "complete" primitives that enable any function to be securely computed. The general set of complete primitives was characterized recently by Maji, Prabhakaran, and Rosulek leveraging an earlier specialized characterization by Kilian. Our contribution in this paper is a simple, self-contained, alternative derivation using elementary information-theoretic tools.
A Comparative Study of Machine Learning Methods for Verbal Autopsy Text Classification
Venue: arXiv cs.CL 2014
Year: 2014

A Verbal Autopsy is the record of an interview about the circumstances of an uncertified death. In developing countries, if a death occurs away from health facilities, a field-worker interviews a relative of the deceased about the circumstances of the death; this Verbal Autopsy can be reviewed off-site. We report on a comparative study of the processes involved in Text Classification applied to classifying Cause of Death: feature value representation; machine learning classification algorithms; and feature reduction strategies in order to identify the suitable approaches applicable to the classification of Verbal Autopsy text. We demonstrate that normalised term frequency and the standard TFiDF achieve comparable performance across a number of classifiers. The results also show Support Vector Machine is superior to other classification algorithms employed in this research. Finally, we demonstrate the effectiveness of employing a "locally-semi-supervised" feature reduction strategy in order to increase performance accuracy.
Compressed bitmap indexes: beyond unions and intersections
Venue: arXiv cs.DB 2014
Year: 2014

Compressed bitmap indexes are used to speed up simple aggregate queries in databases. Indeed, set operations like intersections, unions and complements can be represented as logical operations (AND,OR,NOT) that are ideally suited for bitmaps. However, it is less obvious how to apply bitmaps to more advanced queries. For example, we might seek products in a store that meet some, but maybe not all, criteria. Such threshold queries generalize intersections and unions; they are often used in information-retrieval and data-mining applications. We introduce new algorithms that are sometimes three orders of magnitude faster than a naive approach. Our work shows that bitmap indexes are more broadly applicable than is commonly believed.
Normalized Volume of Hyperball in Complex Grassmann Manifold and Its Application in Large-Scale MU-MIMO Communication Systems
Venue: arXiv cs.IT 2014
Year: 2014

This paper provides a solution to a critical issue in large-scale Multi-User Multiple-Input Multiple-Output (MU-MIMO) communication systems: how to estimate the Signal-to-Interference-plus-Noise-Ratios (SINRs) and their expectations in MU-MIMO mode at the Base Station (BS) side when only the Channel Quality Information (CQI) in Single-User MIMO (SU-MIMO) mode and non-ideal Channel State Information (CSI) are known? A solution to this problem would be very beneficial for the BS to predict the capacity of MU-MIMO and choose the proper modulation and channel coding for MU-MIMO. To that end, this paper derives a normalized volume formula of a hyperball based on the probability density function of the canonical angle between any two points in a complex Grassmann manifold, and shows that this formula provides a solution to the aforementioned issue. It enables the capability of a BS to predict the capacity loss due to non-ideal CSI, group users in MU-MIMO mode, choose the proper modulation and channel coding, and adaptively switch between SU-MIMO and MU-MIMO modes, as well as between Conjugate Beamforming (CB) and Zero-Forcing (ZF) precoding. Numerical results are provided to verify the validity and accuracy of the solution.
Playing games in an uncertain world
Venue: arXiv cs.GT 2014
Year: 2014

Traditional game theory assumes that the players in the game are aware of the rules of the game. However, in practice, often the players are unaware or have only partial knowledge about the game they are playing. They may also have knowledge that other players have only partial knowledge of the game they are playing, which they can try to exploit. We present a novel mathematical formulation of such games. We make use of Kripke semantics, which are a way to keep track of what different players know and do not know about the world. We propose a notion of equilibrium for such games, and show that equilibrium always exists.
PROOF as a Service on the Cloud: a Virtual Analysis Facility based on the CernVM ecosystem
Venue: arXiv cs.DC 2014
Year: 2014

PROOF, the Parallel ROOT Facility, is a ROOT-based framework which enables interactive parallelism for event-based tasks on a cluster of computing nodes. Although PROOF can be used simply from within a ROOT session with no additional requirements, deploying and configuring a PROOF cluster used to be not as straightforward. Recently great efforts have been spent to make the provisioning of generic PROOF analysis facilities with zero configuration, with the added advantages of positively affecting both stability and scalability, making the deployment operations feasible even for the end user. Since a growing amount of large-scale computing resources are nowadays made available by Cloud providers in a virtualized form, we have developed the Virtual PROOF-based Analysis Facility: a cluster appliance combining the solid CernVM ecosystem and PoD (PROOF on Demand), ready to be deployed on the Cloud and leveraging some peculiar Cloud features such as elasticity. We will show how this approach is effective both for sysadmins, who will have little or no configuration to do to run it on their Clouds, and for the end users, who are ultimately in full control of their PROOF cluster and can even easily restart it by themselves in the unfortunate event of a major failure. We will also show how elasticity leads to a more optimal and uniform usage of Cloud resources.
A Survey on Semi-Supervised Learning Techniques
Venue: arXiv cs.LG 2014
Year: 2014

Semisupervised learning is a learning standard which deals with the study of how computers and natural systems such as human beings acquire knowledge in the presence of both labeled and unlabeled data. Semisupervised learning based methods are preferred when compared to the supervised and unsupervised learning because of the improved performance shown by the semisupervised approaches in the presence of large volumes of data. Labels are very hard to attain while unlabeled data are surplus, therefore semisupervised learning is a noble indication to shrink human labor and improve accuracy. There has been a large spectrum of ideas on semisupervised learning. In this paper we bring out some of the key approaches for semisupervised learning.
Concept of Feedback in Future Computing Models to Cloud Systems
Venue: arXiv cs.DC 2014
Year: 2014

Currently, it is urgent to ensure QoS in distributed computing systems. This became especially important to the development and spread of cloud services. Big data structures become heavily distributed. Necessary to consider the communication channels and data transmission systems and virtualization and scalability in future design of computational models in problems of designing cloud systems, evaluating the effectiveness of the algorithms, the assessment of economic performance data centers. Requires not only the monitoring of data flows and computing resources, but also the operational management of these resources to QoS provide. Such a tool may be just the introduction of feedback in computational models. The article presents the main dynamic model with feedback as a basis for a new model of distributed computing processes. The research results are presented here. Formulated in this work can be used for other complex tasks - estimation of structural complexity of distributed databases, evaluation of dynamic characteristics of systems operating in the hybrid cloud, etc.