OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Quality-Guaranteed Data Streaming in Resource-Constrained Sensor Networks
Venue: arXiv cs.DS 2008
Year: 2008

In many emerging applications, data streams are monitored in a network environment. Due to limited communication bandwidth and other resource constraints, a critical and practical demand is to online compress data streams continuously with quality guarantee. Although many data compression and digital signal processing methods have been developed to reduce data volume, their super-linear time and more-than-constant space complexity prevents them from being applied directly on data streams, particularly over resource-constrained sensor networks. In this paper, we tackle the problem of online quality guaranteed compression of data streams using fast linear approximation (i.e., using line segments to approximate a time series). Technically, we address two versions of the problem which explore quality guarantees in different forms. We develop online algorithms with linear time complexity and constant cost in space. Our algorithms are optimal in the sense they generate the minimum number of segments that approximate a time series with the required quality guarantee. To meet the resource constraints in sensor networks, we also develop a fast algorithm which creates connecting segments with very simple computation. The low cost nature of our methods leads to a unique edge on the applications of massive and fast streaming environment, low bandwidth networks, and heavily constrained nodes in computational power. We implement and evaluate our methods in the application of an acoustic wireless sensor network.
Informed stego-systems in active warden context: statistical undetectability and capacity
Venue: arXiv cs.IT 2008
Year: 2008

Several authors have studied stego-systems based on Costa scheme, but just a few ones gave both theoretical and experimental justifications of these schemes performance in an active warden context. We provide in this paper a steganographic and comparative study of three informed stego-systems in active warden context: scalar Costa scheme, trellis-coded quantization and spread transform scalar Costa scheme. By leading on analytical formulations and on experimental evaluations, we show the advantages and limits of each scheme in term of statistical undetectability and capacity in the case of active warden. Such as the undetectability is given by the distance between the stego-signal and the cover distance. It is measured by the Kullback-Leibler distance.
Kinematic Analysis of a Serial - Parallel Machine Tool: the VERNE machine
Venue: arXiv cs.RO 2008
Year: 2008

The paper derives the inverse and the forward kinematic equations of a serial - parallel 5-axis machine tool: the VERNE machine. This machine is composed of a three-degree-of-freedom (DOF) parallel module and a two-DOF serial tilting table. The parallel module consists of a moving platform that is connected to a fixed base by three non-identical legs. These legs are connected in a way that the combined effects of the three legs lead to an over-constrained mechanism with complex motion. This motion is defined as a simultaneous combination of rotation and translation. In this paper we propose symbolical methods that able to calculate all kinematic solutions and identify the acceptable one by adding analytical constraint on the disposition of legs of the parallel module.
Zigzag Persistence
Venue: arXiv cs.CG 2008
Year: 2008

We describe a new methodology for studying persistence of topological features across a family of spaces or point-cloud data sets, called zigzag persistence. Building on classical results about quiver representations, zigzag persistence generalises the highly successful theory of persistent homology and addresses several situations which are not covered by that theory. In this paper we develop theoretical and algorithmic foundations with a view towards applications in topological statistics.
k-means requires exponentially many iterations even in the plane
Venue: arXiv cs.CG 2008
Year: 2008

The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e. O(n^{kd})) can be exponential in the number of points. Recently, Arthur and Vassilvitskii [3] showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to 2^{Ω(\sqrt{n})} with a construction in d=Ω(\sqrt{n}) dimensions. In [3] they also conjectured the existence of superpolynomial lower bounds for any d >= 2. Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2^{Ω(n)}.
Emergent Community Structure in Social Tagging Systems
Venue: arXiv cs.IR 2008
Year: 2008

A distributed classification paradigm known as collaborative tagging has been widely adopted in new Web applications designed to manage and share online resources. Users of these applications organize resources (Web pages, digital photographs, academic papers) by associating with them freely chosen text labels, or tags. Here we leverage the social aspects of collaborative tagging and introduce a notion of resource distance based on the collective tagging activity of users. We collect data from a popular system and perform experiments showing that our definition of distance can be used to build a weighted network of resources with a detectable community structure. We show that this community structure clearly exposes the semantic relations among resources. The communities of resources that we observe are a genuinely emergent feature, resulting from the uncoordinated activity of a large number of users, and their detection paves the way for mapping emergent semantics in social tagging systems.
Justifications for Logic Programs under Answer Set Semantics
Venue: arXiv cs.AI 2008
Year: 2008

