OpenRaiser/Intern-Atlas huggingface dataset:
Définition d'une structure adaptative de réseau local sans fil à consommation optimisée
Venue: arXiv cs.NI 2008
Year: 2008

The strong growth of low rate wireless personal area networks (LR-WPAN), leads us to consider the autonomy problems, thus node lifetime in a network, knowing that the power supplies replacement is often difficult to realize. The inherent mobility in this type of equipment is an essential element. It will provide routing constraints, so a complex problem to solve. This article provides work lines to assess the performance of such a network in terms of energy consumption and mobility. The objectives are contradictory; it will necessarily find a compromise. In addition, if we want to guarantee a maximum delay for the transmitted messages, possibility offered by the IEEE 802.15-4 standard, another compromise necessitate a strictly fixed structure and a fully mobile structure. Therefore, we present a quantization of the energy cost related to the desired data rate and compared to the sleep duration of nodes in the network. Then, we open reflexion lines to find the best compromise: consumption / mobility / guaranteed deadlines, in suggesting an adaptive network structure from a concept of MANET.
Analysis of Social Voting Patterns on Digg
Venue: arXiv cs.CY 2008
Year: 2008

The social Web is transforming the way information is created and distributed. Blog authoring tools enable users to publish content, while sites such as Digg and Del.icio.us are used to distribute content to a wider audience. With content fast becoming a commodity, interest in using social networks to promote and find content has grown, both on the side of content producers (viral marketing) and consumers (recommendation). Here we study the role of social networks in promoting content on Digg, a social news aggregator that allows users to submit links to and vote on news stories. Digg's goal is to feature the most interesting stories on its front page, and it aggregates opinions of its many users to identify them. Like other social networking sites, Digg allows users to designate other users as ``friends'' and see what stories they found interesting. We studied the spread of interest in news stories submitted to Digg in June 2006. Our results suggest that pattern of the spread of interest in a story on the network is indicative of how popular the story will become. Stories that spread mainly outside of the submitter's neighborhood go on to be very popular, while stories that spread mainly through submitter's social neighborhood prove not to be very popular. This effect is visible already in the early stages of voting, and one can make a prediction about the potential audience of a story simply by analyzing where the initial votes come from.
Information-Theoretically Secure Voting Without an Honest Majority
Venue: arXiv cs.CR 2008
Year: 2008

We present three voting protocols with unconditional privacy and information-theoretic correctness, without assuming any bound on the number of corrupt voters or voting authorities. All protocols have polynomial complexity and require private channels and a simultaneous broadcast channel. Our first protocol is a basic voting scheme which allows voters to interact in order to compute the tally. Privacy of the ballot is unconditional, but any voter can cause the protocol to fail, in which case information about the tally may nevertheless transpire. Our second protocol introduces voting authorities which allow the implementation of the first protocol, while reducing the interaction and limiting it to be only between voters and authorities and among the authorities themselves. The simultaneous broadcast is also limited to the authorities. As long as a single authority is honest, the privacy is unconditional, however, a single corrupt authority or a single corrupt voter can cause the protocol to fail. Our final protocol provides a safeguard against corrupt voters by enabling a verification technique to allow the authorities to revoke incorrect votes. We also discuss the implementation of a simultaneous broadcast channel with the use of temporary computational assumptions, yielding versions of our protocols achieving everlasting security.
Classification of curves in 2D and 3D via affine integral signatures
Venue: arXiv cs.CV 2008
Year: 2008

We propose a robust classification algorithm for curves in 2D and 3D, under the special and full groups of affine transformations. To each plane or spatial curve we assign a plane signature curve. Curves, equivalent under an affine transformation, have the same signature. The signatures introduced in this paper are based on integral invariants, which behave much better on noisy images than classically known differential invariants. The comparison with other types of invariants is given in the introduction. Though the integral invariants for planar curves were known before, the affine integral invariants for spatial curves are proposed here for the first time. Using the inductive variation of the moving frame method we compute affine invariants in terms of Euclidean invariants. We present two types of signatures, the global signature and the local signature. Both signatures are independent of parameterization (curve sampling). The global signature depends on the choice of the initial point and does not allow us to compare fragments of curves, and is therefore sensitive to occlusions. The local signature, although is slightly more sensitive to noise, is independent of the choice of the initial point and is not sensitive to occlusions in an image. It helps establish local equivalence of curves. The robustness of these invariants and signatures in their application to the problem of classification of noisy spatial curves extracted from a 3D object is analyzed.
Finding the theta-Guarded Region
Venue: arXiv cs.CG 2008
Year: 2008

