OpenRaiser/Intern-Atlas huggingface dataset:
Approximability of the Minimum Weighted Doubly Resolving Set Problem
Venue: arXiv cs.DM 2014
Year: 2014

Locating source of diffusion in networks is crucial for controlling and preventing epidemic risks. It has been studied under various probabilistic models. In this paper, we study source location from a deterministic point of view by modeling it as the minimum weighted doubly resolving set (DRS) problem, which is a strengthening of the well-known metric dimension problem. Let $G$ be a vertex weighted undirected graph on $n$ vertices. A vertex subset $S$ of $G$ is DRS of $G$ if for every pair of vertices $u,v$ in $G$, there exist $x,y\in S$ such that the difference of distances (in terms of number of edges) between $u$ and $x,y$ is not equal to the difference of distances between $v$ and $x,y$. The minimum weighted DRS problem consists of finding a DRS in $G$ with minimum total weight. We establish $Θ(\ln n)$ approximability of the minimum DRS problem on general graphs for both weighted and unweighted versions. This is the first work providing explicit approximation lower and upper bounds for minimum (weighted) DRS problem, which are nearly tight. Moreover, we design first known strongly polynomial time algorithms for the minimum weighted DRS problem on general wheels and trees with additional constant $k\ge0$ edges.
PrivLoc: Preventing Location Tracking in Geofencing Services
Venue: arXiv cs.CR 2014
Year: 2014

Location-based services are increasingly used in our daily activities. In current services, users however have to give up their location privacy in order to acquire the service. The literature features a large number of contributions which aim at enhancing user privacy in location-based services. Most of these contributions obfuscate the locations of users using spatial and/or temporal cloaking in order to provide k-anonymity. Although such schemes can indeed strengthen the location privacy of users, they often decrease the service quality and do not necessarily prevent the possible tracking of user movements (i.e., direction, trajectory, velocity). With the rise of Geofencing applications, tracking of movements becomes more evident since, in these settings, the service provider is not only requesting a single location of the user, but requires the movement vectors of users to determine whether the user has entered/exited a Geofence of interest. In this paper, we propose a novel solution, PrivLoc, which enables the privacy-preserving outsourcing of Geofencing and location-based services to the cloud without leaking any meaningful information about the location, trajectory, and velocity of the users. Notably, PrivLoc enables an efficient and privacy-preserving intersection of movement vectors with any polygon of interest, leveraging functionality from existing Geofencing services or spatial databases. We analyze the security and privacy provisions of PrivLoc and we evaluate the performance of our scheme by means of implementation. Our results show that the performance overhead introduced by PrivLoc can be largely tolerated in realistic deployment settings.
Accelerated Approximation of the Complex Roots of a Univariate Polynomial (Extended Abstract)
Venue: arXiv cs.SC 2014
Year: 2014

Highly efficient and even nearly optimal algorithms have been developed for the classical problem of univariate polynomial root-finding (see, e.g., \cite{P95}, \cite{P02}, \cite{MNP13}, and the bibliography therein), but this is still an area of active research. By combining some powerful techniques developed in this area we devise new nearly optimal algorithms, whose substantial merit is their simplicity, important for the implementation.
Light Weight Implementation of Stream Ciphers for M-Commerce Applications
Venue: arXiv cs.CR 2014
Year: 2014

In today's world the use of computer and telecommunications networking is essential for human life. Among these, mobile tools and devices due to availability, have found a special impact on everyone life. This feature addition to providing sample facilities such as financial transactions at any place and time has raised the Sensitivities about security of these devices. In order to provide security, numerous techniques have been proposed which due to the limitations of mobile devices; an algorithm should be taken that have the ability to function for light weight ubiquitous computing. In this paper, four eSTREAM candidates from software profile were taken into account and analyzed and implemented by using J2ME technology. Then these algorithms were implemented on a variety of mobile phones and are compared with each other in terms of execution time and finally the obtained Results are expressed.
Generalized Evidence Theory
Venue: arXiv cs.AI 2014
Year: 2014

Conflict management is still an open issue in the application of Dempster Shafer evidence theory. A lot of works have been presented to address this issue. In this paper, a new theory, called as generalized evidence theory (GET), is proposed. Compared with existing methods, GET assumes that the general situation is in open world due to the uncertainty and incomplete knowledge. The conflicting evidence is handled under the framework of GET. It is shown that the new theory can explain and deal with the conflicting evidence in a more reasonable way.
The fifteen year struggle of decentralizing privacy-enhancing technology
Venue: arXiv cs.CY 2014
Year: 2014

