OpenRaiser/Intern-Atlas huggingface dataset:
Heuristics for Network Coding in Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

Multicast is a central challenge for emerging multi-hop wireless architectures such as wireless mesh networks, because of its substantial cost in terms of bandwidth. In this report, we study one specific case of multicast: broadcasting, sending data from one source to all nodes, in a multi-hop wireless network. The broadcast we focus on is based on network coding, a promising avenue for reducing cost; previous work of ours showed that the performance of network coding with simple heuristics is asymptotically optimal: each transmission is beneficial to nearly every receiver. This is for homogenous and large networks of the plan. But for small, sparse or for inhomogeneous networks, some additional heuristics are required. This report proposes such additional new heuristics (for selecting rates) for broadcasting with network coding. Our heuristics are intended to use only simple local topology information. We detail the logic of the heuristics, and with experimental results, we illustrate the behavior of the heuristics, and demonstrate their excellent performance.
Non-atomic Games for Multi-User Systems
Venue: arXiv cs.IT 2007
Year: 2007

In this contribution, the performance of a multi-user system is analyzed in the context of frequency selective fading channels. Using game theoretic tools, a useful framework is provided in order to determine the optimal power allocation when users know only their own channel (while perfect channel state information is assumed at the base station). We consider the realistic case of frequency selective channels for uplink CDMA. This scenario illustrates the case of decentralized schemes, where limited information on the network is available at the terminal. Various receivers are considered, namely the Matched filter, the MMSE filter and the optimum filter. The goal of this paper is to derive simple expressions for the non-cooperative Nash equilibrium as the number of mobiles becomes large and the spreading length increases. To that end two asymptotic methodologies are combined. The first is asymptotic random matrix theory which allows us to obtain explicit expressions of the impact of all other mobiles on any given tagged mobile. The second is the theory of non-atomic games which computes good approximations of the Nash equilibrium as the number of mobiles grows.
Selection Relaying at Low Signal to Noise Ratios
Venue: arXiv cs.IT 2007
Year: 2007

Performance of cooperative diversity schemes at Low Signal to Noise Ratios (LSNR) was recently studied by Avestimehr et. al. [1] who emphasized the importance of diversity gain over multiplexing gain at low SNRs. It has also been pointed out that continuous energy transfer to the channel is necessary for achieving the max-flow min-cut bound at LSNR. Motivated by this we propose the use of Selection Decode and Forward (SDF) at LSNR and analyze its performance in terms of the outage probability. We also propose an energy optimization scheme which further brings down the outage probability.
Interference Alignment and the Degrees of Freedom for the K User Interference Channel
Venue: arXiv cs.IT 2007
Year: 2007

While the best known outerbound for the K user interference channel states that there cannot be more than K/2 degrees of freedom, it has been conjectured that in general the constant interference channel with any number of users has only one degree of freedom. In this paper, we explore the spatial degrees of freedom per orthogonal time and frequency dimension for the K user wireless interference channel where the channel coefficients take distinct values across frequency slots but are fixed in time. We answer five closely related questions. First, we show that K/2 degrees of freedom can be achieved by channel design, i.e. if the nodes are allowed to choose the best constant, finite and nonzero channel coefficient values. Second, we show that if channel coefficients can not be controlled by the nodes but are selected by nature, i.e., randomly drawn from a continuous distribution, the total number of spatial degrees of freedom for the K user interference channel is almost surely K/2 per orthogonal time and frequency dimension. Thus, only half the spatial degrees of freedom are lost due to distributed processing of transmitted and received signals on the interference channel. Third, we show that interference alignment and zero forcing suffice to achieve all the degrees of freedom in all cases. Fourth, we show that the degrees of freedom $D$ directly lead to an $\mathcal{O}(1)$ capacity characterization of the form $C(SNR)=D\log(1+SNR)+\mathcal{O}(1)$ for the multiple access channel, the broadcast channel, the 2 user interference channel, the 2 user MIMO X channel and the 3 user interference channel with M>1 antennas at each node. Fifth, we characterize the degree of freedom benefits from cognitive sharing of messages on the 3 user interference channel.
Performance Analysis of Publish/Subscribe Systems
Venue: arXiv cs.DC 2007
Year: 2007

