OpenRaiser/Intern-Atlas huggingface dataset:
Fault Localization Using Textual Similarities
Venue: arXiv cs.SE 2012
Year: 2012

Maintenance is a dominant component of software cost, and localizing reported defects is a significant component of maintenance. We propose a scalable approach that leverages the natural language present in both defect reports and source code to identify files that are potentially related to the defect in question. Our technique is language-independent and does not require test cases. The approach represents reports and code as separate structured documents and ranks source files based on a document similarity metric that leverages inter-document relationships. We evaluate the fault-localization accuracy of our method against both lightweight baseline techniques and also reported results from state-of-the-art tools. In an empirical evaluation of 5345 historical defects from programs totaling 6.5 million lines of code, our approach reduced the number of files inspected per defect by over 91%. Additionally, we qualitatively and quantitatively examine the utility of the textual and surface features used by our approach.
Optimal Transmission Policy for Cooperative Transmission with Energy Harvesting and Battery Operated Sensor Nodes
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider a scenario where one energy harvesting and one battery operated sensor cooperatively transmit a common message to a distant base station. The goal is to find the jointly optimal transmission (power allocation) policy which maximizes the total throughput for a given deadline. First, we address the case in which the storage capacity of the energy harvesting sensor is infinite. In this context, we identify the necessary conditions for such optimal transmission policy. On their basis, we first show that the problem is convex. Then we go one step beyond and prove that (i) the optimal power allocation for the energy harvesting sensor can be computed independently; and (ii) it unequivocally determines (and allows to compute) that of the battery operated one. Finally, we generalize the analysis for the case of finite storage capacity. Performance is assessed by means of computer simulations. Particular attention is paid to the impact of finite storage capacity and long-term battery degradation on the achievable throughput.
Active Tile Self-assembly, Self-similar Structures and Recursion
Venue: arXiv cs.ET 2012
Year: 2012

We present an active tile assembly model which extends Winfree's abstract tile assembly model to tiles that are capable of transmitting and receiving binding site activation signals. In addition, we introduce a mathematical framework to address self-similarity and recursion within the model. The model is applied to show a recursive assembly of an archetypal self-similar aperiodic tiling known as the L-shape tiling.
Context-Awareness for Service Oriented Systems
Venue: arXiv cs.SE 2012
Year: 2012

Today, service oriented systems need to be enhanced to sense and react to users context in order to provide a better user experience. To meet this requirement, Context-Aware Services (CAS) have emerged as an underling design and development paradigm for the development of context-aware systems. The fundamental challenges for such systems development are context-awareness management and service adaptation to the users context. To cope with such requirements, we propose a well designed architecture, named ACAS, to support the development of Context-Aware Service Oriented Systems (CASOS). This architecture relies on a set of context-awareness and CAS specifications and metamodels to enhance a core service, in service oriented systems, to be context-aware. This enhancement is fulfilled by the Aspect Adaptations Weaver (A2W) which, based on the Aspect Paradigm (AP) concepts, considers the services adaptations as aspects.
The Search for the Laws of Automatic Random Testing
Venue: arXiv cs.SE 2012
Year: 2012

Can one estimate the number of remaining faults in a software system? A credible estimation technique would be immensely useful to project managers as well as customers. It would also be of theoretical interest, as a general law of software engineering. We investigate possible answers in the context of automated random testing, a method that is increasingly accepted as an effective way to discover faults. Our experimental results, derived from best-fit analysis of a variety of mathematical functions, based on a large number of automated tests of library code equipped with automated oracles in the form of contracts, suggest a poly-logarithmic law. Although further confirmation remains necessary on different code bases and testing techniques, we argue that understanding the laws of testing may bring significant benefits for estimating the number of detectable faults and comparing different projects and practices.
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
Venue: arXiv cs.DS 2012
Year: 2012

Belief propagation (BP) is a message-passing heuristic for statistical inference in graphical models such as Bayesian networks and Markov random fields. BP is used to compute marginal distributions or maximum likelihood assignments and has applications in many areas, including machine learning, image processing, and computer vision. However, the theoretical understanding of the performance of BP is unsatisfactory. Recently, BP has been applied to combinatorial optimization problems. It has been proved that BP can be used to compute maximum-weight matchings and minimum-cost flows for instances with a unique optimum. The number of iterations needed for this is pseudo-polynomial and hence BP is not efficient in general. We study belief propagation in the framework of smoothed analysis and prove that with high probability the number of iterations needed to compute maximum-weight matchings and minimum-cost flows is bounded by a polynomial if the weights/costs of the edges are randomly perturbed. To prove our upper bounds, we use an isolation lemma by Beier and Vöcking (SIAM J. Comput. 2006) for matching and generalize an isolation lemma for min-cost flow by Gamarnik, Shah, and Wei (Operations Research, 2012). We also prove almost matching lower tail bounds for the number of iterations that BP needs to converge.
Network Sampling: From Static to Streaming Graphs
Venue: arXiv cs.SI 2012
Year: 2012

