OpenRaiser/Intern-Atlas huggingface dataset:
Design and Analysis of an Asynchronous Zero Collision MAC Protocol
Venue: arXiv cs.NI 2008
Year: 2008

This paper proposes and analyzes a distributed MAC protocol that achieves zero collision with no control message exchange nor synchronization. ZC (ZeroCollision) is neither reservation-based nor dynamic TDMA; the protocol supports variable-length packets and does not lose efficiency when some of the stations do not transmit. At the same time, ZC is not a CSMA; in its steady state, it is completely collision-free. The stations transmit repeatedly in a round-robin order once the convergence state is reached. If some stations skip their turn, their transmissions are replaced by idle $20 μ$-second mini-slots that enable the other stations to keep track of their order. Because of its short medium access delay and its efficiency, the protocol supports both real-time and elastic applications. The protocol allows for nodes leaving and joining the network; it can allocate more throughput to specific nodes (such as an access point). The protocol is robust against carrier sensing errors or clock drift. While collision avoidance is guaranteed in a single collision domain, it is not the case in a multiple collision one. However, experiments show ZC supports a comparable amount of goodput to CSMA in a multiple collision domain environment. The paper presents an analysis and extensive simulations of the protocol, confirming that ZC outperforms both CSMA and TDMA at high and low load.
Bi-Directional Multi-Antenna Relay Communications with Wireless Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we consider a two-way or bidirectional communications system with a relay equipped with multiple antennas. We show that when the downlink channel state information is not known at the relay, the benefit of having additional antennas at the relay can only be obtained by using decode and forward (DF) but not amplify and forward (AF). The gain becomes significant when we employ transmit diversity together with wireless network coding. We also demonstrate how the performance of such system can be improved by performing antenna selection at the relay. Our results show that if downlink channel state information is known at the relay, network coding may not provide additional gain than simple antenna selection scheme.
A Continuous Vector-Perturbation for Multi-Antenna Multi-User Communication
Venue: arXiv cs.IT 2008
Year: 2008

The sum-rate of the broadcast channel in a multi-antenna multi-user communication system can be achieved by using precoding and adding a regular perturbation to the data vector. The perturbation can be removed by the modulus function, thus transparent to the receiver, but the information of the precoding matrix is needed to decode the symbols. This paper proposes a new technique to improve the multi-antenna multi-user system, by adding a continuous perturbation to the data vector without the need of information on the precoding matrix to be known at the receiver. The perturbation vector will be treated as interference at the receiver, thus it will be transparent to the receiver. The derivation of the continuous vector perturbation is provided by maximizing the signal-to-interference plus noise ratio or minimizing the minimum mean square error of the received signal.
Opportunistic Interference Alignment in MIMO Interference Channels
Venue: arXiv cs.GT 2008
Year: 2008

We present two interference alignment techniques such that an opportunistic point-to-point multiple input multiple output (MIMO) link can reuse, without generating any additional interference, the same frequency band of a similar pre-existing primary link. In this scenario, we exploit the fact that under power constraints, although each radio maximizes independently its rate by water-filling on their channel transfer matrix singular values, frequently, not all of them are used. Therefore, by aligning the interference of the opportunistic radio it is possible to transmit at a significant rate while insuring zero-interference on the pre-existing link. We propose a linear pre-coder for a perfect interference alignment and a power allocation scheme which maximizes the individual data rate of the secondary link. Our numerical results show that significant data rates are achieved even for a reduced number of antennas.
How Is Meaning Grounded in Dictionary Definitions?
Venue: arXiv cs.CL 2008
Year: 2008

Meaning cannot be based on dictionary definitions all the way down: at some point the circularity of definitions must be broken in some way, by grounding the meanings of certain words in sensorimotor categories learned from experience or shaped by evolution. This is the "symbol grounding problem." We introduce the concept of a reachable set -- a larger vocabulary whose meanings can be learned from a smaller vocabulary through definition alone, as long as the meanings of the smaller vocabulary are themselves already grounded. We provide simple algorithms to compute reachable sets for any given dictionary.
Conceptualization of seeded region growing by pixels aggregation. Part 3: a wide range of algorithms
Venue: arXiv cs.CV 2008
Year: 2008

In the two previous papers of this serie, we have created a library, called Population, dedicated to seeded region growing by pixels aggregation and we have proposed different growing processes to get a partition with or without a boundary region to divide the other regions or to get a partition invariant about the seeded region initialisation order. Using this work, we implement some algorithms belonging to the field of SRGPA using this library and these growing processes.
Cooperation with Complement is Better
Venue: arXiv cs.MA 2008
Year: 2008