The Desktop Grid offers solutions to overcome several challenges and to answer increasingly needs of scientific computing. Its technology consists mainly in exploiting resources, geographically dispersed, to treat complex applications needing big power of calculation and/or important storage capacity. However, as resources number increases, the need for scalability, self-organisation, dynamic reconfigurations, decentralisation and performance becomes more and more essential. Since such properties are exhibited by P2P systems, the convergence of grid computing and P2P computing seems natural. In this context, this paper evaluates the scalability and performance of P2P tools for discovering and registering services. Three protocols are used for this purpose: Bonjour, Avahi and Free-Pastry. We have studied the behaviour of theses protocols related to two criteria: the elapsed time for registrations services and the needed time to discover new services. Our aim is to analyse these results in order to choose the best protocol we can use in order to create a decentralised middleware for desktop grid.
Robust Audio Watermarking Against the D/A and A/D conversions
Venue: arXiv cs.CR 2007
Year: 2007

Audio watermarking has played an important role in multimedia security. In many applications using audio watermarking, D/A and A/D conversions (denoted by DA/AD in this paper) are often involved. In previous works, however, the robustness issue of audio watermarking against the DA/AD conversions has not drawn sufficient attention yet. In our extensive investigation, it has been found that the degradation of a watermarked audio signal caused by the DA/AD conversions manifests itself mainly in terms of wave magnitude distortion and linear temporal scaling, making the watermark extraction failed. Accordingly, a DWT-based audio watermarking algorithm robust against the DA/AD conversions is proposed in this paper. To resist the magnitude distortion, the relative energy relationships among different groups of the DWT coefficients in the low-frequency sub-band are utilized in watermark embedding by adaptively controlling the embedding strength. Furthermore, the resynchronization is designed to cope with the linear temporal scaling. The time-frequency localization characteristics of DWT are exploited to save the computational load in the resynchronization. Consequently, the proposed audio watermarking algorithm is robust against the DA/AD conversions, other common audio processing manipulations, and the attacks in StirMark Benchmark for Audio, which has been verified by experiments.
Assisted Problem Solving and Decompositions of Finite Automata
Venue: arXiv cs.CC 2007
Year: 2007

A study of assisted problem solving formalized via decompositions of deterministic finite automata is initiated. The landscape of new types of decompositions of finite automata this study uncovered is presented. Languages with various degrees of decomposability between undecomposable and perfectly decomposable are shown to exist.
Precoding for the AWGN Channel with Discrete Interference
Venue: arXiv cs.IT 2007
Year: 2007

For a state-dependent DMC with input alphabet $\mathcal{X}$ and state alphabet $\mathcal{S}$ where the i.i.d. state sequence is known causally at the transmitter, it is shown that by using at most $|\mathcal{X}||\mathcal{S}|-|\mathcal{S}|+1$ out of $|\mathcal{X}|^{|\mathcal{S}|}$ input symbols of the Shannon's \emph{associated} channel, the capacity is achievable. As an example of state-dependent channels with side information at the transmitter, $M$-ary signal transmission over AWGN channel with additive $Q$-ary interference where the sequence of i.i.d. interference symbols is known causally at the transmitter is considered. For the special case where the Gaussian noise power is zero, a sufficient condition, which is independent of interference, is given for the capacity to be $\log_2 M$ bits per channel use. The problem of maximization of the transmission rate under the constraint that the channel input given any current interference symbol is uniformly distributed over the channel input alphabet is investigated. For this setting, the general structure of a communication system with optimal precoding is proposed.
The Role of Time in the Creation of Knowledge
Venue: arXiv cs.LG 2007
Year: 2007