We are given a finite set of n points (guards) G in the plane R^2 and an angle 0 < theta < 2 pi. A theta-cone is a cone with apex angle theta. We call a theta-cone empty (with respect to G) if it does not contain any point of G. A point p in R^2 is called theta-guarded if every theta-cone with its apex located at p is non-empty. Furthermore, the set of all theta-guarded points is called the theta-guarded region, or the theta-region for short. We present several results on this topic. The main contribution of our work is to describe the theta-region with O(n/theta) circular arcs, and we give an algorithm to compute it. We prove a tight O(n) worst-case bound on the complexity of the theta-region for theta >= pi/2. In case theta is bounded from below by a positive constant, we prove an almost linear bound O(n^(1+epsilon)) for any epsilon > 0 on the complexity. Moreover, we show that there is a sequence of inputs such that the asymptotic bound on the complexity of their theta-region is Omega(n^2). In addition we point out gaps in the proofs of a recent publication that claims an O(n) bound on the complexity for any constant angle theta.
A Data-Parallel Algorithm to Reliably Solve Systems of Nonlinear Equations
Venue: arXiv cs.NA 2008
Year: 2008

Numerical methods based on interval arithmetic are efficient means to reliably solve nonlinear systems of equations. Algorithm bc3revise is an interval method that tightens variables' domains by enforcing a property called box consistency. It has been successfully used on difficult problems whose solving eluded traditional numerical methods. We present a new algorithm to enforce box consistency that is simpler than bc3revise, faster, and easily data parallelizable. A parallel implementation with Intel SSE2 SIMD instructions shows that an increase in performance of up to an order of magnitude and more is achievable.
On the Capacity Equivalence with Side Information at Transmitter and Receiver
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, a channel that is contaminated by two independent Gaussian noises $S ~ N(0,Q)$ and $Z_0 ~ N(0,N_0)$ is considered. The capacity of this channel is computed when independent noisy versions of $S$ are known to the transmitter and/or receiver. It is shown that the channel capacity is greater then the capacity when $S$ is completely unknown, but is less then the capacity when $S$ is perfectly known at the transmitter or receiver. For example, if there is one noisy version of $S$ known at the transmitter only, the capacity is $0.5\log(1+\frac{P}{Q(N_1/(Q+N_1))+N_0})$, where $P$ is the input power constraint and $N_1$ is the power of the noise corrupting $S$. Further, it is shown that the capacity with knowledge of any independent noisy versions of $S$ at the transmitter is equal to the capacity with knowledge of the statistically equivalent noisy versions of $S$ at the receiver.
Data-Oblivious Stream Productivity
Venue: arXiv cs.LO 2008
Year: 2008

We are concerned with demonstrating productivity of specifications of infinite streams of data, based on orthogonal rewrite rules. In general, this property is undecidable, but for restricted formats computable sufficient conditions can be obtained. The usual analysis disregards the identity of data, thus leading to approaches that we call data-oblivious. We present a method that is provably optimal among all such data-oblivious approaches. This means that in order to improve on the algorithm in this paper one has to proceed in a data-aware fashion.
Weighted Superimposed Codes and Constrained Integer Compressed Sensing
Venue: arXiv cs.IT 2008
Year: 2008

We introduce a new family of codes, termed weighted superimposed codes (WSCs). This family generalizes the class of Euclidean superimposed codes (ESCs), used in multiuser identification systems. WSCs allow for discriminating all bounded, integer-valued linear combinations of real-valued codewords that satisfy prescribed norm and non-negativity constraints. By design, WSCs are inherently noise tolerant. Therefore, these codes can be seen as special instances of robust compressed sensing schemes. The main results of the paper are lower and upper bounds on the largest achievable code rates of several classes of WSCs. These bounds suggest that with the codeword and weighting vector constraints at hand, one can improve the code rates achievable by standard compressive sensing.
A distributed algorithm for computing and updating the process number of a forest
Venue: arXiv cs.DM 2008
Year: 2008

In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms.
Learning Graph Matching
Venue: arXiv cs.CV 2008
Year: 2008

