OpenRaiser/Intern-Atlas huggingface dataset:
A DNA Sequence Compression Algorithm Based on LUT and LZ77
Venue: arXiv cs.IT 2005
Year: 2005

This article introduces a new DNA sequence compression algorithm which is based on LUT and LZ77 algorithm. Combined a LUT-based pre-coding routine and LZ77 compression routine,this algorithm can approach a compression ratio of 1.9bits \slash base and even lower.The biggest advantage of this algorithm is fast execution, small memory occupation and easy implementation.
A Distributed Multimedia Communication System and its Applications to E-Learning
Venue: arXiv cs.MM 2005
Year: 2005

In this paper we report on a multimedia communication system including a VCoIP (Video Conferencing over IP) software with a distributed architecture and its applications for teaching scenarios. It is a simple, ready-to-use scheme for distributed presenting, recording and streaming multimedia content. We also introduce and investigate concepts and experiments to IPv6 user and session mobility, with the special focus on real-time video group communication.
Cooperative Game Theory within Multi-Agent Systems for Systems Scheduling
Venue: arXiv cs.AI 2005
Year: 2005

Research concerning organization and coordination within multi-agent systems continues to draw from a variety of architectures and methodologies. The work presented in this paper combines techniques from game theory and multi-agent systems to produce self-organizing, polymorphic, lightweight, embedded agents for systems scheduling within a large-scale real-time systems environment. Results show how this approach is used to experimentally produce optimum real-time scheduling through the emergent behavior of thousands of agents. These results are obtained using a SWARM simulation of systems scheduling within a High Energy Physics experiment consisting of 2500 digital signal processors.
Prototype of Fault Adaptive Embedded Software for Large-Scale Real-Time Systems
Venue: arXiv cs.SE 2005
Year: 2005

