OpenRaiser/Intern-Atlas huggingface dataset:
Succinct Coverage Oracles
Venue: arXiv cs.DS 2010
Year: 2010

In this paper, we identify a fundamental algorithmic problem that we term succinct dynamic covering (SDC), arising in many modern-day web applications, including ad-serving and online recommendation systems in eBay and Netflix. Roughly speaking, SDC applies two restrictions to the well-studied Max-Coverage problem: Given an integer k, X={1,2,...,n} and I={S_1, ..., S_m}, S_i a subset of X, find a subset J of I, such that |J| <= k and the union of S in J is as large as possible. The two restrictions applied by SDC are: (1) Dynamic: At query-time, we are given a query Q, a subset of X, and our goal is to find J such that the intersection of Q with the union of S in J is as large as possible; (2) Space-constrained: We don't have enough space to store (and process) the entire input; specifically, we have o(mn), and maybe as little as O((m+n)polylog(mn)) space. The goal of SDC is to maintain a small data structure so as to answer most dynamic queries with high accuracy. We call such a scheme a Coverage Oracle. We present algorithms and complexity results for coverage oracles. We present deterministic and probabilistic near-tight upper and lower bounds on the approximation ratio of SDC as a function of the amount of space available to the oracle. Our lower bound results show that to obtain constant-factor approximations we need Omega(mn) space. Fortunately, our upper bounds present an explicit tradeoff between space and approximation ratio, allowing us to determine the amount of space needed to guarantee certain accuracy.
Towards Utility-driven Anonymization of Transactions
Venue: arXiv cs.DB 2010
Year: 2010

Publishing person-specific transactions in an anonymous form is increasingly required by organizations. Recent approaches ensure that potentially identifying information (e.g., a set of diagnosis codes) cannot be used to link published transactions to persons' identities, but all are limited in application because they incorporate coarse privacy requirements (e.g., protecting a certain set of m diagnosis codes requires protecting all m-sized sets), do not integrate utility requirements, and tend to explore a small portion of the solution space. In this paper, we propose a more general framework for anonymizing transactional data under specific privacy and utility requirements. We model such requirements as constraints, investigate how these constraints can be specified, and propose COAT (COnstraint-based Anonymization of Transactions), an algorithm that anonymizes transactions using a flexible hierarchy-free generalization scheme to meet the specified constraints. Experiments with benchmark datasets verify that COAT significantly outperforms the current state-of-the-art algorithm in terms of data utility, while being comparable in terms of efficiency. The effectiveness of our approach is also demonstrated in a real-world scenario, which requires disseminating a private, patient-specific transactional dataset in a way that preserves both privacy and utility in intended studies.
On the theory of moveable objects
Venue: arXiv cs.HC 2010
Year: 2010

User-driven applications belong to the new type of programs, in which users get the full control of WHAT, WHEN, and HOW must appear on the screen. Such programs can exist only if the screen view is organized not according with the predetermined scenario, written by the developers, but if any screen object can be moved, resized, and reconfigured by any user at any moment. This article describes the algorithm, by which an object of an arbitrary shape can be turned into moveable and resizable. It also explains some rules of such design and the technique, which can be useful in many cases. Both the individual movements of objects and their synchronous movements are analysed. After discussing the individually moveable controls, different types of groups are analysed and the arbitrary grouping of controls is considered.
Relaxed spanners for directed disk graphs
Venue: arXiv cs.DS 2010
Year: 2010

Let $(V,δ)$ be a finite metric space, where $V$ is a set of $n$ points and $δ$ is a distance function defined for these points. Assume that $(V,δ)$ has a constant doubling dimension $d$ and assume that each point $p\in V$ has a disk of radius $r(p)$ around it. The disk graph that corresponds to $V$ and $r(\cdot)$ is a \emph{directed} graph $I(V,E,r)$, whose vertices are the points of $V$ and whose edge set includes a directed edge from $p$ to $q$ if $δ(p,q)\leq r(p)$. In \cite{PeRo08} we presented an algorithm for constructing a $(1+\eps)$-spanner of size $O(n/\eps^d \log M)$, where $M$ is the maximal radius $r(p)$. The current paper presents two results. The first shows that the spanner of \cite{PeRo08} is essentially optimal, i.e., for metrics of constant doubling dimension it is not possible to guarantee a spanner whose size is independent of $M$. The second result shows that by slightly relaxing the requirements and allowing a small perturbation of the radius assignment, considerably better spanners can be constructed. In particular, we show that if it is allowed to use edges of the disk graph $I(V,E,r_{1+\eps})$, where $r_{1+\eps}(p) = (1+\eps)\cdot r(p)$ for every $p\in V$, then it is possible to get a $(1+\eps)$-spanner of size $O(n/\eps^d)$ for $I(V,E,r)$. Our algorithm is simple and can be implemented efficiently.
Decidability of the interval temporal logic ABBar over the natural numbers
Venue: arXiv cs.LO 2010
Year: 2010