Network sampling is integral to the analysis of social, information, and biological networks. Since many real-world networks are massive in size, continuously evolving, and/or distributed in nature, the network structure is often sampled in order to facilitate study. For these reasons, a more thorough and complete understanding of network sampling is critical to support the field of network science. In this paper, we outline a framework for the general problem of network sampling, by highlighting the different objectives, population and units of interest, and classes of network sampling methods. In addition, we propose a spectrum of computational models for network sampling methods, ranging from the traditionally studied model based on the assumption of a static domain to a more challenging model that is appropriate for streaming domains. We design a family of sampling methods based on the concept of graph induction that generalize across the full spectrum of computational models (from static to streaming) while efficiently preserving many of the topological properties of the input graphs. Furthermore, we demonstrate how traditional static sampling algorithms can be modified for graph streams for each of the three main classes of sampling methods: node, edge, and topology-based sampling. Our experimental results indicate that our proposed family of sampling methods more accurately preserves the underlying properties of the graph for both static and streaming graphs. Finally, we study the impact of network sampling algorithms on the parameter estimation and performance evaluation of relational classification algorithms.
The Encoding of Natural Numbers as Nested Parentheses Strings with Associated Probability Distributions
Venue: arXiv cs.DM 2012
Year: 2012

We provide an efficient encoding of the natural numbers {0,1,2,3,...} as strings of nested parentheses {(),(()),(()()),((())),...}, or considered inversely, an efficient enumeration of such strings. The technique is based on the recursive definition of the Catalan numbers. The probability distributions arising from this encoding are explored. Applications of this encoding to prefix-free data encoding and recursive function theory are briefly considered.
Transform coder identification based on quantization footprints and lattice theory
Venue: arXiv cs.IT 2012
Year: 2012

Transform coding is routinely used for lossy compression of discrete sources with memory. The input signal is divided into N-dimensional vectors, which are transformed by means of a linear mapping. Then, transform coefficients are quantized and entropy coded. In this paper we consider the problem of identifying the transform matrix as well as the quantization step sizes. We study the challenging case in which the only available information is a set of P transform decoded vectors. We formulate the problem in terms of finding the lattice with the largest determinant that contains all observed vectors. We propose an algorithm that is able to find the optimal solution and we formally study its convergence properties. Our analysis shows that it is possible to identify successfully both the transform and the quantization step sizes when P >= N + d where d is a small integer, and the probability of failure decreases exponentially to zero as P - N increases.
Multi Relational Data Mining Approaches: A Data Mining Technique
Venue: arXiv cs.DB 2012
Year: 2012

The multi relational data mining approach has developed as an alternative way for handling the structured data such that RDBMS. This will provides the mining in multiple tables directly. In MRDM the patterns are available in multiple tables (relations) from a relational database. As the data are available over the many tables which will affect the many problems in the practice of the data mining. To deal with this problem, one either constructs a single table by Propositionalisation, or uses a Multi-Relational Data Mining algorithm. MRDM approaches have been successfully applied in the area of bioinformatics. Three popular pattern finding techniques classification, clustering and association are frequently used in MRDM. Multi relational approach has developed as an alternative for analyzing the structured data such as relational database. MRDM allowing applying directly in the data mining in multiple tables. To avoid the expensive joining operations and semantic losses we used the MRDM technique. This paper focuses some of the application areas of MRDM and feature directions as well as the comparison of ILP, GM, SSDM and MRDM
Visual Recognition of Isolated Swedish Sign Language Signs
Venue: arXiv cs.CV 2012
Year: 2012