In a setting where heterogeneous agents interact to accomplish a given set of goals, cooperation is of utmost importance, especially when agents cannot achieve their individual goals by exclusive use of their own efforts. Even when we consider friendly environments and benevolent agents, cooperation involves several issues: with whom to cooperate, reciprocation, how to address credit assignment and complex division of gains, etc. We propose a model where heterogeneous agents cooperate by forming groups and formation of larger groups is promoted. Benefit of agents is proportional to the performance and the size of the group. There is a time pressure to form a group. We investigate how preferring similar or complement agents in group formation affects an agent's success. Preferring complement in group formation is found to be better, yet there is no need to push the strategy to the extreme since the effect of complementing partners is saturated.
Linear Parameter Varying Model Identification for Control of Rotorcraft-based UAV
Venue: arXiv cs.RO 2008
Year: 2008

A rotorcraft-based unmanned aerial vehicle exhibits more complex properties compared to its full-size counterparts due to its increased sensitivity to control inputs and disturbances and higher bandwidth of its dynamics. As an aerial vehicle with vertical take-off and landing capability, the helicopter specifically poses a difficult problem of transition between forward flight and unstable hover and vice versa. The LPV control technique explicitly takes into account the change in performance due to the real-time parameter variations. The technique therefore theoretically guarantees the performance and robustness over the entire operating envelope. In this study, we investigate a new approach implementing model identification for use in the LPV control framework. The identification scheme employs recursive least square technique implemented on the LPV system represented by dynamics of helicopter during a transition. The airspeed as the scheduling of parameter trajectory is not assumed to vary slowly. The exclusion of slow parameter change requirement allows for the application of the algorithm for aggressive maneuvering capability without the need of expensive computation. The technique is tested numerically and will be validated in the autonomous flight of a small scale helicopter.
Agnostically Learning Juntas from Random Walks
Venue: arXiv cs.LG 2008
Year: 2008

We prove that the class of functions g:{-1,+1}^n -> {-1,+1} that only depend on an unknown subset of k<<n variables (so-called k-juntas) is agnostically learnable from a random walk in time polynomial in n, 2^{k^2}, epsilon^{-k}, and log(1/delta). In other words, there is an algorithm with the claimed running time that, given epsilon, delta > 0 and access to a random walk on {-1,+1}^n labeled by an arbitrary function f:{-1,+1}^n -> {-1,+1}, finds with probability at least 1-delta a k-junta that is (opt(f)+epsilon)-close to f, where opt(f) denotes the distance of a closest k-junta to f.
Localized Spanners for Wireless Networks
Venue: arXiv cs.DC 2008
Year: 2008

We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G=(V,E) and any e > 0, a (1+e)-spanner for G of maximum degree O(1) and total weight O(w(MST)), where w(MST) denotes the weight of a minimum spanning tree for V. We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V, E), a planar Cdel(1+e)(1+pi/2)-spanner for G of maximum degree O(1) and total weight O(w(MST)). Here Cdel denotes the stretch factor of the unit Delaunay triangulation for V. Both constructions can be completed in O(1) communication rounds, and require each node to know its own coordinates.
SP2Bench: A SPARQL Performance Benchmark
Venue: arXiv cs.DB 2008
Year: 2008

Recently, the SPARQL query language for RDF has reached the W3C recommendation status. In response to this emerging standard, the database community is currently exploring efficient storage techniques for RDF data and evaluation strategies for SPARQL queries. A meaningful analysis and comparison of these approaches necessitates a comprehensive and universal benchmark platform. To this end, we have developed SP^2Bench, a publicly available, language-specific SPARQL performance benchmark. SP^2Bench is settled in the DBLP scenario and comprises both a data generator for creating arbitrarily large DBLP-like documents and a set of carefully designed benchmark queries. The generated documents mirror key characteristics and social-world distributions encountered in the original DBLP data set, while the queries implement meaningful requests on top of this data, covering a variety of SPARQL operator constellations and RDF access patterns. As a proof of concept, we apply SP^2Bench to existing engines and discuss their strengths and weaknesses that follow immediately from the benchmark results.
A new Hedging algorithm and its application to inferring latent random variables
Venue: arXiv cs.GT 2008
Year: 2008

We present a new online learning algorithm for cumulative discounted gain. This learning algorithm does not use exponential weights on the experts. Instead, it uses a weighting scheme that depends on the regret of the master algorithm relative to the experts. In particular, experts whose discounted cumulative gain is smaller (worse) than that of the master algorithm receive zero weight. We also sketch how a regret-based algorithm can be used as an alternative to Bayesian averaging in the context of inferring latent random variables.
Myopic Coding in Multiterminal Networks
Venue: arXiv cs.IT 2008
Year: 2008