This paper describes a comprehensive prototype of large-scale fault adaptive embedded software developed for the proposed Fermilab BTeV high energy physics experiment. Lightweight self-optimizing agents embedded within Level 1 of the prototype are responsible for proactive and reactive monitoring and mitigation based on specified layers of competence. The agents are self-protecting, detecting cascading failures using a distributed approach. Adaptive, reconfigurable, and mobile objects for reliablility are designed to be self-configuring to adapt automatically to dynamically changing environments. These objects provide a self-healing layer with the ability to discover, diagnose, and react to discontinuities in real-time processing. A generic modeling environment was developed to facilitate design and implementation of hardware resource specifications, application data flow, and failure mitigation strategies. Level 1 of the planned BTeV trigger system alone will consist of 2500 DSPs, so the number of components and intractable fault scenarios involved make it impossible to design an `expert system' that applies traditional centralized mitigative strategies based on rules capturing every possible system state. Instead, a distributed reactive approach is implemented using the tools and methodologies developed by the Real-Time Embedded Systems group.
Efficient and Robust Geocasting Protocols for Sensor Networks
Venue: arXiv cs.NI 2005
Year: 2005

Geocasting is the delivery of packets to nodes within a certain geographic area. For many applications in wireless ad hoc and sensor networks, geocasting is an important and frequent communication service. The challenging problem in geocasting is distributing the packets to all the nodes within the geocast region with high probability but with low overhead. According to our study we notice a clear tradeoff between the proportion of nodes in the geocast region that receive the packet and the overhead incurred by the geocast packet especially at low densities and irregular distributions. We present two novel protocols for geocasting that achieve high delivery rate and low overhead by utilizing the local location information of nodes to combine geographic routing mechanisms with region flooding. We show that the first protocol Geographic-Forwarding-Geocast (GFG) has close-to-minimum overhead in dense networks and that the second protocol Geographic-Forwarding-Perimeter-Geocast (GFPG) provides guaranteed delivery without global flooding or global network information even at low densities and with the existence of region gaps or obstacles. An adaptive version of the second protocol (GFPG*) has the desirable property of perfect delivery at all densities and close-to-minimum overhead at high densities. We evaluate our mechanisms and compare them using simulation to other proposed geocasting mechanisms. The results show the significant improvement in delivery rate (up to 63% higher delivery percentage in low density networks) and reduction in overhead (up to 80% reduction) achieved by our mechanisms. We hope for our protocols to become building block mechanisms for dependable sensor network architectures that require robust efficient geocast services.
A New Kind of Hopfield Networks for Finding Global Optimum
Venue: arXiv cs.NE 2005
Year: 2005

The Hopfield network has been applied to solve optimization problems over decades. However, it still has many limitations in accomplishing this task. Most of them are inherited from the optimization algorithms it implements. The computation of a Hopfield network, defined by a set of difference equations, can easily be trapped into one local optimum or another, sensitive to initial conditions, perturbations, and neuron update orders. It doesn't know how long it will take to converge, as well as if the final solution is a global optimum, or not. In this paper, we present a Hopfield network with a new set of difference equations to fix those problems. The difference equations directly implement a new powerful optimization algorithm.
Pluggable AOP: Designing Aspect Mechanisms for Third-party Composition
Venue: arXiv cs.SE 2005
Year: 2005

Studies of Aspect-Oriented Programming (AOP) usually focus on a language in which a specific aspect extension is integrated with a base language. Languages specified in this manner have a fixed, non-extensible AOP functionality. In this paper we consider the more general case of integrating a base language with a set of domain specific third-party aspect extensions for that language. We present a general mixin-based method for implementing aspect extensions in such a way that multiple, independently developed, dynamic aspect extensions can be subject to third-party composition and work collaboratively.
Temporal and Spatial Data Mining with Second-Order Hidden Models
Venue: arXiv cs.AI 2005
Year: 2005

In the frame of designing a knowledge discovery system, we have developed stochastic models based on high-order hidden Markov models. These models are capable to map sequences of data into a Markov chain in which the transitions between the states depend on the \texttt{n} previous states according to the order of the model. We study the process of achieving information extraction fromspatial and temporal data by means of an unsupervised classification. We use therefore a French national database related to the land use of a region, named Teruti, which describes the land use both in the spatial and temporal domain. Land-use categories (wheat, corn, forest, ...) are logged every year on each site regularly spaced in the region. They constitute a temporal sequence of images in which we look for spatial and temporal dependencies. The temporal segmentation of the data is done by means of a second-order Hidden Markov Model (\hmmd) that appears to have very good capabilities to locate stationary segments, as shown in our previous work in speech recognition. Thespatial classification is performed by defining a fractal scanning ofthe images with the help of a Hilbert-Peano curve that introduces atotal order on the sites, preserving the relation ofneighborhood between the sites. We show that the \hmmd performs aclassification that is meaningful for the agronomists.Spatial and temporal classification may be achieved simultaneously by means of a 2 levels \hmmd that measures the \aposteriori probability to map a temporal sequence of images onto a set of hidden classes.
Automatic Verification of Timed Concurrent Constraint Programs
Venue: arXiv cs.LO 2005
Year: 2005

The language Timed Concurrent Constraint (tccp) is the extension over time of the Concurrent Constraint Programming (cc) paradigm that allows us to specify concurrent systems where timing is critical, for example reactive systems. Systems which may have an infinite number of states can be specified in tccp. Model checking is a technique which is able to verify finite-state systems with a huge number of states in an automatic way. In the last years several studies have investigated how to extend model checking techniques to systems with an infinite number of states. In this paper we propose an approach which exploits the computation model of tccp. Constraint based computations allow us to define a methodology for applying a model checking algorithm to (a class of) infinite-state systems. We extend the classical algorithm of model checking for LTL to a specific logic defined for the verification of tccp and to the tccp Structure which we define in this work for modeling the program behavior. We define a restriction on the time in order to get a finite model and then we develop some illustrative examples. To the best of our knowledge this is the first approach that defines a model checking methodology for tccp.
Efficient Management of Short-Lived Data
Venue: arXiv cs.DB 2005
Year: 2005

Motivated by the increasing prominence of loosely-coupled systems, such as mobile and sensor networks, which are characterised by intermittent connectivity and volatile data, we study the tagging of data with so-called expiration times. More specifically, when data are inserted into a database, they may be tagged with time values indicating when they expire, i.e., when they are regarded as stale or invalid and thus are no longer considered part of the database. In a number of applications, expiration times are known and can be assigned at insertion time. We present data structures and algorithms for online management of data tagged with expiration times. The algorithms are based on fully functional, persistent treaps, which are a combination of binary search trees with respect to a primary attribute and heaps with respect to a secondary attribute. The primary attribute implements primary keys, and the secondary attribute stores expiration times in a minimum heap, thus keeping a priority queue of tuples to expire. A detailed and comprehensive experimental study demonstrates the well-behavedness and scalability of the approach as well as its efficiency with respect to a number of competitors.
Iterative MILP Methods for Vehicle Control Problems
Venue: arXiv cs.RO 2005
Year: 2005

Mixed integer linear programming (MILP) is a powerful tool for planning and control problems because of its modeling capability and the availability of good solvers. However, for large models, MILP methods suffer computationally. In this paper, we present iterative MILP algorithms that address this issue. We consider trajectory generation problems with obstacle avoidance requirements and minimum time trajectory generation problems. The algorithms use fewer binary variables than standard MILP methods and require less computational effort.
A T Step Ahead Optimal Target Detection Algorithm for a Multi Sensor Surveillance System
Venue: arXiv cs.MA 2005
Year: 2005

This paper presents a methodology for optimal target detection in a multi sensor surveillance system. The system consists of mobile sensors that guard a rectangular surveillance zone crisscrossed by moving targets. Targets percolate the surveillance zone in a poisson fashion with uniform velocities. Under these statistics this paper computes a motion strategy for a sensor that maximizes target detections for the next T time steps. A coordination mechanism between sensors ensures that overlapping areas between sensors is reduced. This coordination mechanism is interleaved with the motion strategy computation to reduce detections of the same target by more than one sensor. To avoid an exhaustive search in the joint space of all sensors the coordination mechanism constraints the search by assigning priorities to the sensors. A comparison of this methodology with other multi target tracking schemes verifies its efficacy in maximizing detections. A tabulation of these comparisons is reported in results section of the paper
Sub-Optimum Signal Linear Detector Using Wavelets and Support Vector Machines
Venue: arXiv cs.IR 2005
Year: 2005

The problem of known signal detection in Additive White Gaussian Noise is considered. In previous work, a new detection scheme was introduced by the authors, and it was demonstrated that optimum performance cannot be reached in a real implementation. In this paper we analyse Support Vector Machines (SVM) as an alternative, evaluating the results in terms of Probability of detection curves for a fixed Probability of false alarm.
A dissipative particle swarm optimization
Venue: arXiv cs.NE 2005
Year: 2005

A dissipative particle swarm optimization is developed according to the self-organization of dissipative structure. The negative entropy is introduced to construct an opening dissipative system that is far-from-equilibrium so as to driving the irreversible evolution process with better fitness. The testing of two multimodal functions indicates it improves the performance effectively
On the Solution of Graph Isomorphism by Dynamical Algorithms
Venue: arXiv cs.CC 2005
Year: 2005

In the recent years, several polynomial algorithms of a dynamical nature have been proposed to address the graph isomorphism problem. In this paper we propose a generalization of an approach exposed in cond-mat/0209112 and find that this dynamical algorithm is covered by a combinatorial approach. It is possible to infer that polynomial dynamical algorithms addressing graph isomorphism are covered by suitable polynomial combinatorial approaches and thus are tackled by the same weaknesses as the last ones.
Authentication and routing in simple Quantum Key Distribution networks
Venue: arXiv cs.NI 2005
Year: 2005

We consider various issues which arise as soon as one tries to practically implement simple networks of quantum relays for QKD. In particular we discuss authentication and routing which are essential ingredients of any QKD network. This paper aims to address some gaps between quantum and networking aspects of QKD networks usually reserved to specialist in physics and computer science respectively.
Defensive forecasting for linear protocols
Venue: arXiv cs.LG 2005
Year: 2005

We consider a general class of forecasting protocols, called "linear protocols", and discuss several important special cases, including multi-class forecasting. Forecasting is formalized as a game between three players: Reality, whose role is to generate observations; Forecaster, whose goal is to predict the observations; and Skeptic, who tries to make money on any lack of agreement between Forecaster's predictions and the actual observations. Our main mathematical result is that for any continuous strategy for Skeptic in a linear protocol there exists a strategy for Forecaster that does not allow Skeptic's capital to grow. This result is a meta-theorem that allows one to transform any continuous law of probability in a linear protocol into a forecasting strategy whose predictions are guaranteed to satisfy this law. We apply this meta-theorem to a weak law of large numbers in Hilbert spaces to obtain a version of the K29 prediction algorithm for linear protocols and show that this version also satisfies the attractive properties of proper calibration and resolution under a suitable choice of its kernel parameter, with no assumptions about the way the data is generated.
The Equivalence Problem for Deterministic MSO Tree Transducers is Decidable
Venue: arXiv cs.LO 2005
Year: 2005

It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.
On the Throughput-Delay Tradeoff in Cellular Multicast
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we adopt a cross layer design approach for analyzing the throughput-delay tradeoff of the multicast channel in a single cell system. To illustrate the main ideas, we start with the single group case, i.e., pure multicast, where a common information stream is requested by all the users. We consider three classes of scheduling algorithms with progressively increasing complexity. The first class strives for minimum complexity by resorting to a static scheduling strategy along with memoryless decoding. Our analysis for this class of scheduling algorithms reveals the existence of a static scheduling policy that achieves the optimal scaling law of the throughput at the expense of a delay that increases exponentially with the number of users. The second scheduling policy resorts to a higher complexity incremental redundancy encoding/decoding strategy to achieve a superior throughput-delay tradeoff. The third, and most complex, scheduling strategy benefits from the cooperation between the different users to minimize the delay while achieving the optimal scaling law of the throughput. In particular, the proposed cooperative multicast strategy is shown to simultaneously achieve the optimal scaling laws of both throughput and delay. Then, we generalize our scheduling algorithms to exploit the multi-group diversity available when different information streams are requested by different subsets of the user population. Finally, we discuss the effect of the potential gains of equipping the base station with multi-transmit antennas and present simulation results that validate our theoretical claims.
Asymptotics of Discrete MDL for Online Prediction
Venue: arXiv cs.IT 2005
Year: 2005

Minimum Description Length (MDL) is an important principle for induction and prediction, with strong relations to optimal Bayesian learning. This paper deals with learning non-i.i.d. processes by means of two-part MDL, where the underlying model class is countable. We consider the online learning framework, i.e. observations come in one by one, and the predictor is allowed to update his state of mind after each time step. We identify two ways of predicting by MDL for this setup, namely a static} and a dynamic one. (A third variant, hybrid MDL, will turn out inferior.) We will prove that under the only assumption that the data is generated by a distribution contained in the model class, the MDL predictions converge to the true values almost surely. This is accomplished by proving finite bounds on the quadratic, the Hellinger, and the Kullback-Leibler loss of the MDL learner, which are however exponentially worse than for Bayesian prediction. We demonstrate that these bounds are sharp, even for model classes containing only Bernoulli distributions. We show how these bounds imply regret bounds for arbitrary loss functions. Our results apply to a wide range of setups, namely sequence prediction, pattern classification, regression, and universal induction in the sense of Algorithmic Information Theory among others.
Sorting a Low-Entropy Sequence
Venue: arXiv cs.DS 2005
Year: 2005

We give the first sorting algorithm with bounds in terms of higher-order entropies: let $S$ be a sequence of length $m$ containing $n$ distinct elements and let (H_\ell (S)) be the $\ell$th-order empirical entropy of $S$, with (n^{\ell + 1} \log n \in O (m)); our algorithm sorts $S$ using ((H_\ell (S) + O (1)) m) comparisons.
Tree-Based Construction of LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

We present a construction of LDPC codes that have minimum pseudocodeword weight equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a d-regular tree for a fixed number of layers and employing a connection algorithm based on mutually orthogonal Latin squares to close the tree. Methods are presented for degrees d=p^s and d = p^s+1, for p a prime, -- one of which includes the well-known finite-geometry-based LDPC codes.
Exploitation de dictionnaires électroniques pour la désambiguïsation sémantique lexicale
Venue: arXiv cs.DL 2005
Year: 2005

This paper presents a lexical disambiguation system, initially developed for English and now adapted to French. This system associates a word with its meaning in a given context using electronic dictionaries as semantically annotated corpora in order to extract semantic disambiguation rules. We describe the rule extraction and application process as well as the evaluation of the system. The results for French give us insight information on some possible improvments of the nature and content of lexical resources adapted for disambiguation in this framework.
Analysis on Transmit Antenna Selection for Spatial Multiplexing Systems: A Geometrical Approach
Venue: arXiv cs.IT 2005
Year: 2005

Recently, the remarkable potential of a multiple-input multiple-output (MIMO) wireless communication system was unveiled for its ability to provide spatial diversity or multiplexing gains. For MIMO diversity schemes, it is already known that. by the optimal antenna selection maximizing the post-processing signal-to-noise ratio, the diversity order of the full system can be maintained. On the other hand, the diversity order achieved by antenna selection in spatial multiplexing systems, especially those exploiting practical coding and decoding schemes, has not been rigorously analyzed thus far. In this paper, from a geometric standpoint, we propose a new framework for theoretically analyzing the diversity order achieved by transmit antenna selection for separately encoded spatial multiplexing systems with linear and decision-feedback receivers. We rigorously show that a diversity order of (Nt-1)(Nr-1) can be achieved for an Nr by Nt SM system when L=2 antennas are selected from the transmit side; while for L>2 scenarios, we give bounds for the achievable diversity order and show that the optimal diversity order is at least (Nt-L+1)(Nr-L+1) . Furthermore, the same geometrical approach can be used to evaluate the diversity-multiplexing tradeoff curves for the considered spatial multiplexing systems with transmit antenna selection.
Priority-Based Conflict Resolution in Inconsistent Relational Databases
Venue: arXiv cs.DB 2005
Year: 2005

We study here the impact of priorities on conflict resolution in inconsistent relational databases. We extend the framework of repairs and consistent query answers. We propose a set of postulates that an extended framework should satisfy and consider two instantiations of the framework: (locally preferred) l-repairs and (globally preferred) g-repairs. We study the relationships between them and the impact each notion of repair has on the computational complexity of repair checking and consistent query answers.
Optimal multiple assignments based on integer programming in secret sharing schemes with general access structures
Venue: arXiv cs.CR 2005
Year: 2005

It is known that for any general access structure, a secret sharing scheme (SSS) can be constructed from an (m,m)-threshold scheme by using the so-called cumulative map or from a (t,m)-threshold SSS by a modified cumulative map. However, such constructed SSSs are not efficient generally. In this paper, we propose a new method to construct a SSS from a $(t,m)$-threshold scheme for any given general access structure. In the proposed method, integer programming is used to distribute optimally the shares of (t,m)-threshold scheme to each participant of the general access structure. From the optimality, it can always attain lower coding rate than the cumulative maps except the cases that they give the optimal distribution. The same method is also applied to construct SSSs for incomplete access structures and/or ramp access structures.