In this paper, we focus our attention on the interval temporal logic of the Allen's relations "meets", "begins", and "begun by" (ABBar for short), interpreted over natural numbers. We first introduce the logic and we show that it is expressive enough to model distinctive interval properties,such as accomplishment conditions, to capture basic modalities of point-based temporal logic, such as the until operator, and to encode relevant metric constraints. Then, we prove that the satisfiability problem for ABBar over natural numbers is decidable by providing a small model theorem based on an original contraction method. Finally, we prove the EXPSPACE-completeness of the problem
A Survey of Paraphrasing and Textual Entailment Methods
Venue: arXiv cs.CL 2010
Year: 2010

Paraphrasing methods recognize, generate, or extract phrases, sentences, or longer natural language expressions that convey almost the same information. Textual entailment methods, on the other hand, recognize, generate, or extract pairs of natural language expressions, such that a human who reads (and trusts) the first element of a pair would most likely infer that the other element is also true. Paraphrasing can be seen as bidirectional textual entailment and methods from the two areas are often similar. Both kinds of methods are useful, at least in principle, in a wide range of natural language processing applications, including question answering, summarization, text generation, and machine translation. We summarize key ideas from the two areas by considering in turn recognition, generation, and extraction methods, also pointing to prominent articles and resources.
A Simplified Proof For The Application Of Freivalds' Technique to Verify Matrix Multiplication
Venue: arXiv cs.DS 2010
Year: 2010

Fingerprinting is a well known technique, which is often used in designing Monte Carlo algorithms for verifying identities involving ma- trices, integers and polynomials. The book by Motwani and Raghavan [1] shows how this technique can be applied to check the correctness of matrix multiplication -- check if AB = C where A, B and C are three nxn matrices. The result is a Monte Carlo algorithm running in time $Theta(n^2)$ with an exponentially decreasing error probability after each indepen- dent iteration. In this paper we give a simple alternate proof addressing the same problem. We also give further generalizations and relax various assumptions made in the proof.
Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies
Venue: arXiv cs.LO 2010
Year: 2010

We study normalising reduction strategies for infinitary Combinatory Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs. These facts properly generalise a number of results on normalising strategies in first-order infinitary rewriting and provide the first examples of normalising strategies for infinitary lambda calculus.
1-State Error-Trellis Decoding of LDPC Convolutional Codes Based on Circulant Matrices
Venue: arXiv cs.IT 2010
Year: 2010

We consider the decoding of convolutional codes using an error trellis constructed based on a submatrix of a given check matrix. In the proposed method, the syndrome-subsequence computed using the remaining submatrix is utilized as auxiliary information for decoding. Then the ML error path is correctly decoded using the degenerate error trellis. We also show that the decoding complexity of the proposed method is basically identical with that of the conventional one based on the original error trellis. Next, we apply the method to check matrices with monomial entries proposed by Tanner et al. By choosing any row of the check matrix as the submatrix for error-trellis construction, a 1-state error trellis is obtained. Noting the fact that a likelihood-concentration on the all-zero state and the states with many 0's occurs in the error trellis, we present a simplified decoding method based on a 1-state error trellis, from which decoding-complexity reduction is realized.
High-Speed Signature Matching in Network Interface Device using Bloom Filters
Venue: arXiv cs.NI 2010
Year: 2010

Network intrusion detection systems play a critical role in protecting the information infrastructure of an organization. Due to the sophistication and complexity of techniques used for the analysis they are commonly based on general-purpose workstations. Although cost-efficient, these general-purpose systems are found to be inadequate as they are unable to perform efficiently at high packet rates. The resulting packet loss degrades the system's overall effectiveness, as the analyzing capability of the system is reduced. It has been found that the performance of these sensors can be improved significantly by filtering out unwanted packets. This paper presents the design of a Programmable Ethernet Interface Card that is used to offload signature matching from software and thereby improve the detection ratio and performance of the system.
A distributed file system for a wide-area high performance computing infrastructure
Venue: arXiv cs.DC 2010
Year: 2010

We describe our work in implementing a wide-area distributed file system for the NSF TeraGrid. The system, called XUFS, allows private distributed name spaces to be created for transparent access to personal files across over 9000 computer nodes. XUFS builds on many principles from prior distributed file systems research, but extends key design goals to support the workflow of computational science researchers. Specifically, XUFS supports file access from the desktop to the wide-area network seamlessly, survives transient disconnected operations robustly, and demonstrates comparable or better throughput than some current high performance file systems on the wide-area network.
The Traveling Salesman Problem Under Squared Euclidean Distances
Venue: arXiv cs.CG 2010
Year: 2010