This paper I assume that in humans the creation of knowledge depends on a discrete time, or stage, sequential decision-making process subjected to a stochastic, information transmitting environment. For each time-stage, this environment randomly transmits Shannon type information-packets to the decision-maker, who examines each of them for relevancy and then determines his optimal choices. Using this set of relevant information-packets, the decision-maker adapts, over time, to the stochastic nature of his environment, and optimizes the subjective expected rate-of-growth of knowledge. The decision-maker's optimal actions, lead to a decision function that involves, over time, his view of the subjective entropy of the environmental process and other important parameters at each time-stage of the process. Using this model of human behavior, one could create psychometric experiments using computer simulation and real decision-makers, to play programmed games to measure the resulting human performance.
Phase space methods and psychoacoustic models in lossy transform coding
Venue: arXiv cs.IT 2007
Year: 2007

I present a method for lossy transform coding of digital audio that uses the Weyl symbol calculus for constructing the encoding and decoding transformation. The method establishes a direct connection between a time-frequency representation of the signal dependent threshold of masked noise and the encode/decode pair. The formalism also offers a time-frequency measure of perceptual entropy.
From Royal Road to Epistatic Road for Variable Length Evolution Algorithm
Venue: arXiv cs.NE 2007
Year: 2007

Although there are some real world applications where the use of variable length representation (VLR) in Evolutionary Algorithm is natural and suitable, an academic framework is lacking for such representations. In this work we propose a family of tunable fitness landscapes based on VLR of genotypes. The fitness landscapes we propose possess a tunable degree of both neutrality and epistasis; they are inspired, on the one hand by the Royal Road fitness landscapes, and the other hand by the NK fitness landscapes. So these landscapes offer a scale of continuity from Royal Road functions, with neutrality and no epistasis, to landscapes with a large amount of epistasis and no redundancy. To gain insight into these fitness landscapes, we first use standard tools such as adaptive walks and correlation length. Second, we evaluate the performances of evolutionary algorithms on these landscapes for various values of the neutral and the epistatic parameters; the results allow us to correlate the performances with the expected degrees of neutrality and epistasis.
Unfolding Orthogonal Terrains
Venue: arXiv cs.CG 2007
Year: 2007

It is shown that every orthogonal terrain, i.e., an orthogonal (right-angled) polyhedron based on a rectangle that meets every vertical line in a segment, has a grid unfolding: its surface may be unfolded to a single non-overlapping piece by cutting along grid edges defined by coordinate planes through every vertex.
Dial a Ride from k-forest
Venue: arXiv cs.DS 2007
Year: 2007

The k-forest problem is a common generalization of both the k-MST and the dense-$k$-subgraph problems. Formally, given a metric space on $n$ vertices $V$, with $m$ demand pairs $\subseteq V \times V$ and a ``target'' $k\le m$, the goal is to find a minimum cost subgraph that connects at least $k$ demand pairs. In this paper, we give an $O(\min\{\sqrt{n},\sqrt{k}\})$-approximation algorithm for $k$-forest, improving on the previous best ratio of $O(n^{2/3}\log n)$ by Segev & Segev. We then apply our algorithm for k-forest to obtain approximation algorithms for several Dial-a-Ride problems. The basic Dial-a-Ride problem is the following: given an $n$ point metric space with $m$ objects each with its own source and destination, and a vehicle capable of carrying at most $k$ objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We prove that an $α$-approximation algorithm for the $k$-forest problem implies an $O(α\cdot\log^2n)$-approximation algorithm for Dial-a-Ride. Using our results for $k$-forest, we get an $O(\min\{\sqrt{n},\sqrt{k}\}\cdot\log^2 n)$- approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an $O(\sqrt{k}\log n)$-approximation by Charikar & Raghavachari; our results give a different proof of a similar approximation guarantee--in fact, when the vehicle capacity $k$ is large, we give a slight improvement on their results.
Model Selection Through Sparse Maximum Likelihood Estimation
Venue: arXiv cs.AI 2007
Year: 2007