We present a method for recognition of isolated Swedish Sign Language signs. The method will be used in a game intended to help children training signing at home, as a complement to training with a teacher. The target group is not primarily deaf children, but children with language disorders. Using sign language as a support in conversation has been shown to greatly stimulate the speech development of such children. The signer is captured with an RGB-D (Kinect) sensor, which has three advantages over a regular RGB camera. Firstly, it allows complex backgrounds to be removed easily. We segment the hands and face based on skin color and depth information. Secondly, it helps with the resolution of hand over face occlusion. Thirdly, signs take place in 3D; some aspects of the signs are defined by hand motion vertically to the image plane. This motion can be estimated if the depth is observable. The 3D motion of the hands relative to the torso are used as a cue together with the hand shape, and HMMs trained with this input are used for classification. To obtain higher robustness towards differences across signers, Fisher Linear Discriminant Analysis is used to find the combinations of features that are most descriptive for each sign, regardless of signer. Experiments show that the system can distinguish signs from a challenging 94 word vocabulary with a precision of up to 94% in the signer dependent case and up to 47% in the signer independent case.
Two Approaches to the Construction of Deletion Correcting Codes: Weight Partitioning and Optimal Colorings
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of constructing deletion correcting codes over a binary alphabet and take a graph theoretic view. An $n$-bit $s$-deletion correcting code is an independent set in a particular graph. We propose constructing such a code by taking the union of many constant Hamming weight codes. This results in codes that have additional structure. Searching for codes in constant Hamming weight induced subgraphs is computationally easier than searching the original graph. We prove a lower bound on size of a codebook constructed this way for any number of deletions and show that it is only a small factor below the corresponding lower bound on unrestricted codes. In the single deletion case, we find optimal colorings of the constant Hamming weight induced subgraphs. We show that the resulting code is asymptotically optimal. We discuss the relationship between codes and colorings and observe that the VT codes are optimal in a coloring sense. We prove a new lower bound on the chromatic number of the deletion channel graphs. Colorings of the deletion channel graphs that match this bound do not necessarily produce asymptotically optimal codes.
Membrane Systems and Petri Net Synthesis
Venue: arXiv cs.LO 2012
Year: 2012

Automated synthesis from behavioural specifications is an attractive and powerful way of constructing concurrent systems. Here we focus on the problem of synthesising a membrane system from a behavioural specification given in the form of a transition system which specifies the desired state space of the system to be constructed. We demonstrate how a Petri net solution to this problem, based on the notion of region of a transition system, yields a method of automated synthesis of membrane systems from state spaces.
Higher-order port-graph rewriting
Venue: arXiv cs.LO 2012
Year: 2012

The biologically inspired framework of port-graphs has been successfully used to specify complex systems. It is the basis of the PORGY modelling tool. To facilitate the specification of proof normalisation procedures via graph rewriting, in this paper we add higher-order features to the original port-graph syntax, along with a generalised notion of graph morphism. We provide a matching algorithm which enables to implement higher-order port-graph rewriting in PORGY, thus one can visually study the dynamics of the systems modelled. We illustrate the expressive power of higher-order port-graphs with examples taken from proof-net reduction systems.
Network Coding Meets Multimedia: a Review
Venue: arXiv cs.MM 2012
Year: 2012

While every network node only relays messages in a traditional communication system, the recent network coding (NC) paradigm proposes to implement simple in-network processing with packet combinations in the nodes. NC extends the concept of "encoding" a message beyond source coding (for compression) and channel coding (for protection against errors and losses). It has been shown to increase network throughput compared to traditional networks implementation, to reduce delay and to provide robustness to transmission errors and network dynamics. These features are so appealing for multimedia applications that they have spurred a large research effort towards the development of multimedia-specific NC techniques. This paper reviews the recent work in NC for multimedia applications and focuses on the techniques that fill the gap between NC theory and practical applications. It outlines the benefits of NC and presents the open challenges in this area. The paper initially focuses on multimedia-specific aspects of network coding, in particular delay, in-network error control, and media-specific error control. These aspects permit to handle varying network conditions as well as client heterogeneity, which are critical to the design and deployment of multimedia systems. After introducing these general concepts, the paper reviews in detail two applications that lend themselves naturally to NC via the cooperation and broadcast models, namely peer-to-peer multimedia streaming and wireless networking.
Non-Local Patch Regression: Robust Image Denoising in Patch Space
Venue: arXiv cs.CV 2012
Year: 2012

It was recently demonstrated in [Chaudhury et al.,Non-Local Euclidean Medians,2012] that the denoising performance of Non-Local Means (NLM) can be improved at large noise levels by replacing the mean by the robust Euclidean median. Numerical experiments on synthetic and natural images showed that the latter consistently performed better than NLM beyond a certain noise level, and significantly so for images with sharp edges. The Euclidean mean and median can be put into a common regression (on the patch space) framework, in which the l_2 norm of the residuals is considered in the former, while the l_1 norm is considered in the latter. The natural question then is what happens if we consider l_p (0<p<1) regression? We investigate this possibility in this paper.
A Dynamical System for PageRank with Time-Dependent Teleportation
Venue: arXiv cs.SI 2012
Year: 2012