Let $P$ be a set of points in $\mathbb{R}^d$, and let $α\ge 1$ be a real number. We define the distance between two points $p,q\in P$ as $|pq|^α$, where $|pq|$ denotes the standard Euclidean distance between $p$ and $q$. We denote the traveling salesman problem under this distance function by TSP($d,α$). We design a 5-approximation algorithm for TSP(2,2) and generalize this result to obtain an approximation factor of $3^{α-1}+\sqrt{6}^α/3$ for $d=2$ and all $α\ge2$. We also study the variant Rev-TSP of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-TSP$(2,α)$ with $α\ge2$, and we show that Rev-TSP$(d, α)$ is APX-hard if $d\ge3$ and $α>1$. The APX-hardness proof carries over to TSP$(d, α)$ for the same parameter ranges.
Robust Image Watermarking in the Wavelet Domain for Copyright Protection
Venue: arXiv cs.IT 2010
Year: 2010

In this paper a new approach to image watermarking in wavelet domain is presented. The idea is to hide the watermark data in blocks of the block segmented image. Two schemes are presented based on this idea by embedding the watermark data in the low pass wavelet coefficients of each block. Due to low computational complexity of the proposed approach, this algorithm can be implemented in real time. Experimental results demonstrate the impercepti-bility of the proposed method and its high robustness against various attacks such as filtering, JPEG compres-sion, cropping, noise addition and geometric distortions.
A Complete Method for Checking Hurwitz Stability of a Polytope of Matrices
Venue: arXiv cs.SC 2010
Year: 2010

We present a novel method for checking the Hurwitz stability of a polytope of matrices. First we prove that the polytope matrix is stable if and only if two homogenous polynomials are positive on a simplex, then through a newly proposed method, i.e., the weighted difference substitution method, the latter can be checked in finite steps. Examples show the efficiency of our method.
Optimal Query Complexity for Reconstructing Hypergraphs
Venue: arXiv cs.LG 2010
Year: 2010

In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let $G$ be a weighted hidden hypergraph of constant rank with n vertices and $m$ hyperedges. For any $m$ there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O(\frac{m\log n}{\log m}) $$ additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. {\em STOC}, 749--758,~2008]. When the weights of the hypergraph are integers that are less than $O(poly(n^d/m))$ where $d$ is the rank of the hypergraph (and therefore for unweighted hypergraphs) there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O(\frac{m\log \frac{n^d}{m}}{\log m}). $$ additive queries. Using the information theoretic bound the above query complexities are tight.
A new Rational Generating Function for the Frobenius Coin Problem
Venue: arXiv cs.DM 2010
Year: 2010

An important question arising from the Frobenius Coin Problem is to decide whether or not a given monetary sum S can be obtained from N coin denominations. We develop a new Generating Function G(x), where the coefficient of x^i is equal to the number of ways in which coins from the given denominations can be arranged as a stack whose total monetary worth is i. We show that the Recurrence Relation for obtaining G(x), is linear, enabling G(x) to be expressed as a rational function, that is, G(x) = P(x)/Q(x), where both P(x) and Q(x) are Polynomials whose degrees are bounded by the largest coin denomination.
Modeling and Annotating the Expressive Semantics of Dance Videos
Venue: arXiv cs.MM 2010
Year: 2010

Dance videos are interesting and semantics-intensive. At the same time, they are the complex type of videos compared to all other types such as sports, news and movie videos. In fact, dance video is the one which is less explored by the researchers across the globe. Dance videos exhibit rich semantics such as macro features and micro features and can be classified into several types. Hence, the conceptual modeling of the expressive semantics of the dance videos is very crucial and complex. This paper presents a generic Dance Video Semantics Model (DVSM) in order to represent the semantics of the dance videos at different granularity levels, identified by the components of the accompanying song. This model incorporates both syntactic and semantic features of the videos and introduces a new entity type called, Agent, to specify the micro features of the dance videos. The instantiations of the model are expressed as graphs. The model is implemented as a tool using J2SE and JMF to annotate the macro and micro features of the dance videos. Finally examples and evaluation results are provided to depict the effectiveness of the proposed dance video model. Keywords: Agents, Dance videos, Macro features, Micro features, Video annotation, Video semantics.
RFID et nouvelles technologies de communication; enjeux économiques incontournables et problèmes d'éthique RFID and new communication technologies - economic challenges and ethic problems
Venue: arXiv cs.CY 2010
Year: 2010