The paper introduces the notion of off-line justification for Answer Set Programming (ASP). Justifications provide a graph-based explanation of the truth value of an atom w.r.t. a given answer set. The paper extends also this notion to provide justification of atoms during the computation of an answer set (on-line justification), and presents an integration of on-line justifications within the computation model of Smodels. Off-line and on-line justifications provide useful tools to enhance understanding of ASP, and they offer a basic data structure to support methodologies and tools for debugging answer set programs. A preliminary implementation has been developed in ASP-PROLOG. (To appear in Theory and Practice of Logic Programming (TPLP))
Adaptive Spam Detection Inspired by a Cross-Regulation Model of Immune Dynamics: A Study of Concept Drift
Venue: arXiv cs.AI 2008
Year: 2008

This paper proposes a novel solution to spam detection inspired by a model of the adaptive immune system known as the crossregulation model. We report on the testing of a preliminary algorithm on six e-mail corpora. We also compare our results statically and dynamically with those obtained by the Naive Bayes classifier and another binary classification method we developed previously for biomedical text-mining applications. We show that the cross-regulation model is competitive against those and thus promising as a bio-inspired algorithm for spam detection in particular, and binary classification in general.
Uncovering protein interaction in abstracts and text using a novel linear model and word proximity networks
Venue: arXiv cs.IR 2008
Year: 2008

We participated in three of the protein-protein interaction subtasks of the Second BioCreative Challenge: classification of abstracts relevant for protein-protein interaction (IAS), discovery of protein pairs (IPS) and text passages characterizing protein interaction (ISS) in full text documents. We approached the abstract classification task with a novel, lightweight linear model inspired by spam-detection techniques, as well as an uncertainty-based integration scheme. We also used a Support Vector Machine and the Singular Value Decomposition on the same features for comparison purposes. Our approach to the full text subtasks (protein pair and passage identification) includes a feature expansion method based on word-proximity networks. Our approach to the abstract classification task (IAS) was among the top submissions for this task in terms of the measures of performance used in the challenge evaluation (accuracy, F-score and AUC). We also report on a web-tool we produced using our approach: the Protein Interaction Abstract Relevance Evaluator (PIARE). Our approach to the full text tasks resulted in one of the highest recall rates as well as mean reciprocal rank of correct passages. Our approach to abstract classification shows that a simple linear model, using relatively few features, is capable of generalizing and uncovering the conceptual nature of protein-protein interaction from the bibliome. Since the novel approach is based on a very lightweight linear model, it can be easily ported and applied to similar problems. In full text problems, the expansion of word features with word-proximity networks is shown to be useful, though the need for some improvements is discussed.
An Efficient Adaptive Distributed Space-Time Coding Scheme for Cooperative Relaying
Venue: arXiv cs.IT 2008
Year: 2008

A non-regenerative dual-hop wireless system based on a distributed space-time coding strategy is considered. It is assumed that each relay retransmits an appropriately scaled space-time coded version of its received signal. The main goal of this paper is to investigate a power allocation strategy in relay stations, which is based on minimizing the outage probability. In the high signal-to-noise ratio regime for the relay-destination link, it is shown that a threshold-based power allocation scheme (i.e., the relay remains silent if its channel gain with the source is less than a prespecified threshold) is optimum. Monte-Carlo simulations show that the derived on-off power allocation scheme performs close to optimum for finite signal-to-noise ratio values. Numerical results demonstrate a dramatic improvement in system performance as compared to the case that the relay stations forward their received signals with full power. In addition, a hybrid amplify-and-forward/detect-and-forward scheme is proposed for the case that the quality of the source-relay link is good. Finally, the robustness of the proposed scheme in the presence of channel estimation errors is numerically evaluated.
Distributed (Delta + 1)-coloring in linear (in Delta) time
Venue: arXiv cs.DC 2008
Year: 2008