Ever since the introduction of the internet, it has been void of any privacy. The majority of internet traffic currently is and always has been unencrypted. A number of anonymous communication overlay networks exist whose aim it is to provide privacy to its users. However, due to the nature of the internet, there is major difficulty in getting these networks to become both decentralized and anonymous. We list reasons for having anonymous networks, discern the problems in achieving decentralization and sum up the biggest initiatives in the field and their current status. To do so, we use one exemplary network, the Tor network. We explain how Tor works, what vulnerabilities this network currently has, and possible attacks that could be used to violate privacy and anonymity. The Tor network is used as a key comparison network in the main part of the report: a tabular overview of the major anonymous networking technologies in use today.
Topology optimization based on moving deformable components: A new computational framework
Venue: arXiv cs.CE 2014
Year: 2014

In the present work, a new computational framework for structural topology optimization based on the concept of moving deformable components is proposed. Compared with the traditional pixel or node point-based solution framework, the proposed solution paradigm can incorporate more geometry and mechanical information into topology optimization directly and therefore render the solution process more flexible. It also has the great potential to reduce the computational burden associated with topology optimization substantially. Some representative examples are presented to illustrate the effectiveness of the proposed approach.
$μ$-calculus on data words
Venue: arXiv cs.LO 2014
Year: 2014

We study the decidability and expressiveness issues of $μ$-calculus on data words and data $ω$-words. It is shown that the full logic as well as the fragment which uses only the least fixpoints are undecidable, while the fragment containing only greatest fixpoints is decidable. Two subclasses, namely BMA and BR, obtained by limiting the compositions of formulas and their automata characterizations are exhibited. Furthermore, Data-LTL and two-variable first-order logic are expressed as unary alternation-free fragment of BMA. Finally basic inclusions of the fragments are discussed.
A matheuristic approach for the Pollution-Routing Problem
Venue: arXiv cs.DS 2014
Year: 2014

This paper deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by [Bektas and Laporte (2011), Transport. Res. B-Meth. 45 (8), 1232-1250]. The objective is to minimize operational and environmental costs while respecting capacity constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. The vehicle speeds are considered as decision variables. They complement routing decisions, impacting the total cost, the travel time between locations, and thus the set of feasible routes. We propose a method which combines a local search-based metaheuristic with an integer programming approach over a set covering formulation and a recursive speed-optimization algorithm. This hybridization enables to integrate more tightly route and speed decisions. Moreover, two other "green" VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed. The proposed method compares very favorably with previous algorithms from the literature and many new improved solutions are reported.
Document Retrieval on Repetitive Collections
Venue: arXiv cs.DS 2014
Year: 2014

Document retrieval aims at finding the most important documents where a pattern appears in a collection of strings. Traditional pattern-matching techniques yield brute-force document retrieval solutions, which has motivated the research on tailored indexes that offer near-optimal performance. However, an experimental study establishing which alternatives are actually better than brute force, and which perform best depending on the collection characteristics, has not been carried out. In this paper we address this shortcoming by exploring the relationship between the nature of the underlying collection and the performance of current methods. Via extensive experiments we show that established solutions are often beaten in practice by brute-force alternatives. We also design new methods that offer superior time/space trade-offs, particularly on repetitive collections.
Prediction of rate of improvement of software quality and development effort on the basis of Degreeof excellence with respect to number of lines of code
Venue: arXiv cs.SE 2014
Year: 2014

The objective of this research work is to improve the degree of excellence by removing the number of exceptions from the software. The modern age is more concerned with the quality of software. Extensive research is being carried out in this direction. The rate of improvement of quality of software largely depends on the development time. This development time is chiefly calculated in clock hours. However development time does not reflect the effort put in by the developer. A better parameter can be the rate of improvement of quality level or the rate of improvement of the degree of excellence with respect to time. Now this parameter needs the prediction of error level and degree of excellence at a particular stage of development of the software. This paper explores an attempt to develop a system to predict rate of improvement of the software quality at a particular point of time with respect to the number of lines of code present in the software. Having calculated the error level and degree of excellence at two points in time, we can move forward towards the estimation of the rate of improvement of the software quality with respect to time. This parameter can estimate the effort put in while development of the software and can add a new dimension to the understanding of software quality in software engineering domain. In order to obtain the results we have used an indigenous tool for software quality prediction and for graphical representation of data, we have used Microsoft office 2007 graphical chart.
Training-Free Non-Intrusive Load Monitoring of Electric Vehicle Charging with Low Sampling Rate
Venue: arXiv cs.OH 2014
Year: 2014

Non-intrusive load monitoring (NILM) is an important topic in smart-grid and smart-home. Many energy disaggregation algorithms have been proposed to detect various individual appliances from one aggregated signal observation. However, few works studied the energy disaggregation of plug-in electric vehicle (EV) charging in the residential environment since EVs charging at home has emerged only recently. Recent studies showed that EV charging has a large impact on smart-grid especially in summer. Therefore, EV charging monitoring has become a more important and urgent missing piece in energy disaggregation. In this paper, we present a novel method to disaggregate EV charging signals from aggregated real power signals. The proposed method can effectively mitigate interference coming from air-conditioner (AC), enabling accurate EV charging detection and energy estimation under the presence of AC power signals. Besides, the proposed algorithm requires no training, demands a light computational load, delivers high estimation accuracy, and works well for data recorded at the low sampling rate 1/60 Hz. When the algorithm is tested on real-world data recorded from 11 houses over about a whole year (total 125 months worth of data), the averaged error in estimating energy consumption of EV charging is 15.7 kwh/month (while the true averaged energy consumption of EV charging is 208.5 kwh/month), and the averaged normalized mean square error in disaggregating EV charging load signals is 0.19.
Local Rank Modulation for Flash Memories II
Venue: arXiv cs.IT 2014
Year: 2014

Local rank modulation scheme was suggested recently for representing information in flash memories in order to overcome drawbacks of rank modulation. For $0 < s\leq t\leq n$ with $s$ divides $n$, an $(s,t,n)$-LRM scheme is a local rank modulation scheme where the $n$ cells are locally viewed cyclically through a sliding window of size $t$ resulting in a sequence of small permutations which requires less comparisons and less distinct values. The gap between two such windows equals to $s$. In this work, encoding, decoding, and asymptotic enumeration of the $(1,3,n)$-LRM scheme is studied. The techniques which are suggested have some generalizations for $(1,t,n)$-LRM, $t > 3$, but the proofs will become more complicated. The enumeration problem is presented also as a purely combinatorial problem. Finally, we prove the conjecture that the size of a constant weight $(1,2,n)$-LRM Gray code with weight two is at most $2n$.
The predictable degree property, column reducedness, and minimality in multidimensional convolutional coding
Venue: arXiv cs.IT 2014
Year: 2014

Higher-dimensional analogs of the predictable degree property and column reducedness are defined, and it is proved that the two properties are equivalent. It is shown that every multidimensional convolutional code has, what is called, a minimal reduced polynomial resolution. It is uniquely determined (up to isomorphism) and leads to a number of important integer invariants of the code generalizing classical Forney's indices.
Spectrum Sensing with Small-Sized Datasets in Cognitive Radio: Algorithms and Analysis
Venue: arXiv cs.NI 2014
Year: 2014

Spectrum sensing is a fundamental component of cognitive radio. How to promptly sense the presence of primary users is a key issue to a cognitive radio network. The time requirement is critical in that violating it will cause harmful interference to the primary user, leading to a system-wide failure. The motivation of our work is to provide an effective spectrum sensing method to detect primary users as soon as possible. In the language of streaming based real-time data processing, short-time means small-sized data. In this paper, we propose a cumulative spectrum sensing method dealing with limited sized data. A novel method of covariance matrix estimation is utilized to approximate the true covariance matrix. The theoretical analysis is derived based on concentration inequalities and random matrix theory to support the claims of detection performance. Comparisons between the proposed method and other traditional approaches, judged by the simulation using a captured digital TV signal, show that this proposed method can operate either using smaller-sized data or working under lower SNR environment.
Linking Geographic Vocabularies through WordNet
Venue: arXiv cs.IR 2014
Year: 2014

The linked open data (LOD) paradigm has emerged as a promising approach to structuring and sharing geospatial information. One of the major obstacles to this vision lies in the difficulties found in the automatic integration between heterogeneous vocabularies and ontologies that provides the semantic backbone of the growing constellation of open geo-knowledge bases. In this article, we show how to utilize WordNet as a semantic hub to increase the integration of LOD. With this purpose in mind, we devise Voc2WordNet, an unsupervised mapping technique between a given vocabulary and WordNet, combining intensional and extensional aspects of the geographic terms. Voc2WordNet is evaluated against a sample of human-generated alignments with the OpenStreetMap (OSM) Semantic Network, a crowdsourced geospatial resource, and the GeoNames ontology, the vocabulary of a large digital gazetteer. These empirical results indicate that the approach can obtain high precision and recall.
A Polynomial Time Algorithm for Minimax-Regret Evacuation on a Dynamic Path
Venue: arXiv cs.DS 2014
Year: 2014

A dynamic path network is an undirected path with evacuees situated at each vertex. To evacuate the path, evacuees travel towards a designated sink (doorway) to exit. Each edge has a capacity, the number of evacuees that can enter the edge in unit time. Congestion occurs if an evacuee has to wait at a vertex for other evacuees to leave first. The basic problem is to place k sinks on the line, with an associated evacuation strategy, so as to minimize the total time needed to evacuate everyone. The minmax-regret version introduces uncertainty into the input, with the number of evacuees at vertices only being specified to within a range. The problem is to find a universal solution whose regret (difference from optimal for a given input) is minimized over all legal inputs. The previously best known algorithms for the minmax regret version problem ran in time exponential in k. In this paper, we derive new prop- erties of solutions that yield the first polynomial time algorithms for solving the problem.
Complex Workflow Management and Integration of Distributed Computing Resources by Science Gateway Portal for Molecular Dynamics Simulations in Materials Science
Venue: arXiv cs.CE 2014
Year: 2014

The "IMP Science Gateway Portal" (http://scigate.imp.kiev.ua) for complex workflow management and integration of distributed computing resources (like clusters, service grids, desktop grids, clouds) is presented. It is created on the basis of WS-PGRADE and gUSE technologies, where WS-PGRADE is designed for science workflow operation and gUSE - for smooth integration of available resources for parallel and distributed computing in various heterogeneous distributed computing infrastructures (DCI). The typical scientific workflow with possible scenarios of its preparation and usage is considered. Several typical science applications (scientific workflows) are considered for molecular dynamics (MD) simulations of complex behavior of various nanostructures (nanoindentation of graphene layers, defect system relaxation in metal nanocrystals, thermal stability of boron nitride nanotubes, etc.). The advantages and drawbacks of the solution are shortly analyzed in the context of its practical applications for MD simulations in materials science, physics and nanotechnologies with available heterogeneous DCIs.
Combining pattern-based CRFs and weighted context-free grammars
Venue: arXiv cs.FL 2014
Year: 2014

We consider two models for the sequence labeling (tagging) problem. The first one is a {\em Pattern-Based Conditional Random Field }(\PB), in which the energy of a string (chain labeling) $x=x_1\ldots x_n\in D^n$ is a sum of terms over intervals $[i,j]$ where each term is non-zero only if the substring $x_i\ldots x_j$ equals a prespecified word $w\in Λ$. The second model is a {\em Weighted Context-Free Grammar }(\WCFG) frequently used for natural language processing. \PB and \WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary. We propose a {\em Grammatical Pattern-Based CRF model }(\GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the {\em Hybrid model} of Bened{í} and Sanchez that combines {\em $\mbox{$N$-grams}$} and \WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a \GPB such as computing MAP. We present a polynomial-time algorithm for general \GPBs and a faster version for a special case that we call {\em Interaction Grammars}.
Polar Codes for Distributed Hierarchical Source Coding
Venue: arXiv cs.IT 2014
Year: 2014

We show that polar codes can be used to achieve the rate-distortion functions in the problem of hierarchical source coding also known as the successive refinement problem. We also analyze the distributed version of this problem, constructing a polar coding scheme that achieves the rate distortion functions for successive refinement with side information.
The condensation phase transition in random graph coloring
Venue: arXiv cs.DM 2014
Year: 2014

Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random $k$-SAT or random graph $k$-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called "condensation" [Krzakala et al., PNAS 2007]. The existence of this phase transition appears to be intimately related to the difficulty of proving precise results on, e.g., the $k$-colorability threshold as well as to the performance of message passing algorithms. In random graph $k$-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture for $k$ exceeding a certain constant $k_0$.
A Computationally Efficient Limited Memory CMA-ES for Large Scale Optimization
Venue: arXiv cs.NE 2014
Year: 2014

We propose a computationally efficient limited memory Covariance Matrix Adaptation Evolution Strategy for large scale optimization, which we call the LM-CMA-ES. The LM-CMA-ES is a stochastic, derivative-free algorithm for numerical optimization of non-linear, non-convex optimization problems in continuous domain. Inspired by the limited memory BFGS method of Liu and Nocedal (1989), the LM-CMA-ES samples candidate solutions according to a covariance matrix reproduced from $m$ direction vectors selected during the optimization process. The decomposition of the covariance matrix into Cholesky factors allows to reduce the time and memory complexity of the sampling to $O(mn)$, where $n$ is the number of decision variables. When $n$ is large (e.g., $n$ > 1000), even relatively small values of $m$ (e.g., $m=20,30$) are sufficient to efficiently solve fully non-separable problems and to reduce the overall run-time.