Auto ID technologies such RFID are more and more commonly used in industry and in distribution. Human are identify thanks to this technology, too. A lot of people have highlighted ethic problems relative to their utilization. This paper present first RFID technology, then it presents their opportunities in business and industry. In a second part, the paper highlights some ethic problems leading to a necessary standardization and regulation.
Optimal Exploration of Terrains with Obstacles
Venue: arXiv cs.DS 2010
Year: 2010

A mobile robot represented by a point moving in the plane has to explore an unknown terrain with obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity O(P + D?k), where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity O(P + A + ?Ak), where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain T with obstacles is c-fat if R/r ? c, where R is the radius of the smallest disc containing T and r is the radius of the largest disc contained in T .) We also prove a matching lower bound ?(P + A + ?Ak) on the complexity of exploration for limited vision, even if the terrain is known to the robot.
Least and greatest fixpoints in game semantics
Venue: arXiv cs.LO 2010
Year: 2010

We show how solutions to many recursive arena equations can be computed in a natural way by allowing loops in arenas. We then equip arenas with winning functions and total winning strategies. We present two natural winning conditions compatible with the loop construction which respectively provide initial algebras and terminal coalgebras for a large class of continuous functors. Finally, we introduce an intuitionistic sequent calculus, extended with syntactic constructions for least and greatest fixed points, and prove it has a sound and (in a certain weak sense) complete interpretation in our game model.
Introducing Automated Regression Testing in Open Source Projects
Venue: arXiv cs.SE 2010
Year: 2010

To learn how to introduce automated regression testing to existing medium scale Open Source projects, a long-term field experiment was performed with the Open Source project FreeCol. Results indicate that (1) introducing testing is both beneficial for the project and feasible for an outside innovator, (2) testing can enhance communication between developers, (3) signaling is important for engaging the project participants to fill a newly vacant position left by a withdrawal of the innovator. Five prescriptive strategies are extracted for the innovator and two conjectures offered about the ability of an Open Source project to learn about innovations.
Alternation-Trading Proofs, Linear Programming, and Lower Bounds
Venue: arXiv cs.CC 2010
Year: 2010

A fertile area of recent research has demonstrated concrete polynomial time lower bounds for solving natural hard problems on restricted computational models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path, Mod6-SAT, Majority-of-Majority-SAT, and Tautologies, to name a few. The proofs of these lower bounds follow a certain proof-by-contradiction strategy that we call alternation-trading. An important open problem is to determine how powerful such proofs can possibly be. We propose a methodology for studying these proofs that makes them amenable to both formal analysis and automated theorem proving. We prove that the search for better lower bounds can often be turned into a problem of solving a large series of linear programming instances. Implementing a small-scale theorem prover based on this result, we extract new human-readable time lower bounds for several problems. This framework can also be used to prove concrete limitations on the current techniques.
Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graph
Venue: arXiv cs.DS 2010
Year: 2010

Let $G=(V,E)$ be any undirected graph on $V$ vertices and $E$ edges. A path $\textbf{P}$ between any two vertices $u,v\in V$ is said to be $t$-approximate shortest path if its length is at most $t$ times the length of the shortest path between $u$ and $v$. We consider the problem of building a compact data structure for a given graph $G$ which is capable of answering the following query for any $u,v,z\in V$ and $t>1$: Report $t$-approximate shortest path between $u$ and $v$ when vertex $z$ fails We present data structures for the single source as well all-pairs versions of this problem. Our data structures guarantee optimal query time. Most impressive feature of our data structures is that their size {\em nearly} match the size of their best static counterparts.
Document Clustering with K-tree
Venue: arXiv cs.IR 2010
Year: 2010

This paper describes the approach taken to the XML Mining track at INEX 2008 by a group at the Queensland University of Technology. We introduce the K-tree clustering algorithm in an Information Retrieval context by adapting it for document clustering. Many large scale problems exist in document clustering. K-tree scales well with large inputs due to its low complexity. It offers promising results both in terms of efficiency and quality. Document classification was completed using Support Vector Machines.
A Review of Wireless Body Area Networks for Medical Applications
Venue: arXiv cs.NI 2010
Year: 2010

Recent advances in Micro-Electro-Mechanical Systems (MEMS) technology, integrated circuits, and wireless communication have allowed the realization of Wireless Body Area Networks (WBANs). WBANs promise unobtrusive ambulatory health monitoring for a long period of time and provide real-time updates of the patient's status to the physician. They are widely used for ubiquitous healthcare, entertainment, and military applications. This paper reviews the key aspects of WBANs for numerous applications. We present a WBAN infrastructure that provides solutions to on-demand, emergency, and normal traffic. We further discuss in-body antenna design and low-power MAC protocol for WBAN. In addition, we briefly outline some of the WBAN applications with examples. Our discussion realizes a need for new power-efficient solutions towards in-body and on-body sensor networks.