We consider the problem of estimating the parameters of a Gaussian or binary distribution in such a way that the resulting undirected graphical model is sparse. Our approach is to solve a maximum likelihood problem with an added l_1-norm penalty term. The problem as formulated is convex but the memory requirements and complexity of existing interior point methods are prohibitive for problems with more than tens of nodes. We present two new algorithms for solving problems with at least a thousand nodes in the Gaussian case. Our first algorithm uses block coordinate descent, and can be interpreted as recursive l_1-norm penalized regression. Our second algorithm, based on Nesterov's first order method, yields a complexity estimate with a better dependence on problem size than existing interior point methods. Using a log determinant relaxation of the log partition function (Wainwright & Jordan (2006)), we show that these same algorithms can be used to solve an approximate sparse maximum likelihood problem for the binary case. We test our algorithms on synthetic data, as well as on gene expression and senate voting records data.
Workspace Analysis of the Parallel Module of the VERNE Machine
Venue: arXiv cs.RO 2007
Year: 2007

The paper addresses geometric aspects of a spatial three-degree-of-freedom parallel module, which is the parallel module of a hybrid serial-parallel 5-axis machine tool. This parallel module consists of a moving platform that is connected to a fixed base by three non-identical legs. Each leg is made up of one prismatic and two pairs of spherical joint, which 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. A method for computing the complete workspace of the VERNE parallel module for various tool lengths is presented. An algorithm describing this method is also introduced.
The Requirements for Ontologies in Medical Data Integration: A Case Study
Venue: arXiv cs.DB 2007
Year: 2007

Evidence-based medicine is critically dependent on three sources of information: a medical knowledge base, the patients medical record and knowledge of available resources, including where appropriate, clinical protocols. Patient data is often scattered in a variety of databases and may, in a distributed model, be held across several disparate repositories. Consequently addressing the needs of an evidence-based medicine community presents issues of biomedical data integration, clinical interpretation and knowledge management. This paper outlines how the Health-e-Child project has approached the challenge of requirements specification for (bio-) medical data integration, from the level of cellular data, through disease to that of patient and population. The approach is illuminated through the requirements elicitation and analysis of Juvenile Idiopathic Arthritis (JIA), one of three diseases being studied in the EC-funded Health-e-Child project.
Very fast watermarking by reversible contrast mapping
Venue: arXiv cs.MM 2007
Year: 2007

Reversible contrast mapping (RCM) is a simple integer transform that applies to pairs of pixels. For some pairs of pixels, RCM is invertible, even if the least significant bits (LSBs) of the transformed pixels are lost. The data space occupied by the LSBs is suitable for data hiding. The embedded information bit-rates of the proposed spatial domain reversible watermarking scheme are close to the highest bit-rates reported so far. The scheme does not need additional data compression, and, in terms of mathematical complexity, it appears to be the lowest complexity one proposed up to now. A very fast lookup table implementation is proposed. Robustness against cropping can be ensured as well.
Spectrum Sensing in Cognitive Radios Based on Multiple Cyclic Frequencies
Venue: arXiv cs.IT 2007
Year: 2007

Cognitive radios sense the radio spectrum in order to find unused frequency bands and use them in an agile manner. Transmission by the primary user must be detected reliably even in the low signal-to-noise ratio (SNR) regime and in the face of shadowing and fading. Communication signals are typically cyclostationary, and have many periodic statistical properties related to the symbol rate, the coding and modulation schemes as well as the guard periods, for example. These properties can be exploited in designing a detector, and for distinguishing between the primary and secondary users' signals. In this paper, a generalized likelihood ratio test (GLRT) for detecting the presence of cyclostationarity using multiple cyclic frequencies is proposed. Distributed decision making is employed by combining the quantized local test statistics from many secondary users. User cooperation allows for mitigating the effects of shadowing and provides a larger footprint for the cognitive radio system. Simulation examples demonstrate the resulting performance gains in the low SNR regime and the benefits of cooperative detection.
The star trellis decoding of Reed-Solomon codes
Venue: arXiv cs.IT 2007
Year: 2007