As a fundamental problem in pattern recognition, graph matching has applications in a variety of fields, from computer vision to computational biology. In graph matching, patterns are modeled as graphs and pattern recognition amounts to finding a correspondence between the nodes of different graphs. Many formulations of this problem can be cast in general as a quadratic assignment problem, where a linear term in the objective function encodes node compatibility and a quadratic term encodes edge compatibility. The main research focus in this theme is about designing efficient algorithms for approximately solving the quadratic assignment problem, since it is NP-hard. In this paper we turn our attention to a different question: how to estimate compatibility functions such that the solution of the resulting graph matching problem best matches the expected solution that a human would manually provide. We present a method for learning graph matching: the training examples are pairs of graphs and the `labels' are matches between them. Our experimental results reveal that learning can substantially improve the performance of standard graph matching algorithms. In particular, we find that simple linear assignment with such a learning scheme outperforms Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation algorithm.
Multi Site Coordination using a Multi-Agent System
Venue: arXiv cs.MA 2008
Year: 2008

A new approach of coordination of decisions in a multi site system is proposed. It is based this approach on a multi-agent concept and on the principle of distributed network of enterprises. For this purpose, each enterprise is defined as autonomous and performs simultaneously at the local and global levels. The basic component of our approach is a so-called Virtual Enterprise Node (VEN), where the enterprise network is represented as a set of tiers (like in a product breakdown structure). Within the network, each partner constitutes a VEN, which is in contact with several customers and suppliers. Exchanges between the VENs ensure the autonomy of decision, and guarantiee the consistency of information and material flows. Only two complementary VEN agents are necessary: one for external interactions, the Negotiator Agent (NA) and one for the planning of internal decisions, the Planner Agent (PA). If supply problems occur in the network, two other agents are defined: the Tier Negotiator Agent (TNA) working at the tier level only and the Supply Chain Mediator Agent (SCMA) working at the level of the enterprise network. These two agents are only active when the perturbation occurs. Otherwise, the VENs process the flow of information alone. With this new approach, managing enterprise network becomes much more transparent and looks like managing a simple enterprise in the network. The use of a Multi-Agent System (MAS) allows physical distribution of the decisional system, and procures a heterarchical organization structure with a decentralized control that guaranties the autonomy of each entity and the flexibility of the network.
Atlas-Based Prostate Segmentation Using an Hybrid Registration
Venue: arXiv cs.OH 2008
Year: 2008

Purpose: This paper presents the preliminary results of a semi-automatic method for prostate segmentation of Magnetic Resonance Images (MRI) which aims to be incorporated in a navigation system for prostate brachytherapy. Methods: The method is based on the registration of an anatomical atlas computed from a population of 18 MRI exams onto a patient image. An hybrid registration framework which couples an intensity-based registration with a robust point-matching algorithm is used for both atlas building and atlas registration. Results: The method has been validated on the same dataset that the one used to construct the atlas using the "leave-one-out method". Results gives a mean error of 3.39 mm and a standard deviation of 1.95 mm with respect to expert segmentations. Conclusions: We think that this segmentation tool may be a very valuable help to the clinician for routine quantitative image exploitation.
Conceptualization of seeded region growing by pixels aggregation. Part 2: how to localize a final partition invariant about the seeded region initialisation order
Venue: arXiv cs.CV 2008
Year: 2008

In the previous paper, we have conceptualized the localization and the organization of seeded region growing by pixels aggregation (SRGPA) but we do not give the issue when there is a collision between two distinct regions during the growing process. In this paper, we propose two implementations to manage two classical growing processes: one without a boundary region region to divide the other regions and another with. Unfortunately, as noticed by Mehnert and Jakway (1997), this partition depends on the seeded region initialisation order (SRIO). We propose a growing process, invariant about SRIO such as the boundary region is the set of ambiguous pixels.
A comparison of two approaches for polynomial time algorithms computing basic graph parameters
Venue: arXiv cs.DS 2008
Year: 2008

In this paper we compare and illustrate the algorithmic use of graphs of bounded tree-width and graphs of bounded clique-width. For this purpose we give polynomial time algorithms for computing the four basic graph parameters independence number, clique number, chromatic number, and clique covering number on a given tree structure of graphs of bounded tree-width and graphs of bounded clique-width in polynomial time. We also present linear time algorithms for computing the latter four basic graph parameters on trees, i.e. graphs of tree-width 1, and on co-graphs, i.e. graphs of clique-width at most 2.
Implementation for blow up of tornado-type solutions for complex version of 3D Navier-Stokes system
Venue: arXiv cs.NA 2008
Year: 2008

We consider Cauchy problem for Fourier transformation of 3-dimensional Navier-Stokes system with zero external force. Using initial data purposed by Dong Li and Ya.G.Sinai we implement self-similar regime producing fast growing behavior of the energy of solution while time tends to critical value.
Approximability and parameterized complexity of minmax values
Venue: arXiv cs.GT 2008
Year: 2008

We consider approximating the minmax value of a multi-player game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of epsilon log n digits (for any constant epsilon>0 is NP-hard, where n is the size of the game. On the other hand, approximating the value with a precision of c log log n digits (for any constant c >= 1) can be done in quasi-polynomial time. We consider the parameterized complexity of the problem, with the parameter being the number of pure strategies k of the player for which the minmax value is computed. We show that if there are three players, k=2 and there are only two possible rational payoffs, the minmax value is a rational number and can be computed exactly in linear time. In the general case, we show that the value can be approximated with any polynomial number of digits of accuracy in time n^(O(k)). On the other hand, we show that minmax value approximation is W[1]-hard and hence not likely to be fixed parameter tractable. Concretely, we show that if k-CLIQUE requires time n^(Omega(k)) then so does minmax value computation.
Prediction with Expert Advice in Games with Unbounded One-Step Gains
Venue: arXiv cs.LG 2008
Year: 2008

The games of prediction with expert advice are considered in this paper. We present some modification of Kalai and Vempala algorithm of following the perturbed leader for the case of unrestrictedly large one-step gains. We show that in general case the cumulative gain of any probabilistic prediction algorithm can be much worse than the gain of some expert of the pool. Nevertheless, we give the lower bound for this cumulative gain in general case and construct a universal algorithm which has the optimal performance; we also prove that in case when one-step gains of experts of the pool have ``limited deviations'' the performance of our algorithm is close to the performance of the best expert.
WiPal: Efficient Offline Merging of IEEE 802.11 Traces
Venue: arXiv cs.NI 2008
Year: 2008

Merging wireless traces is a fundamental step in measurement-based studies involving multiple packet sniffers. Existing merging tools either require a wired infrastructure or are limited in their usability. We propose WiPal, an offline merging tool for IEEE 802.11 traces that has been designed to be efficient and simple to use. WiPal is flexible in the sense that it does not require any specific services, neither from monitors (like synchronization, access to a wired network, or embedding specific software) nor from its software environment (e.g. an SQL server). We present WiPal's operation and show how its features - notably, its modular design - improve both ease of use and efficiency. Experiments on real traces show that WiPal is an order of magnitude faster than other tools providing the same features. To our knowledge, WiPal is the only offline trace merger that can be used by the research community in a straightforward fashion.
Structural Damage Detection Using Randomized Trained Neural Networks
Venue: arXiv cs.NE 2008
Year: 2008

A computationally method on damage detection problems in structures was conducted using neural networks. The problem that is considered in this works consists of estimating the existence, location and extent of stiffness reduction in structure which is indicated by the changes of the structural static parameters such as deflection and strain. The neural network was trained to recognize the behaviour of static parameter of the undamaged structure as well as of the structure with various possible damage extent and location which were modelled as random states. The proposed techniques were applied to detect damage in a simply supported beam. The structure was analyzed using finite-element-method (FEM) and the damage identification was conducted by a back-propagation neural network using the change of the structural strain and displacement. The results showed that using proposed method the strain is more efficient for identification of damage than the displacement.
Nested Ordered Sets and their Use for Data Modelling
Venue: arXiv cs.DB 2008
Year: 2008

In this paper we present a new approach to data modelling, called the concept-oriented model (CoM), and describe its main features and characteristics including data semantics and operations. The distinguishing feature of this model is that it is based on the formalism of nested ordered sets where any element participates in two structures simultaneously: hierarchical (nested) and multi-dimensional (ordered). An element of the model is postulated to consist of two parts, called identity and entity, and the whole approach can be naturally broken into two branches: identity modelling and entity modelling. We also propose a new query language with the main construct, called concept, defined as a pair of two classes: identity class and entity class. We describe how its operations of projection, de-projection and product can be used to solve typical data modelling tasks.
On stars and Steiner stars. II
Venue: arXiv cs.CG 2008
Year: 2008

A {\em Steiner star} for a set $P$ of $n$ points in $\RR^d$ connects an arbitrary center point to all points of $P$, while a {\em star} connects a point $p\in P$ to the remaining $n-1$ points of $P$. All connections are realized by straight line segments. Fekete and Meijer showed that the minimum star is at most $\sqrt{2}$ times longer than the minimum Steiner star for any finite point configuration in $\RR^d$. The maximum ratio between them, over all finite point configurations in $\RR^d$, is called the {\em star Steiner ratio} in $\RR^d$. It is conjectured that this ratio is $4/π= 1.2732...$ in the plane and $4/3=1.3333...$ in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space, thereby substantially improving recent upper bounds of 1.3999, and $\sqrt{2}-10^{-4}$, respectively. Our results also imply improved bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions.