OpenRaiser/Intern-Atlas huggingface dataset:
A Novel Probabilistic Pruning Approach to Speed Up Similarity Queries in Uncertain Databases
Venue: arXiv cs.DB 2011
Year: 2011

In this paper, we propose a novel, effective and efficient probabilistic pruning criterion for probabilistic similarity queries on uncertain data. Our approach supports a general uncertainty model using continuous probabilistic density functions to describe the (possibly correlated) uncertain attributes of objects. In a nutshell, the problem to be solved is to compute the PDF of the random variable denoted by the probabilistic domination count: Given an uncertain database object B, an uncertain reference object R and a set D of uncertain database objects in a multi-dimensional space, the probabilistic domination count denotes the number of uncertain objects in D that are closer to R than B. This domination count can be used to answer a wide range of probabilistic similarity queries. Specifically, we propose a novel geometric pruning filter and introduce an iterative filter-refinement strategy for conservatively and progressively estimating the probabilistic domination count in an efficient way while keeping correctness according to the possible world semantics. In an experimental evaluation, we show that our proposed technique allows to acquire tight probability bounds for the probabilistic domination count quickly, even for large uncertain databases.
Energy-Efficient Design and Optimization of Wireline Access Networks
Venue: arXiv cs.NI 2011
Year: 2011

Access networks, in particular, Digital Subscriber Line (DSL) equipment, are a significant source of energy consumption for wireline operators. Replacing large monolithic DSLAMs with smaller remote DSLAM units closer to customers can reduce the energy consumption as well as increase the reach of the access network. This paper attempts to formalize the design and optimization of the "last mile" wireline access network with energy as one of the costs to be minimized. In particular, the placement of remote DSLAM units needs to be optimized. We propose solutions for two scenarios. For the scenario where an existing all-copper network from the central office to the customers is to be transformed into a fiber-copper network with remote DSLAM units, we present optimal polynomial-time solutions. In the green-field scenario, both the access network layout and the placement of remote DSLAM units must be determined. We show that this problem is NP-complete. We present an optimal ILP formulation and also design an efficient heuristic-based approach to build a power-and-cost-optimized access network. Our heuristic-based approach yields results that are very close to optimal. We show how the power consumption of the access network can be reduced by carefully laying the access network and introducing remote DSLAM units.
Optimized data sharing in multicell MIMO with finite backhaul capacity
Venue: arXiv cs.IT 2011
Year: 2011

This paper addresses cooperation in a multicell environment where base stations (BSs) wish to jointly serve multiple users, under a constrained-capacity backhaul. We point out that for finite backhaul capacity a trade-off between sharing user data, which allows for full MIMO cooperation, and not doing so, which reduces the setup to an interference channel but also requires less overhead, emerges. We optimize this trade-off by formulating a rate splitting approach in which non-shared data (private to each transmitter) and shared data are superposed. We derive the corresponding achievable rate region and obtain the optimal beamforming design for both shared and private symbols. We show how the capacity of the backhaul can be used to determine how much of the user data is worth sharing across multiple BSs, particularly depending on how strong the interference is.
A Refined Denominator Bounding Algorithm for Multivariate Linear Difference Equations
Venue: arXiv cs.SC 2011
Year: 2011

We continue to investigate which polynomials can possibly occur as factors in the denominators of rational solutions of a given partial linear difference equation. In an earlier article we had introduced the distinction between periodic and aperiodic factors in the denominator, and we gave an algorithm for predicting the aperiodic ones. Now we extend this technique towards the periodic case and present a refined algorithm which also finds most of the periodic factors.
Formal Verification of Differential Privacy for Interactive Systems
Venue: arXiv cs.CR 2011
Year: 2011

Differential privacy is a promising approach to privacy preserving data analysis with a well-developed theory for functions. Despite recent work on implementing systems that aim to provide differential privacy, the problem of formally verifying that these systems have differential privacy has not been adequately addressed. This paper presents the first results towards automated verification of source code for differentially private interactive systems. We develop a formal probabilistic automaton model of differential privacy for systems by adapting prior work on differential privacy for functions. The main technical result of the paper is a sound proof technique based on a form of probabilistic bisimulation relation for proving that a system modeled as a probabilistic automaton satisfies differential privacy. The novelty lies in the way we track quantitative privacy leakage bounds using a relation family instead of a single relation. We illustrate the proof technique on a representative automaton motivated by PINQ, an implemented system that is intended to provide differential privacy. To make our proof technique easier to apply to realistic systems, we prove a form of refinement theorem and apply it to show that a refinement of the abstract PINQ automaton also satisfies our differential privacy definition. Finally, we begin the process of automating our proof technique by providing an algorithm for mechanically checking a restricted class of relations from the proof technique.
The Theory of Intervention Games for Resource Sharing in Wireless Communications
Venue: arXiv cs.GT 2011
Year: 2011

This paper develops a game-theoretic framework for the design and analysis of a new class of incentive schemes called intervention schemes. We formulate intervention games, propose a solution concept of intervention equilibrium, and prove its existence in a finite intervention game. We apply our framework to resource sharing scenarios in wireless communications, whose non-cooperative outcomes without intervention yield suboptimal performance. We derive analytical results and analyze illustrative examples in the cases of imperfect and perfect monitoring. In the case of imperfect monitoring, intervention schemes can improve the suboptimal performance of non-cooperative equilibrium when the intervention device has a sufficiently accurate monitoring technology, although it may not be possible to achieve the best feasible performance. In the case of perfect monitoring, the best feasible performance can be obtained with an intervention scheme when the intervention device has a sufficiently strong intervention capability.
Wiselib: A Generic Algorithm Library for Heterogeneous Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

One unfortunate consequence of the success story of wireless sensor networks (WSNs) in separate research communities is an ever-growing gap between theory and practice. Even though there is a increasing number of algorithmic methods for WSNs, the vast majority has never been tried in practice; conversely, many practical challenges are still awaiting efficient algorithmic solutions. The main cause for this discrepancy is the fact that programming sensor nodes still happens at a very technical level. We remedy the situation by introducing Wiselib, our algorithm library that allows for simple implementations of algorithms onto a large variety of hardware and software. This is achieved by employing advanced C++ techniques such as templates and inline functions, allowing to write generic code that is resolved and bound at compile time, resulting in virtually no memory or computation overhead at run time. The Wiselib runs on different host operating systems, such as Contiki, iSense OS, and ScatterWeb. Furthermore, it runs on virtual nodes simulated by Shawn. For any algorithm, the Wiselib provides data structures that suit the specific properties of the target platform. Algorithm code does not contain any platform-specific specializations, allowing a single implementation to run natively on heterogeneous networks. In this paper, we describe the building blocks of the Wiselib, and analyze the overhead. We demonstrate the effectiveness of our approach by showing how routing algorithms can be implemented. We also report on results from experiments with real sensor-node hardware.
Experimental Performance Evaluation of Location Distinction for MIMO Channels
Venue: arXiv cs.NI 2011
Year: 2011

Location distinction is defined as determining whether or not the position of a device has changed. We introduce methods and metrics for performing location distinction in multiple-input multiple-output (MIMO) wireless networks. Using MIMO channel measurements from two different testbeds, we evaluate the performance of temporal signature-based location distinction with varying system parameters, and show that it can be applied to MIMO channels with favorable results. In particular, a 2x2 MIMO channel with a bandwidth of 80 MHz allows a 64-fold reduction in miss rate over the SISO channel for a fixed false alarm rate, achieving as small as 4 x 10^-4 probability of false alarm for a 2.4 x 10^-4 probability of missed detection. The very high reliability of MIMO location distinction enables location distinction systems to detect the change in position of a transmitter even when using a single receiver.
Ensuring Correctness at the Application Level: a Software Framework Approach
Venue: arXiv cs.SE 2011
Year: 2011

As scientific applications extend to the simulation of more and more complex systems, they involve an increasing number of abstraction levels, at each of which errors can emerge and across which they can propagate; tools for correctness evaluation and enforcement at every level (from the code level to the application level) are therefore necessary. Whilst code-level debugging tools are already a well established standard, application-level tools are lagging behind, possibly due to their stronger dependence on the application's details. In this paper, we describe the programming model introduced by the Cactus framework, review the High Performance Computing (HPC) challenges that Cactus is designed to address, and illustrate the correctness strategies that are currently available in Cactus at the code, component, and application level.
Generalized Belief Propagation for the Noiseless Capacity and Information Rates of Run-Length Limited Constraints
Venue: arXiv cs.IT 2011
Year: 2011

The performance of the generalized belief propagation algorithm for computing the noiseless capacity and mutual information rates of finite-size two-dimensional and three-dimensional run-length limited constraints is investigated. For each constraint, a method is proposed to choose the basic regions and to construct the region graph. Simulation results for the capacity of different constraints as a function of the size of the channel and mutual information rates of different constraints as a function of signal-to-noise ratio are reported. Convergence to the Shannon capacity is also discussed.
Node Classification in Social Networks
Venue: arXiv cs.SI 2011
Year: 2011

When dealing with large graphs, such as those that arise in the context of online social networks, a subset of nodes may be labeled. These labels can indicate demographic values, interest, beliefs or other characteristics of the nodes (users). A core problem is to use this information to extend the labeling so that all nodes are assigned a label (or labels). In this chapter, we survey classification techniques that have been proposed for this problem. We consider two broad categories: methods based on iterative application of traditional classifiers using graph information as features, and methods which propagate the existing labels via random walks. We adopt a common perspective on these methods to highlight the similarities between different approaches within and across the two categories. We also describe some extensions and related directions to the central problem of node classification.
Structured sublinear compressive sensing via belief propagation
Venue: arXiv cs.IT 2011
Year: 2011

Compressive sensing (CS) is a sampling technique designed for reducing the complexity of sparse data acquisition. One of the major obstacles for practical deployment of CS techniques is the signal reconstruction time and the high storage cost of random sensing matrices. We propose a new structured compressive sensing scheme, based on codes of graphs, that allows for a joint design of structured sensing matrices and logarithmic-complexity reconstruction algorithms. The compressive sensing matrices can be shown to offer asymptotically optimal performance when used in combination with Orthogonal Matching Pursuit (OMP) methods. For more elaborate greedy reconstruction schemes, we propose a new family of list decoding belief propagation algorithms, as well as reinforced- and multiple-basis belief propagation algorithms. Our simulation results indicate that reinforced BP CS schemes offer very good complexity-performance tradeoffs for very sparse signal vectors.
A Generalized Criterion for Signature Related Gröbner Basis Algorithms
Venue: arXiv cs.SC 2011
Year: 2011

A generalized criterion for signature related algorithms to compute Gröbner basis is proposed in this paper. Signature related algorithms are a popular kind of algorithms for computing Gröbner basis, including the famous F5 algorithm, the extended F5 algorithm and the GVW algorithm. The main purpose of current paper is to study in theory what kind of criteria is correct in signature related algorithms and provide a generalized method to develop new criteria. For this purpose, a generalized criterion is proposed. The generalized criterion only relies on a general partial order defined on a set of polynomials. When specializing the partial order to appropriate specific orders, the generalized criterion can specialize to almost all existing criteria of signature related algorithms. For {\em admissible} partial orders, a complete proof of the correctness of the algorithm based on this generalized criterion is also presented. This proof has no extra requirements on the computing order of critical pairs, and is also valid for non-homogeneous polynomial systems. More importantly, the partial orders implied by existing criteria are admissible. Besides, one can also check whether a new criterion is correct in signature related algorithms or even develop new criteria by using other admissible partial orders in the generalized criterion.
Multi-objective Optimization For The Dynamic Multi-Pickup and Delivery Problem with Time Windows
Venue: arXiv cs.DS 2011
Year: 2011

The PDPTW is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence, capacity and time constraints. We present, in this paper, a genetic algorithm for multi-objective optimization of a dynamic multi pickup and delivery problem with time windows (Dynamic m-PDPTW). We propose a brief literature review of the PDPTW, present our approach based on Pareto dominance method and lower bounds, to give a satisfying solution to the Dynamic m-PDPTW minimizing the compromise between total travel cost and total tardiness time. Computational results indicate that the proposed algorithm gives good results with a total tardiness equal to zero with a tolerable cost.
New Quadriphase Sequences families with Larger Linear Span and Size
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, new families of quadriphase sequences with larger linear span and size have been proposed and studied. In particular, a new family of quadriphase sequences of period $2^n-1$ for a positive integer $n=em$ with an even positive factor $m$ is presented, the cross-correlation function among these sequences has been explicitly calculated. Another new family of quadriphase sequences of period $2(2^n-1)$ for a positive integer $n=em$ with an even positive factor $m$ is also presented, a detailed analysis of the cross-correlation function of proposed sequences has also been presented.
Model Checking of Continuous-Time Markov Chains Against Timed Automata Specifications
Venue: arXiv cs.LO 2011
Year: 2011

We study the verification of a finite continuous-time Markov chain (CTMC) C against a linear real-time specification given as a deterministic timed automaton (DTA) A with finite or Muller acceptance conditions. The central question that we address is: what is the probability of the set of paths of C that are accepted by A, i.e., the likelihood that C satisfies A? It is shown that under finite acceptance criteria this equals the reachability probability in a finite piecewise deterministic Markov process (PDP), whereas for Muller acceptance criteria it coincides with the reachability probability of terminal strongly connected components in such a PDP. Qualitative verification is shown to amount to a graph analysis of the PDP. Reachability probabilities in our PDPs are then characterized as the least solution of a system of Volterra integral equations of the second type and are shown to be approximated by the solution of a system of partial differential equations. For single-clock DTA, this integral equation system can be transformed into a system of linear equations where the coefficients are solutions of ordinary differential equations. As the coefficients are in fact transient probabilities in CTMCs, this result implies that standard algorithms for CTMC analysis suffice to verify single-clock DTA specifications.
Estimating the Average of a Lipschitz-Continuous Function from One Sample
Venue: arXiv cs.DS 2011
Year: 2011