This paper investigates the interplay between cooperation and achievable rates in multi-terminal networks. Cooperation refers to the process of nodes working together to relay data toward the destination. There is an inherent tradeoff between achievable information transmission rates and the level of cooperation, which is determined by how many nodes are involved and how the nodes encode/decode the data. We illustrate this trade-off by studying information-theoretic decode-forward based coding strategies for data transmission in multi-terminal networks. Decode-forward strategies are usually discussed in the context of omniscient coding, in which all nodes in the network fully cooperate with each other, both in encoding and decoding. In this paper, we investigate myopic coding, in which each node cooperates with only a few neighboring nodes. We show that achievable rates of myopic decode-forward can be as large as that of omniscient decode-forward in the low SNR regime. We also show that when each node has only a few cooperating neighbors, adding one node into the cooperation increases the transmission rate significantly. Furthermore, we show that myopic decode-forward can achieve non-zero rates as the network size grows without bound.
A Dynamic Programming Approach To Length-Limited Huffman Coding
Venue: arXiv cs.DS 2008
Year: 2008

The ``state-of-the-art'' in Length Limited Huffman Coding algorithms is the $Θ(ND)$-time, $Θ(N)$-space one of Hirschberg and Larmore, where $D\le N$ is the length restriction on the code. This is a very clever, very problem specific, technique. In this note we show that there is a simple Dynamic-Programming (DP) method that solves the problem with the same time and space bounds. The fact that there was an $Θ(ND)$ time DP algorithm was previously known; it is a straightforward DP with the Monge property (which permits an order of magnitude speedup). It was not interesting, though, because it also required $Θ(ND)$ space. The main result of this paper is the technique developed for reducing the space. It is quite simple and applicable to many other problems modeled by DPs with the Monge property. We illustrate this with examples from web-proxy design and wireless mobile paging.
Conception et Evaluation de XQuery dans une architecture de médiation "Tout-XML"
Venue: arXiv cs.DB 2008
Year: 2008

XML has emerged as the leading language for representing and exchanging data not only on the Web, but also in general in the enterprise. XQuery is emerging as the standard query language for XML. Thus, tools are required to mediate between XML queries and heterogeneous data sources to integrate data in XML. This paper presents the XMedia mediator, a unique tool for integrating and querying disparate heterogeneous information as unified XML views. It describes the mediator architecture and focuses on the unique distributed query processing technology implemented in this component. Query evaluation is based on an original XML algebra simply extending classical operators to process tuples of tree elements. Further, we present a set of performance evaluation on a relational benchmark, which leads to discuss possible performance enhancements.
Range Medians
Venue: arXiv cs.DS 2008
Year: 2008

We study a generalization of the classical median finding problem to batched query case: given an array of unsorted $n$ items and $k$ (not necessarily disjoint) intervals in the array, the goal is to determine the median in {\em each} of the intervals in the array. We give an algorithm that uses $O(n\log n + k\log k \log n)$ comparisons and show a lower bound of $Ω(n\log k)$ comparisons for this problem. This is optimal for $k=O(n/\log n)$.
Wireless Broadcast with Network Coding in Mobile Ad-Hoc Networks: DRAGONCAST
Venue: arXiv cs.NI 2008
Year: 2008

Network coding is a recently proposed method for transmitting data, which has been shown to have potential to improve wireless network performance. We study network coding for one specific case of multicast, broadcasting, from one source to all nodes of the network. We use network coding as a loss tolerant, energy-efficient, method for broadcast. Our emphasis is on mobile networks. Our contribution is the proposal of DRAGONCAST, a protocol to perform network coding in such a dynamically evolving environment. It is based on three building blocks: a method to permit real-time decoding of network coding, a method to adjust the network coding transmission rates, and a method for ensuring the termination of the broadcast. The performance and behavior of the method are explored experimentally by simulations; they illustrate the excellent performance of the protocol.
Lightweight Security for Network Coding
Venue: arXiv cs.CR 2008
Year: 2008

Under the emerging network coding paradigm, intermediate nodes in the network are allowed not only to store and forward packets but also to process and mix different data flows. We propose a low-complexity cryptographic scheme that exploits the inherent security provided by random linear network coding and offers the advantage of reduced overhead in comparison to traditional end-to-end encryption of the entire data. Confidentiality is achieved by protecting (or "locking") the source coefficients required to decode the encoded data, without preventing intermediate nodes from running their standard network coding operations. Our scheme can be easily combined with existing techniques that counter active attacks.
Random XML sampling the Boltzmann way
Venue: arXiv cs.OH 2008
Year: 2008