The distributed (Delta + 1)-coloring problem is one of most fundamental and well-studied problems of Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current state-of-the-art running time is O(Delta log Delta + log^* n), due to Kuhn and Wattenhofer, PODC'06. Linial (FOCS'87) has proved a lower bound of 1/2 \log^* n for the problem, and Szegedy and Vishwanathan (STOC'93) provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve running time smaller than Θ(Delta log Delta). We present a deterministic (Delta + 1)-coloring distributed algorithm with running time O(Delta) + 1/2 log^* n. We also present a tradeoff between the running time and the number of colors, and devise an O(Delta * t)-coloring algorithm with running time O(Delta / t + \log^* n), for any parameter t, 1 < t < Delta^{1-epsilon}, for an arbitrarily small constant epsilon, 0 < epsilon < 1. On the way to this result we study a generalization of the notion of graph coloring, which is called defective coloring. In an m-defective p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-defective p-coloring with reasonably small m and p can be computed very efficiently. We also develop a technique to employ multiple defect colorings of various subgraphs of the original graph G for computing a (Delta+1)-coloring of G. We believe that these techniques are of independent interest.
Molecular communication: Physically realistic models and achievable information rates
Venue: arXiv cs.IT 2008
Year: 2008

Molecular communication is a biologically-inspired method of communication with attractive properties for microscale and nanoscale devices. In molecular communication, messages are transmitted by releasing a pattern of molecules at a transmitter, which propagate through a fluid medium towards a receiver. In this paper, molecular communication is formulated as a mathematical communication problem in an information-theoretic context. Physically realistic models are obtained, with sufficient abstraction to allow manipulation by communication and information theorists. Although mutual information in these channels is intractable, we give sequences of upper and lower bounds on the mutual information which trade off complexity and performance, and present results to illustrate the feasibility of these bounds in estimating the true mutual information.
Multi-Agent Reinforcement Learning and Genetic Policy Sharing
Venue: arXiv cs.MA 2008
Year: 2008

The effects of policy sharing between agents in a multi-agent dynamical system has not been studied extensively. I simulate a system of agents optimizing the same task using reinforcement learning, to study the effects of different population densities and policy sharing. I demonstrate that sharing policies decreases the time to reach asymptotic behavior, and results in improved asymptotic behavior.
Convex Sparse Matrix Factorizations
Venue: arXiv cs.LG 2008
Year: 2008

We present a convex formulation of dictionary learning for sparse signal decomposition. Convexity is obtained by replacing the usual explicit upper bound on the dictionary size by a convex rank-reducing term similar to the trace norm. In particular, our formulation introduces an explicit trade-off between size and sparsity of the decomposition of rectangular matrices. Using a large set of synthetic examples, we compare the estimation abilities of the convex and non-convex approaches, showing that while the convex formulation has a single local minimum, this may lead in some cases to performance which is inferior to the local minima of the non-convex formulation.
A new metric for robustness with respect to virus spread
Venue: arXiv cs.DM 2008
Year: 2008

The robustness of a network is depending on the type of attack we are considering. In this paper we focus on the spread of viruses on networks. It is common practice to use the epidemic threshold as a measure for robustness. Because the epidemic threshold is inversely proportional to the largest eigenvalue of the adjacency matrix, it seems easy to compare the robustness of two networks. We will show in this paper that the comparison of the robustness with respect to virus spread for two networks actually depends on the value of the effective spreading rate tau. For this reason we propose a new metric, the viral conductance, which takes into account the complete range of values tau can obtain. In this paper we determine the viral conductance of regular graphs, complete bi-partite graphs and a number of realistic networks.
Convex Hull of Arithmetic Automata
Venue: arXiv cs.DS 2008
Year: 2008

Arithmetic automata recognize infinite words of digits denoting decompositions of real and integer vectors. These automata are known expressive and efficient enough to represent the whole set of solutions of complex linear constraints combining both integral and real variables. In this paper, the closed convex hull of arithmetic automata is proved rational polyhedral. Moreover an algorithm computing the linear constraints defining these convex set is provided. Such an algorithm is useful for effectively extracting geometrical properties of the whole set of solutions of complex constraints symbolically represented by arithmetic automata.
Consensus Answers for Queries over Probabilistic Databases
Venue: arXiv cs.DB 2008
Year: 2008

We address the problem of finding a "best" deterministic query answer to a query over a probabilistic database. For this purpose, we propose the notion of a consensus world (or a consensus answer) which is a deterministic world (answer) that minimizes the expected distance to the possible worlds (answers). This problem can be seen as a generalization of the well-studied inconsistent information aggregation problems (e.g. rank aggregation) to probabilistic databases. We consider this problem for various types of queries including SPJ queries, \Topk queries, group-by aggregate queries, and clustering. For different distance metrics, we obtain polynomial time optimal or approximation algorithms for computing the consensus answers (or prove NP-hardness). Most of our results are for a general probabilistic database model, called {\em and/xor tree model}, which significantly generalizes previous probabilistic database models like x-tuples and block-independent disjoint models, and is of independent interest.
The MIMO Iterative Waterfilling Algorithm
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the non-cooperative maximization of mutual information in the vector Gaussian interference channel in a fully distributed fashion via game theory. This problem has been widely studied in a number of works during the past decade for frequency-selective channels, and recently for the more general MIMO case, for which the state-of-the art results are valid only for nonsingular square channel matrices. Surprisingly, these results do not hold true when the channel matrices are rectangular and/or rank deficient matrices. The goal of this paper is to provide a complete characterization of the MIMO game for arbitrary channel matrices, in terms of conditions guaranteeing both the uniqueness of the Nash equilibrium and the convergence of asynchronous distributed iterative waterfilling algorithms. Our analysis hinges on new technical intermediate results, such as a new expression for the MIMO waterfilling projection valid (also) for singular matrices, a mean-value theorem for complex matrix-valued functions, and a general contraction theorem for the multiuser MIMO watefilling mapping valid for arbitrary channel matrices. The quite surprising result is that uniqueness/convergence conditions in the case of tall (possibly singular) channel matrices are more restrictive than those required in the case of (full rank) fat channel matrices. We also propose a modified game and algorithm with milder conditions for the uniqueness of the equilibrium and convergence, and virtually the same performance (in terms of Nash equilibria) of the original game.
Face Detection Using Adaboosted SVM-Based Component Classifier
Venue: arXiv cs.CV 2008
Year: 2008

Recently, Adaboost has been widely used to improve the accuracy of any given learning algorithm. In this paper we focus on designing an algorithm to employ combination of Adaboost with Support Vector Machine as weak component classifiers to be used in Face Detection Task. To obtain a set of effective SVM-weaklearner Classifier, this algorithm adaptively adjusts the kernel parameter in SVM instead of using a fixed one. Proposed combination outperforms in generalization in comparison with SVM on imbalanced classification problem. The proposed here method is compared, in terms of classification accuracy, to other commonly used Adaboost methods, such as Decision Trees and Neural Networks, on CMU+MIT face database. Results indicate that the performance of the proposed method is overall superior to previous Adaboost approaches.
Universal Behavior in Large-scale Aggregation of Independent Noisy Observations
Venue: arXiv cs.IT 2008
Year: 2008

Aggregation of noisy observations involves a difficult tradeoff between observation quality, which can be increased by increasing the number of observations, and aggregation quality which decreases if the number of observations is too large. We clarify this behavior for a protypical system in which arbitrarily large numbers of observations exceeding the system capacity can be aggregated using lossy data compression. We show the existence of a scaling relation between the collective error and the system capacity, and show that large scale lossy aggregation can outperform lossless aggregation above a critical level of observation noise. Further, we show that universal results for scaling and critical value of noise which are independent of system capacity can be obtained by considering asymptotic behavior when the system capacity increases toward infinity.
Ontology Assisted Query Reformulation Using Semantic and Assertion Capabilities of OWL-DL Ontologies
Venue: arXiv cs.DB 2008
Year: 2008

End users of recent biomedical information systems are often unaware of the storage structure and access mechanisms of the underlying data sources and can require simplified mechanisms for writing domain specific complex queries. This research aims to assist users and their applications in formulating queries without requiring complete knowledge of the information structure of underlying data sources. To achieve this, query reformulation techniques and algorithms have been developed that can interpret ontology-based search criteria and associated domain knowledge in order to reformulate a relational query. These query reformulation algorithms exploit the semantic relationships and assertion capabilities of OWL-DL based domain ontologies for query reformulation. In this paper, this approach is applied to the integrated database schema of the EU funded Health-e-Child (HeC) project with the aim of providing ontology assisted query reformulation techniques to simplify the global access that is needed to millions of medical records across the UK and Europe.
Achievable Throughput of Multi-mode Multiuser MIMO with Imperfect CSI Constraints
Venue: arXiv cs.IT 2008
Year: 2008

For the multiple-input multiple-output (MIMO) broadcast channel with imperfect channel state information (CSI), neither the capacity nor the optimal transmission technique have been fully discovered. In this paper, we derive achievable ergodic rates for a MIMO fading broadcast channel when CSI is delayed and quantized. It is shown that we should not support too many users with spatial division multiplexing due to the residual inter-user interference caused by imperfect CSI. Based on the derived achievable rates, we propose a multi-mode transmission strategy to maximize the throughput, which adaptively adjusts the number of active users based on the channel statistics information.
Two conjectures such that the proof of any one of them will lead to the proof that P = NP
Venue: arXiv cs.CC 2008
Year: 2008

In this paper we define a construct called a time-graph. A complete time-graph of order n is the cartesian product of a complete graph with n vertices and a linear graph with n vertices. A time-graph of order n is given by a subset of the set of edges E(n) of such a graph. The notion of a hamiltonian time-graph is defined in a natural way and we define the Hamiltonian time-graph problem (HAMTG) as : Given a time-graph is it hamiltonian ? We show that the Hamiltonian path problem (HAMP) can be transformed to HAMTG in polynomial time. We then define certain vector spaces of functions from E(n) and E(n)xE(n) to B = {0,1}, the field of two elements and derive certain properties of these spaces. We give two conjectures about these spaces and prove that if any one of these conjectures is true, we get a polynomial time algorithm for the Hamiltonian path problem. Since the Hamiltonian path problem is NP-complete we obtain the proof of P = NP provided any one of the two conjectures is true.