The new method for Reed-Solomon codes decoding is introduced. The method is based on the star trellis decoding of the binary image of Reed-Solomon codes.
Noisy Sorting Without Resampling
Venue: arXiv cs.DS 2007
Year: 2007

In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order $a_{π(1)} < ... < a_{π(n)}$ where $π$ is a permutation on $n$ elements. The input is the status of $n \choose 2$ queries of the form $q(a_i,x_j)$, where $q(a_i,a_j) = +$ with probability at least $1/2+\ga$ if $π(i) > π(j)$ for all pairs $i \neq j$, where $\ga > 0$ is a constant and $q(a_i,a_j) = -q(a_j,a_i)$ for all $i$ and $j$. It is assumed that the errors are independent. Given the status of the queries the goal is to find the maximum likelihood order. In other words, the goal is find a permutation $σ$ that minimizes the number of pairs $σ(i) > σ(j)$ where $q(σ(i),σ(j)) = -$. The problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbations of a linear order. Note that when $\ga < 1/2$ and $n$ is large, it is impossible to recover the original order $π$. It is known that the weighted feedback are set problem on tournaments is NP-hard in general. Here we present an algorithm of running time $n^{O(γ^{-4})}$ and sampling complexity $O_γ(n \log n)$ that with high probability solves the noisy sorting without re-sampling problem. We also show that if $a_{σ(1)},a_{σ(2)},...,a_{σ(n)}$ is an optimal solution of the problem then it is ``close'' to the original order. More formally, with high probability it holds that $\sum_i |σ(i) - π(i)| = Θ(n)$ and $\max_i |σ(i) - π(i)| = Θ(\log n)$. Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts.
Delayed Correlations in Inter-Domain Network Traffic
Venue: arXiv cs.NI 2007
Year: 2007

To observe the evolution of network traffic correlations we analyze the eigenvalue spectra and eigenvectors statistics of delayed correlation matrices of network traffic counts time series. Delayed correlation matrix D is composed of the correlations between one variable in the multivariable time series and another at a time delay τ. Inverse participation ratio (IPR) of eigenvectors of D deviates substantially from the IPR of eigenvectors of the equal time correlation matrix C. We relate this finding to the localization and discuss its importance for network congestion control. The time-lagged correlation pattern between network time series is preserved over a long time, up to 100τ, where τ=300 sec. The largest eigenvalue λ_{max} of D and the corresponding IPR oscillate with two characteristic periods of 3τand 6τ. The existence of delayed correlations between network time series fits well into the long range dependence (LRD) property of the network traffic. The ability to monitor and control the long memory processes is crucial since they impact the network performance. Injecting the random traffic counts between non-randomly correlated time series, we were able to break the picture of periodicity of λ_{max}. In addition, we investigated influence of the periodic injections on both largest eigenvalue and the IPR, and addressed relevance of these indicators for the LRD and self-similarity of the network traffic.
Sélection simultanée d'index et de vues matérialisées
Venue: arXiv cs.DB 2007
Year: 2007

Indices and materialized views are physical structures that accelerate data access in data warehouses. However, these data structures generate some maintenance overhead. They also share the same storage space. The existing studies about index and materialized view selection consider these structures separately. In this paper, we adopt the opposite stance and couple index and materialized view selection to take into account the interactions between them and achieve an efficient storage space sharing. We develop cost models that evaluate the respective benefit of indexing and view materialization. These cost models are then exploited by a greedy algorithm to select a relevant configuration of indices and materialized views. Experimental results show that our strategy performs better than the independent selection of indices and materialized views.