In this article we present the prototype of a framework capable of producing, with linear complexity, uniformly random XML documents with respect to a given RELAX NG grammar. The generation relies on powerful combinatorial methods together with numerical and symbolic resolution of polynomial systems.
A Counterexample Guided Abstraction-Refinement Framework for Markov Decision Processes
Venue: arXiv cs.SE 2008
Year: 2008

The main challenge in using abstractions effectively, is to construct a suitable abstraction for the system being verified. One approach that tries to address this problem is that of {\it counterexample guided abstraction-refinement (CEGAR)}, wherein one starts with a coarse abstraction of the system, and progressively refines it, based on invalid counterexamples seen in prior model checking runs, until either an abstraction proves the correctness of the system or a valid counterexample is generated. While CEGAR has been successfully used in verifying non-probabilistic systems automatically, CEGAR has not been applied in the context of probabilistic systems. The main issues that need to be tackled in order to extend the approach to probabilistic systems is a suitable notion of ``counterexample'', algorithms to generate counterexamples, check their validity, and then automatically refine an abstraction based on an invalid counterexample. In this paper, we address these issues, and present a CEGAR framework for Markov Decision Processes.
Line Transversals of Convex Polyhedra in $\reals^3$
Venue: arXiv cs.CG 2008
Year: 2008

We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the combinatorial complexity of the set $\T$ of line transversals of a collection $¶$ of $k$ convex polyhedra in $\reals^3$ with a total of $n$ facets, and present a randomized algorithm which computes the boundary of $\T$ in comparable expected time. Thus, when $k\ll n$, the new bounds on the complexity (and construction cost) of $\T$ improve upon the previously best known bounds, which are nearly cubic in $n$. To obtain the above result, we study the set $\TL$ of line transversals which emanate from a fixed line $\ell_0$, establish an almost tight bound of $O(nk^{1+\eps})$ on the complexity of $\TL$, and provide a randomized algorithm which computes $\TL$ in comparable expected time. Slightly improved combinatorial bounds for the complexity of $\TL$, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of $¶$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $¶$, and the case where the polyhedra of $¶$ are unbounded in a direction parallel to $\ell_0$.
Expanders via Random Spanning Trees
Venue: arXiv cs.DM 2008
Year: 2008

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph G_{n,p}, for p> c log{n}/n, two spanning trees give an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary -- each spanning tree can be produced independently using an algorithm by Aldous and Broder: a random walk in the graph with edges leading to previously unvisited vertices included in the tree. A second important application of splicers is to graph sparsification where the goal is to approximate every cut (and more generally the quadratic form of the Laplacian) using only a small subgraph of the original graph. Benczur-Karger as well as Spielman-Srivastava have shown sparsifiers with O(n log n/eps^2)$ edges that achieve approximation within factors 1+eps and 1-eps. Their methods, based on independent sampling of edges, need Omega(n log n) edges to get any approximation (else the subgraph could be disconnected) and leave open the question of linear-size sparsifiers. Splicers address this question for random graphs by providing sparsifiers of size O(n) that approximate every cut to within a factor of O(log n).
Mean asymptotic behaviour of radix-rational sequences and dilation equations (Extended version)
Venue: arXiv cs.DM 2008
Year: 2008

The generating series of a radix-rational sequence is a rational formal power series from formal language theory viewed through a fixed radix numeration system. For each radix-rational sequence with complex values we provide an asymptotic expansion for the sequence of its Cesàro means. The precision of the asymptotic expansion depends on the joint spectral radius of the linear representation of the sequence; the coefficients are obtained through some dilation equations. The proofs are based on elementary linear algebra.
Coinductive Formal Reasoning in Exact Real Arithmetic
Venue: arXiv cs.LO 2008
Year: 2008

In this article we present a method for formally proving the correctness of the lazy algorithms for computing homographic and quadratic transformations -- of which field operations are special cases-- on a representation of real numbers by coinductive streams. The algorithms work on coinductive stream of Möbius maps and form the basis of the Edalat--Potts exact real arithmetic. We use the machinery of the Coq proof assistant for the coinductive types to present the formalisation. The formalised algorithms are only partially productive, i.e., they do not output provably infinite streams for all possible inputs. We show how to deal with this partiality in the presence of syntactic restrictions posed by the constructive type theory of Coq. Furthermore we show that the type theoretic techniques that we develop are compatible with the semantics of the algorithms as continuous maps on real numbers. The resulting Coq formalisation is available for public download.