We study the problem of estimating the average of a Lipschitz continuous function $f$ defined over a metric space, by querying $f$ at only a single point. More specifically, we explore the role of randomness in drawing this sample. Our goal is to find a distribution minimizing the expected estimation error against an adversarially chosen Lipschitz continuous function. Our work falls into the broad class of estimating aggregate statistics of a function from a small number of carefully chosen samples. The general problem has a wide range of practical applications in areas as diverse as sensor networks, social sciences and numerical analysis. However, traditional work in numerical analysis has focused on asymptotic bounds, whereas we are interested in the \emph{best} algorithm. For arbitrary discrete metric spaces of bounded doubling dimension, we obtain a PTAS for this problem. In the special case when the points lie on a line, the running time improves to an FPTAS. Both algorithms are based on approximately solving a linear program with an infinite set of constraints, by using an approximate separation oracle. For Lipschitz-continuous functions over $[0,1]$, we calculate the precise achievable error as $1-\frac{\sqrt{3}}{2} \approx 0.134$, which improves upon the \quarter which is best possible for deterministic algorithms.
OSPF Weight Setting Optimization for Single Link Failures
Venue: arXiv cs.NI 2011
Year: 2011

In operational networks, nodes are connected via multiple links for load sharing and redundancy. This is done to make sure that a failure of a link does not disconnect or isolate some parts of the network. However, link failures have an effect on routing, as the routers find alternate paths for the traffic originally flowing through the link which has failed. This effect is severe in case of failure of a critical link in the network, such as backbone links or the links carrying higher traffic loads. When routing is done using the Open Shortest Path First (OSPF) routing protocol, the original weight selection for the normal state topology may not be as efficient for the failure state. In this paper, we investigate the single link failure issue with an objective to find a weight setting which results in efficient routing in normal and failure states. We engineer Tabu Search Iterative heuristic using two different implementation strategies to solve the OSPF weight setting problem for link failure scenarios. We evaluate these heuristics and show through experimental results that both heuristics efficiently handle weight setting for the failure state. A comparison of both strategies is also presented.
Turning the tables in citation analysis one more time: Principles for comparing sets of documents
Venue: arXiv cs.DL 2011
Year: 2011

We submit newly developed citation impact indicators based not on arithmetic averages of citations but on percentile ranks. Citation distributions are-as a rule-highly skewed and should not be arithmetically averaged. With percentile ranks, the citation of each paper is rated in terms of its percentile in the citation distribution. The percentile ranks approach allows for the formulation of a more abstract indicator scheme that can be used to organize and/or schematize different impact indicators according to three degrees of freedom: the selection of the reference sets, the evaluation criteria, and the choice of whether or not to define the publication sets as independent. Bibliometric data of seven principal investigators (PIs) of the Academic Medical Center of the University of Amsterdam is used as an exemplary data set. We demonstrate that the proposed indicators [R(6), R(100), R(6,k), R(100,k)] are an improvement of averages-based indicators because one can account for the shape of the distributions of citations over papers.
Secure Multiplex Coding with a Common Message
Venue: arXiv cs.IT 2011
Year: 2011

We determine the capacity region of the secure multiplex coding with a common message, and evaluate the mutual information and the equivocation rate of a collection of secret messages to the second receiver (eavesdropper), which were not evaluated by Yamamoto et al.
Linear-Space Data Structures for Range Mode Query in Arrays
Venue: arXiv cs.DS 2011
Year: 2011

A mode of a multiset $S$ is an element $a \in S$ of maximum multiplicity; that is, $a$ occurs at least as frequently as any other element in $S$. Given a list $A[1:n]$ of $n$ items, we consider the problem of constructing a data structure that efficiently answers range mode queries on $A$. Each query consists of an input pair of indices $(i, j)$ for which a mode of $A[i:j]$ must be returned. We present an $O(n^{2-2ε})$-space static data structure that supports range mode queries in $O(n^ε)$ time in the worst case, for any fixed $ε\in [0,1/2]$. When $ε= 1/2$, this corresponds to the first linear-space data structure to guarantee $O(\sqrt{n})$ query time. We then describe three additional linear-space data structures that provide $O(k)$, $O(m)$, and $O(|j-i|)$ query time, respectively, where $k$ denotes the number of distinct elements in $A$ and $m$ denotes the frequency of the mode of $A$. Finally, we examine generalizing our data structures to higher dimensions.