We propose a dynamical system that captures changes to the network centrality of nodes as external interest in those nodes vary. We derive this system by adding time-dependent teleportation to the PageRank score. The result is not a single set of importance scores, but rather a time-dependent set. These can be converted into ranked lists in a variety of ways, for instance, by taking the largest change in the importance score. For an interesting class of the dynamic teleportation functions, we derive closed form solutions for the dynamic PageRank vector. The magnitude of the deviation from a static PageRank vector is given by a PageRank problem with complex-valued teleportation parameters. Moreover, these dynamical systems are easy to evaluate. We demonstrate the utility of dynamic teleportation on both the article graph of Wikipedia, where the external interest information is given by the number of hourly visitors to each page, and the Twitter social network, where external interest is the number of tweets per month. For these problems, we show that using information from the dynamical system helps improve a prediction task and identify trends in the data.
Toward a Principled Framework for Benchmarking Consistency
Venue: arXiv cs.DC 2012
Year: 2012

Large-scale key-value storage systems sacrifice consistency in the interest of dependability (i.e., partition tolerance and availability), as well as performance (i.e., latency). Such systems provide eventual consistency,which---to this point---has been difficult to quantify in real systems. Given the many implementations and deployments of eventually-consistent systems (e.g., NoSQL systems), attempts have been made to measure this consistency empirically, but they suffer from important drawbacks. For example, state-of-the art consistency benchmarks exercise the system only in restricted ways and disrupt the workload, which limits their accuracy. In this paper, we take the position that a consistency benchmark should paint a comprehensive picture of the relationship between the storage system under consideration, the workload, the pattern of failures, and the consistency observed by clients. To illustrate our point, we first survey prior efforts to quantify eventual consistency. We then present a benchmarking technique that overcomes the shortcomings of existing techniques to measure the consistency observed by clients as they execute the workload under consideration. This method is versatile and minimally disruptive to the system under test. As a proof of concept, we demonstrate this tool on Cassandra.
Degrees-of-Freedom Region of Time Correlated MISO Broadcast Channel with Perfect Delayed CSIT and Asymmetric Partial Current CSIT
Venue: arXiv cs.IT 2012
Year: 2012

The impact of imperfect CSIT on the degrees of freedom (DoF) of a time correlated MISO Broadcast Channel has drawn a lot of attention recently. Maddah-Ali and Tse have shown that the completely stale CSIT still benefit the DoF. In very recent works, Yang et al. have extended the results by integrating the partial current CSIT for a two-user MISO broadcast channel. However, those researches so far focused on a symmetric case. In this contribution, we investigate a more general case where the transmitter has knowledge of current CSI of both users with unequal qualities. The essential ingredient in our work lies in the way to multicast the overheard interference to boost the DoF. The optimal DoF region is simply proved and its achievability is shown using a novel transmission scheme assuming an infinite number of channel uses.
Artificial Neural Network Based Optical Character Recognition
Venue: arXiv cs.CV 2012
Year: 2012

Optical Character Recognition deals in recognition and classification of characters from an image. For the recognition to be accurate, certain topological and geometrical properties are calculated, based on which a character is classified and recognized. Also, the Human psychology perceives characters by its overall shape and features such as strokes, curves, protrusions, enclosures etc. These properties, also called Features are extracted from the image by means of spatial pixel-based calculation. A collection of such features, called Vectors, help in defining a character uniquely, by means of an Artificial Neural Network that uses these Feature Vectors.
Towards a Scalable Dynamic Spatial Database System
Venue: arXiv cs.DB 2012
Year: 2012

With the rise of GPS-enabled smartphones and other similar mobile devices, massive amounts of location data are available. However, no scalable solutions for soft real-time spatial queries on large sets of moving objects have yet emerged. In this paper we explore and measure the limits of actual algorithms and implementations regarding different application scenarios. And finally we propose a novel distributed architecture to solve the scalability issues.
The crossing numbers of $K_{n,n}-nK_2$, $K_{n}\times P_2$, $K_{n}\times P_3$ and $K_n\times C_4$
Venue: arXiv cs.DM 2012
Year: 2012

The crossing number of a graph $G$ is the minimum number of pairwise intersections of edges among all drawings of $G$. In this paper, we study the crossing number of $K_{n,n}-nK_2$, $K_n\times P_2$, $K_n\times P_3$ and $K_n\times C_4$.
Performance Evaluation of DOA Estimation using MATLAB
Venue: arXiv cs.OH 2012
Year: 2012

This paper presents the performance analysis of directions of arrival estimation techniques, Subspace and the Non-Subspace methods. In this paper, exploring the analysis category of high resolution and super resolution algorithms, presentation of description, comparison and the performance and resolution analyses of these algorithms are made. Sensitivity to various perturbations and the effect of parameters related to the design of the sensor array itself such as the number of array elements and their spacing are also investigated.