OpenRaiser/Intern-Atlas huggingface dataset:
Regression-free Synthesis for Concurrency
Venue: arXiv cs.PL 2014
Year: 2014

While fixing concurrency bugs, program repair algorithms may introduce new concurrency bugs. We present an algorithm that avoids such regressions. The solution space is given by a set of program transformations we consider in for repair process. These include reordering of instructions within a thread and inserting atomic sections. The new algorithm learns a constraint on the space of candidate solutions, from both positive examples (error-free traces) and counterexamples (error traces). From each counterexample, the algorithm learns a constraint necessary to remove the errors. From each positive examples, it learns a constraint that is necessary in order to prevent the repair from turning the trace into an error trace. We implemented the algorithm and evaluated it on simplified Linux device drivers with known bugs.
Expertise localization discovered through correlation of key term distribution and community detection in co-author networks
Venue: arXiv cs.SI 2014
Year: 2014

We present an efficient and effective automatic method for determining the research focus of scientific communities found in co-authorship networks. It utilizes bibliographic data from a database to form the network, followed by fastgreedy community detection to identify communities within large connected components of the network. Text analysis techniques are used to identify community-specific significant terms which represent the topic of the community. In order to greatly reduce computation time, the `Topics' field of each publication in the network is analyzed rather than its entire text. Using this text analysis approach requires a certain level of statistical confidence,therefore analyzing very small communities is not effective with this technique. We find a minimum community size threshold of 8 coauthored papers; below this value, the community's topic cannot be reliably identified with this method. Additionally, we consider the implications this study has regarding factors involved in the formation of scientific communities in co-authorship networks.
Query Optimization for Dynamic Graphs
Venue: arXiv cs.DB 2014
Year: 2014

Given a query graph that represents a pattern of interest, the emerging pattern detection problem can be viewed as a continuous query problem on a dynamic graph. We present an incremental algorithm for continuous query processing on dynamic graphs. The algorithm is based on the concept of query decomposition; we decompose a query graph into smaller subgraphs and assemble the result of sub-queries to find complete matches with the specified query. The novelty of our work lies in using the subgraph distributional statistics collected from the dynamic graph to generate the decomposition. We introduce a "Lazy Search" algorithm where the search strategy is decided on a vertex-to-vertex basis depending on the likelihood of a match in the vertex neighborhood. We also propose a metric named "Relative Selectivity" that is used to select between different query decomposition strategies. Our experiments performed on real online news, network traffic stream and a synthetic social network benchmark demonstrate 10-100x speedups over competing approaches.
Benchmarking Named Entity Disambiguation approaches for Streaming Graphs
Venue: arXiv cs.CL 2014
Year: 2014

Named Entity Disambiaguation (NED) is a central task for applications dealing with natural language text. Assume that we have a graph based knowledge base (subsequently referred as Knowledge Graph) where nodes represent various real world entities such as people, location, organization and concepts. Given data sources such as social media streams and web pages Entity Linking is the task of mapping named entities that are extracted from the data to those present in the Knowledge Graph. This is an inherently difficult task due to several reasons. Almost all these data sources are generated without any formal ontology; the unstructured nature of the input, limited context and the ambiguity involved when multiple entities are mapped to the same name make this a hard task. This report looks at two state of the art systems employing two distinctive approaches: graph based Accurate Online Disambiguation of Entities (AIDA) and Mined Evidence Named Entity Disambiguation (MENED), which employs a statistical inference approach. We compare both approaches using the data set and queries provided by the Knowledge Base Population (KBP) track at 2011 NIST Text Analytics Conference (TAC). This report begins with an overview of the respective approaches, followed by detailed description of the experimental setup. It concludes with our findings from the benchmarking exercise.
FilterPlus: A real-time content filtering extension for Google Chrome
Venue: arXiv cs.CR 2014
Year: 2014

Content filtering in web browsers is a tedious process for most of the people, because of several reasons. By blocking JavaScript, Cookies and Popups, end users can ensure maximum protection from browser based attacks and vulnerabilities. In order to accomplish this, we build an extension for Google Chrome which allows users to have easy control over what they wish to recievce from a web page. We also build this extension in such a way that it remembers the choice of options made by the user for every URLs, thereby letting users create rules for websites they visit.
Experimental Study of Remote Job Submission and Execution on LRM through Grid Computing Mechanisms
Venue: arXiv cs.DC 2014
Year: 2014

Remote job submission and execution is fundamental requirement of distributed computing done using Cluster computing. However, Cluster computing limits usage within a single organization. Grid computing environment can allow use of resources for remote job execution that are available in other organizations. This paper discusses concepts of batch-job execution using LRM and using Grid. The paper discusses two ways of preparing test Grid computing environment that we use for experimental testing of concepts. This paper presents experimental testing of remote job submission and execution mechanisms through LRM specific way and Grid computing ways. Moreover, the paper also discusses various problems faced while working with Grid computing environment and discusses their trouble-shootings. The understanding and experimental testing presented in this paper would become very useful to researchers who are new to the field of job management in Grid.
A Note on Higher Order and Variable Order Logic over Finite Models
Venue: arXiv cs.LO 2014
Year: 2014

We show that descriptive complexity's result extends in High Order Logic to capture the expressivity of Turing Machine which have a finite number of alternation and whose time or space is bounded by a finite tower of exponential. Hence we have a logical characterisation of ELEMENTARY. We also consider the expressivity of some fixed point operators and of monadic high order logic. Finally, we show that Variable Order logic over finite structures contain the Analytical Hierarchy.
Fast matrix completion without the condition number
Venue: arXiv cs.LG 2014
Year: 2014

We give the first algorithm for Matrix Completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix in the running time. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.
VANET Applications: Hot Use Cases
Venue: arXiv cs.CY 2014
Year: 2014

Current challenges of car manufacturers are to make roads safe, to achieve free flowing traffic with few congestions, and to reduce pollution by an effective fuel use. To reach these goals, many improvements are performed in-car, but more and more approaches rely on connected cars with communication capabilities between cars, with an infrastructure, or with IoT devices. Monitoring and coordinating vehicles allow then to compute intelligent ways of transportation. Connected cars have introduced a new way of thinking cars - not only as a mean for a driver to go from A to B, but as smart cars - a user extension like the smartphone today. In this report, we introduce concepts and specific vocabulary in order to classify current innovations or ideas on the emerging topic of smart car. We present a graphical categorization showing this evolution in function of the societal evolution. Different perspectives are adopted: a vehicle-centric view, a vehicle-network view, and a user-centric view; described by simple and complex use-cases and illustrated by a list of emerging and current projects from the academic and industrial worlds. We identified an empty space in innovation between the user and his car: paradoxically even if they are both in interaction, they are separated through different application uses. Future challenge is to interlace social concerns of the user within an intelligent and efficient driving.
Measuring information transfer in a soft robotic arm
Venue: arXiv cs.IT 2014
Year: 2014

Soft robots can exhibit diverse behaviors with simple types of actuation by partially outsourcing control to the morphological and material properties of their soft bodies, which is made possible by the tight coupling between control, body, and environment. In this paper, we present a method that will quantitatively characterize these diverse spatiotemporal dynamics of a soft body based on the information-theoretic approach. In particular, soft bodies have the ability to propagate the effect of actuation through the entire body, with a certain time delay, due to their elasticity. Our goal is to capture this delayed interaction in a quantitative manner based on a measure called momentary information transfer. We extend this measure to soft robotic applications and demonstrate its power using a physical soft robotic platform inspired by the octopus. Our approach is illustrated in two ways. First, we statistically characterize the delayed actuation propagation through the body as a strength of information transfer. Second, we capture this information propagation directly as local information dynamics. As a result, we show that our approach can successfully characterize the spatiotemporal dynamics of the soft robotic platform, explicitly visualizing how information transfers through the entire body with delays. Further extension scenarios of our approach are discussed for soft robotic applications in general.
Web API Fragility: How Robust is Your Web API Client
Venue: arXiv cs.SE 2014
Year: 2014

Web APIs provide a systematic and extensible approach for application-to-application interaction. A large number of mobile applications makes use of web APIs to integrate services into apps. Each Web API's evolution pace is determined by their respective developer and mobile application developers are forced to accompany the API providers in their software evolution tasks. In this paper we investigate whether mobile application developers understand and how they deal with the added distress of web APIs evolving. In particular, we studied how robust 48 high profile mobile applications are when dealing with mutated web API responses. Additionally, we interviewed three mobile application developers to better understand their choices and trade-offs regarding web API integration.
The Role Model Estimator Revisited
Venue: arXiv cs.IT 2014
Year: 2014

We re-visit the role model strategy introduced in an earlier paper, which allows one to train an estimator for degraded observations by imitating a reference estimator that has access to superior observations. We show that, while it is true and surprising that this strategy yields the optimal Bayesian estimator for the degraded observations, it in fact reduces to a much simpler form in the non-parametric case, which corresponds to a type of Monte Carlo integration. We then show an example for which only parametric estimation can be implemented and discuss further applications for discrete parametric estimation where the role model strategy does have its uses, although it loses claim to optimality in this context.
Non-binary LDPC decoding using truncated messages in the Walsh-Hadamard domain
Venue: arXiv cs.IT 2014
Year: 2014

The Extended Min-Sum (EMS) algorithm for non-binary low-density parity-check (LDPC) defined over an alphabet of size $q$ operates on truncated messages of length $q'$ to achieve a complexity of the order $q'^2$. In contrast, Walsh-Hadamard (WH) transform based iterative decoders achieve a complexity of the order $q\log q$, which is much larger for $q'<<q$. In this paper, we demonstrate that considerable savings can be achieved by letting WH based decoders operate on truncated messages as well. We concentrate on the direct WH transform and compute the number of operations required if only $q'$ of the $q$ inputs are non-zero. Our paper does not cover the inverse WH transform and hence further research is needed to construct WH based decoders that can compete with the EMS algorithm on complexity terms.
One-Step or Two-Step Optimization and the Overfitting Phenomenon: A Case Study on Time Series Classification
Venue: arXiv cs.AI 2014
Year: 2014

For the last few decades, optimization has been developing at a fast rate. Bio-inspired optimization algorithms are metaheuristics inspired by nature. These algorithms have been applied to solve different problems in engineering, economics, and other domains. Bio-inspired algorithms have also been applied in different branches of information technology such as networking and software engineering. Time series data mining is a field of information technology that has its share of these applications too. In previous works we showed how bio-inspired algorithms such as the genetic algorithms and differential evolution can be used to find the locations of the breakpoints used in the symbolic aggregate approximation of time series representation, and in another work we showed how we can utilize the particle swarm optimization, one of the famous bio-inspired algorithms, to set weights to the different segments in the symbolic aggregate approximation representation. In this paper we present, in two different approaches, a new meta optimization process that produces optimal locations of the breakpoints in addition to optimal weights of the segments. The experiments of time series classification task that we conducted show an interesting example of how the overfitting phenomenon, a frequently encountered problem in data mining which happens when the model overfits the training set, can interfere in the optimization process and hide the superior performance of an optimization algorithm.
Convex separable problems with linear and box constraints in signal processing and communications
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we focus on separable convex optimization problems with box constraints and a set of triangular linear constraints. The solution is given in closed-form as a function of some Lagrange multipliers that can be computed through an iterative procedure in a finite number of steps. Graphical interpretations are given casting valuable insights into the proposed algorithm and allowing to retain some of the intuition spelled out by the water-filling policy. It turns out that it is not only general enough to compute the solution to different instances of the problem at hand but also remarkably simple in the way it operates. We also show how some power allocation problems in signal processing and communications can be solved with the proposed algorithm.
Coded Caching for Delay-Sensitive Content
Venue: arXiv cs.IT 2014
Year: 2014

Coded caching is a recently proposed technique that achieves significant performance gains for cache networks compared to uncoded caching schemes. However, this substantial coding gain is attained at the cost of large delivery delay, which is not tolerable in delay-sensitive applications such as video streaming. In this paper, we identify and investigate the tradeoff between the performance gain of coded caching and the delivery delay. We propose a computationally efficient caching algorithm that provides the gains of coding and respects delay constraints. The proposed algorithm achieves the optimum performance for large delay, but still offers major gains for small delay. These gains are demonstrated in a practical setting with a video-streaming prototype.
Analysis of Attacks on Hybrid DWT-DCT Algorithm for Digital Image Watermarking With MATLAB
Venue: arXiv cs.CR 2014
Year: 2014

Watermarking algorithms needs properties of robustness and perceptibility. But these properties are affected by different -2 types of attacks performed on watermarked images. The goal of performing attacks is destroy the information of watermark hidden in the watermarked image. So every Algorithms should be previously tested by developers so that it would not affected by attacks.
Efficient On-the-fly Category Retrieval using ConvNets and GPUs
Venue: arXiv cs.CV 2014
Year: 2014

We investigate the gains in precision and speed, that can be obtained by using Convolutional Networks (ConvNets) for on-the-fly retrieval - where classifiers are learnt at run time for a textual query from downloaded images, and used to rank large image or video datasets. We make three contributions: (i) we present an evaluation of state-of-the-art image representations for object category retrieval over standard benchmark datasets containing 1M+ images; (ii) we show that ConvNets can be used to obtain features which are incredibly performant, and yet much lower dimensional than previous state-of-the-art image representations, and that their dimensionality can be reduced further without loss in performance by compression using product quantization or binarization. Consequently, features with the state-of-the-art performance on large-scale datasets of millions of images can fit in the memory of even a commodity GPU card; (iii) we show that an SVM classifier can be learnt within a ConvNet framework on a GPU in parallel with downloading the new training images, allowing for a continuous refinement of the model as more images become available, and simultaneous training and ranking. The outcome is an on-the-fly system that significantly outperforms its predecessors in terms of: precision of retrieval, memory requirements, and speed, facilitating accurate on-the-fly learning and ranking in under a second on a single GPU.
The Information Service Evaluation (ISE) Model
Venue: arXiv cs.CY 2014
Year: 2014

Information services are an inherent part of our everyday life. Especially since ubiquitous cities are being developed all over the world their number is increasing even faster. They aim at facilitating the production of information and the access to the needed information and are supposed to make life easier. Until today many different evaluation models (among others, TAM, TAM 2, TAM 3, UTAUT and MATH) have been developed to measure the quality and acceptance of these services. Still, they only consider subareas of the whole concept that represents an information service. As a holistic and comprehensive approach, the ISE Model studies five dimensions that influence adoption, use, impact and diffusion of the information service: information service quality, information user, information acceptance, information environment and time. All these aspects have a great impact on the final grading and of the success (or failure) of the service. Our model combines approaches, which study subjective impressions of users (e.g., the perceived service quality), and user-independent, more objective approaches (e.g., the degree of gamification of a system). Furthermore, we adopt results of network economics, especially the Success breeds success-principle.
A Comparative Study of Meta-heuristic Algorithms for Solving Quadratic Assignment Problem
Venue: arXiv cs.AI 2014
Year: 2014

Quadratic Assignment Problem (QAP) is an NP-hard combinatorial optimization problem, therefore, solving the QAP requires applying one or more of the meta-heuristic algorithms. This paper presents a comparative study between Meta-heuristic algorithms: Genetic Algorithm, Tabu Search, and Simulated annealing for solving a real-life (QAP) and analyze their performance in terms of both runtime efficiency and solution quality. The results show that Genetic Algorithm has a better solution quality while Tabu Search has a faster execution time in comparison with other Meta-heuristic algorithms for solving QAP.
Synthetic Generation of Solar States for Smart Grid: A Multiple Segment Markov Chain Apptoach
Venue: arXiv cs.PF 2014
Year: 2014

The use of photovoltaic (PV) sources is becoming very popular in smart grid for their ecological benefits, with higher scalability and utilization for local generation and delivery. PV can also potentially avoid the energy losses that are normally associated with long-range grid distribution. The increased penetration of solar panels, however, has introduced a need for solar energy models that are capable of producing realistic synthetic data with small error margins. Such models, for instance, can be used to design the appropriate size of energy storage devices or to determine the maximum charging rate of a PV-powered electric vehicle (EV) charging station. In this regard, this paper proposes a stochastic model for solar generation using a Markov chain approach. Based on real data, it is first shown that the solar states are inter-dependent, and thus suitable for modeling using a Markov model. Then, the probabilities of transition between states are shown to be heterogeneous over different time segments. A model is proposed that captures the inter temporal dependency of solar irradiance through segmentation of the Markov chain across different times of the day. In the studied model, different state transition matrices are constructed for different time segments, which the proposed algorithm then uses to generate the solar states for different times of the day. Numerical examples are provided to show the effectiveness of the proposed synthetic generator.
Integrating R and Hadoop for Big Data Analysis
Venue: arXiv cs.DC 2014
Year: 2014

Analyzing and working with big data could be very diffi cult using classical means like relational database management systems or desktop software packages for statistics and visualization. Instead, big data requires large clusters with hundreds or even thousands of computing nodes. Offi cial statistics is increasingly considering big data for deriving new statistics because big data sources could produce more relevant and timely statistics than traditional sources. One of the software tools successfully and wide spread used for storage and processing of big data sets on clusters of commodity hardware is Hadoop. Hadoop framework contains libraries, a distributed fi le-system (HDFS), a resource-management platform and implements a version of the MapReduce programming model for large scale data processing. In this paper we investigate the possibilities of integrating Hadoop with R which is a popular software used for statistical computing and data visualization. We present three ways of integrating them: R with Streaming, Rhipe and RHadoop and we emphasize the advantages and disadvantages of each solution.