OpenRaiser/Intern-Atlas huggingface dataset:
Experimenting with recursive queries in database and logic programming systems
Venue: arXiv cs.AI 2007
Year: 2007

This paper considers the problem of reasoning on massive amounts of (possibly distributed) data. Presently, existing proposals show some limitations: {\em (i)} the quantity of data that can be handled contemporarily is limited, due to the fact that reasoning is generally carried out in main-memory; {\em (ii)} the interaction with external (and independent) DBMSs is not trivial and, in several cases, not allowed at all; {\em (iii)} the efficiency of present implementations is still not sufficient for their utilization in complex reasoning tasks involving massive amounts of data. This paper provides a contribution in this setting; it presents a new system, called DLV$^{DB}$, which aims to solve these problems. Moreover, the paper reports the results of a thorough experimental analysis we have carried out for comparing our system with several state-of-the-art systems (both logic and databases) on some classical deductive problems; the other tested systems are: LDL++, XSB, Smodels and three top-level commercial DBMSs. DLV$^{DB}$ significantly outperforms even the commercial Database Systems on recursive queries. To appear in Theory and Practice of Logic Programming (TPLP)
Generalized Stability Condition for Generalized and Doubly-Generalized LDPC Codes
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, the stability condition for low-density parity-check (LDPC) codes on the binary erasure channel (BEC) is extended to generalized LDPC (GLDPC) codes and doublygeneralized LDPC (D-GLDPC) codes. It is proved that, in both cases, the stability condition only involves the component codes with minimum distance 2. The stability condition for GLDPC codes is always expressed as an upper bound to the decoding threshold. This is not possible for D-GLDPC codes, unless all the generalized variable nodes have minimum distance at least 3. Furthermore, a condition called derivative matching is defined in the paper. This condition is sufficient for a GLDPC or DGLDPC code to achieve the stability condition with equality. If this condition is satisfied, the threshold of D-GLDPC codes (whose generalized variable nodes have all minimum distance at least 3) and GLDPC codes can be expressed in closed form.
Estimation Diversity and Energy Efficiency in Distributed Sensing
Venue: arXiv cs.IT 2007
Year: 2007

Distributed estimation based on measurements from multiple wireless sensors is investigated. It is assumed that a group of sensors observe the same quantity in independent additive observation noises with possibly different variances. The observations are transmitted using amplify-and-forward (analog) transmissions over non-ideal fading wireless channels from the sensors to a fusion center, where they are combined to generate an estimate of the observed quantity. Assuming that the Best Linear Unbiased Estimator (BLUE) is used by the fusion center, the equal-power transmission strategy is first discussed, where the system performance is analyzed by introducing the concept of estimation outage and estimation diversity, and it is shown that there is an achievable diversity gain on the order of the number of sensors. The optimal power allocation strategies are then considered for two cases: minimum distortion under power constraints; and minimum power under distortion constraints. In the first case, it is shown that by turning off bad sensors, i.e., sensors with bad channels and bad observation quality, adaptive power gain can be achieved without sacrificing diversity gain. Here, the adaptive power gain is similar to the array gain achieved in Multiple-Input Single-Output (MISO) multi-antenna systems when channel conditions are known to the transmitter. In the second case, the sum power is minimized under zero-outage estimation distortion constraint, and some related energy efficiency issues in sensor networks are discussed.
Bayesian approach to rough set
Venue: arXiv cs.AI 2007
Year: 2007

This paper proposes an approach to training rough set models using Bayesian framework trained using Markov Chain Monte Carlo (MCMC) method. The prior probabilities are constructed from the prior knowledge that good rough set models have fewer rules. Markov Chain Monte Carlo sampling is conducted through sampling in the rough set granule space and Metropolis algorithm is used as an acceptance criteria. The proposed method is tested to estimate the risk of HIV given demographic data. The results obtained shows that the proposed approach is able to achieve an average accuracy of 58% with the accuracy varying up to 66%. In addition the Bayesian rough set give the probabilities of the estimated HIV status as well as the linguistic rules describing how the demographic parameters drive the risk of HIV.
On Energy Efficient Hierarchical Cross-Layer Design: Joint Power Control and Routing for Ad Hoc Networks
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, a hierarchical cross-layer design approach is proposed to increase energy efficiency in ad hoc networks through joint adaptation of nodes' transmitting powers and route selection. The design maintains the advantages of the classic OSI model, while accounting for the cross-coupling between layers, through information sharing. The proposed joint power control and routing algorithm is shown to increase significantly the overall energy efficiency of the network, at the expense of a moderate increase in complexity. Performance enhancement of the joint design using multiuser detection is also investigated, and it is shown that the use of multiuser detection can increase the capacity of the ad hoc network significantly for a given level of energy consumption.
Avoiding Rotated Bitboards with Direct Lookup
Venue: arXiv cs.DS 2007
Year: 2007

This paper describes an approach for obtaining direct access to the attacked squares of sliding pieces without resorting to rotated bitboards. The technique involves creating four hash tables using the built in hash arrays from an interpreted, high level language. The rank, file, and diagonal occupancy are first isolated by masking the desired portion of the board. The attacked squares are then directly retrieved from the hash tables. Maintaining incrementally updated rotated bitboards becomes unnecessary as does all the updating, mapping and shifting required to access the attacked squares. Finally, rotated bitboard move generation speed is compared with that of the direct hash table lookup method.
A Note on Ontology and Ordinary Language
Venue: arXiv cs.AI 2007
Year: 2007

We argue for a compositional semantics grounded in a strongly typed ontology that reflects our commonsense view of the world and the way we talk about it. Assuming such a structure we show that the semantics of various natural language phenomena may become nearly trivial.
Using Images to create a Hierarchical Grid Spatial Index
Venue: arXiv cs.DS 2007
Year: 2007

This paper presents a hybrid approach to spatial indexing of two dimensional data. It sheds new light on the age old problem by thinking of the traditional algorithms as working with images. Inspiration is drawn from an analogous situation that is found in machine and human vision. Image processing techniques are used to assist in the spatial indexing of the data. A fixed grid approach is used and bins with too many records are sub-divided hierarchically. Search queries are pre-computed for bins that do not contain any data records. This has the effect of dividing the search space up into non rectangular regions which are based on the spatial properties of the data. The bucketing quad tree can be considered as an image with a resolution of two by two for each layer. The results show that this method performs better than the quad tree if there are more divisions per layer. This confirms our suspicions that the algorithm works better if it gets to look at the data with higher resolution images. An elegant class structure is developed where the implementation of concrete spatial indexes for a particular data type merely relies on rendering the data onto an image.
More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
Venue: arXiv cs.IT 2007
Year: 2007

There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known polynomial time algorithm for solving it optimally there are many good heuristics that all provide additive errors to optimal. The additive error in these algorithms usually depends linearly upon the largest encoding letter size. This paper was motivated by the problem of finding optimal codes when the encoding alphabet is infinite. Because the largest letter cost is infinite, the previous analyses could give infinite error bounds. We provide a new algorithm that works with infinite encoding alphabets. When restricted to the finite alphabet case, our algorithm often provides better error bounds than the best previous ones known.
Inverse-free Berlekamp-Massey-Sakata Algorithm and Small Decoders for Algebraic-Geometric Codes
Venue: arXiv cs.IT 2007
Year: 2007

This paper proposes a novel algorithm for finding error-locators of algebraic-geometric codes that can eliminate the division-calculations of finite fields from the Berlekamp-Massey-Sakata algorithm. This inverse-free algorithm provides full performance in correcting a certain class of errors, generic errors, which includes most errors, and can decode codes on algebraic curves without the determination of unknown syndromes. Moreover, we propose three different kinds of architectures that our algorithm can be applied to, and we represent the control operation of shift-registers and switches at each clock-timing with numerical simulations. We estimate the performance in comparison of the total running time and the numbers of multipliers and shift-registers in three architectures with those of the conventional ones for codes on algebraic curves.
Encoding for the Blackwell Channel with Reinforced Belief Propagation
Venue: arXiv cs.IT 2007
Year: 2007

A key idea in coding for the broadcast channel (BC) is binning, in which the transmitter encode information by selecting a codeword from an appropriate bin (the messages are thus the bin indexes). This selection is normally done by solving an appropriate (possibly difficult) combinatorial problem. Recently it has been shown that binning for the Blackwell channel --a particular BC-- can be done by iterative schemes based on Survey Propagation (SP). This method uses decimation for SP and suffers a complexity of O(n^2). In this paper we propose a new variation of the Belief Propagation (BP) algorithm, named Reinforced BP algorithm, that turns BP into a solver. Our simulations show that this new algorithm has complexity O(n log n). Using this new algorithm together with a non-linear coding scheme, we can efficiently achieve rates close to the border of the capacity region of the Blackwell channel.
Clustering Co-occurrence of Maximal Frequent Patterns in Streams
Venue: arXiv cs.AI 2007
Year: 2007

One way of getting a better view of data is using frequent patterns. In this paper frequent patterns are subsets that occur a minimal number of times in a stream of itemsets. However, the discovery of frequent patterns in streams has always been problematic. Because streams are potentially endless it is in principle impossible to say if a pattern is often occurring or not. Furthermore the number of patterns can be huge and a good overview of the structure of the stream is lost quickly. The proposed approach will use clustering to facilitate the analysis of the structure of the stream. A clustering on the co-occurrence of patterns will give the user an improved view on the structure of the stream. Some patterns might occur so much together that they should form a combined pattern. In this way the patterns in the clustering will be the largest frequent patterns: maximal frequent patterns. Our approach to decide if patterns occur often together will be based on a method of clustering when only the distance between pairs is known. The number of maximal frequent patterns is much smaller and combined with clustering methods these patterns provide a good view on the structure of the stream.
Moving Walkways, Escalators, and Elevators
Venue: arXiv cs.CG 2007
Year: 2007

We study a simple geometric model of transportation facility that consists of two points between which the travel speed is high. This elementary definition can model shuttle services, tunnels, bridges, teleportation devices, escalators or moving walkways. The travel time between a pair of points is defined as a time distance, in such a way that a customer uses the transportation facility only if it is helpful. We give algorithms for finding the optimal location of such a transportation facility, where optimality is defined with respect to the maximum travel time between two points in a given set.
Soft constraint abstraction based on semiring homomorphism
Venue: arXiv cs.AI 2007
Year: 2007

The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi \cite{BMR97}, is a very general framework of soft constraints. In this paper we propose an abstraction scheme for soft constraints that uses semiring homomorphism. To find optimal solutions of the concrete problem, the idea is, first working in the abstract problem and finding its optimal solutions, then using them to solve the concrete problem. In particular, we show that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism. Moreover, for a semiring homomorphism $α$ and a problem $P$ over $S$, if $t$ is optimal in $α(P)$, then there is an optimal solution $\bar{t}$ of $P$ such that $\bar{t}$ has the same value as $t$ in $α(P)$.
The Optimization of a Novel Prismatic Drive
Venue: arXiv cs.RO 2007
Year: 2007

The design of a mechanical transmission taking into account the transmitted forces is reported in this paper. This transmission is based on Slide-o-Cam, a cam mechanism with multiple rollers mounted on a common translating follower. The design of Slide-o-Cam, a transmission intended to produce a sliding motion from a turning drive, or vice versa, was reported elsewhere. This transmission provides pure-rolling motion, thereby reducing the friction of rack-and-pinions and linear drives. The pressure angle is a relevant performance index for this transmission because it determines the amount of force transmitted to the load vs. that transmitted to the machine frame. To assess the transmission capability of the mechanism, the Hertz formula is introduced to calculate the stresses on the rollers and on the cams. The final transmission is intended to replace the current ball-screws in the Orthoglide, a three-DOF parallel robot for the production of translational motions, currently under development for machining applications at Ecole Centrale de Nantes.
ANDNA: the distributed hostname management system of Netsukuku
Venue: arXiv cs.NI 2007
Year: 2007

We present the Abnormal Netsukuku Domain Name Anarchy system. ANDNA is the distributed, non hierarchical and decentralised system of hostname management used in the Netsukuku network.
The Multiobjective Optimization of a Prismatic Drive
Venue: arXiv cs.RO 2007
Year: 2007

The multiobjective optimization of Slide-o-Cam is reported in this paper. Slide-o-Cam is a cam mechanism with multiple rollers mounted on a common translating follower. This transmission provides pure-rolling motion, thereby reducing the friction of rack-and-pinions and linear drives. A Pareto frontier is obtained by means of multiobjective optimization. This optimization is based on three objective functions: (i) the pressure angle, which is a suitable performance index for the transmission because it determines the amount of force transmitted to the load vs. that transmitted to the machine frame; (ii) the Hertz pressure used to evaluate the stresses produced on the contact surface between cam and roller; and (iii) the size of the mechanism, characterized by the number of cams and their width.
Game-Theoretic Power Control in Impulse Radio UWB Wireless Networks
Venue: arXiv cs.GT 2007
Year: 2007

In this paper, a game-theoretic model for studying power control for wireless data networks in frequency-selective multipath environments is analyzed. The uplink of an impulse-radio ultrawideband system is considered. The effects of self-interference and multiple-access interference on the performance of Rake receivers are investigated for synchronous systems. Focusing on energy efficiency, a noncooperative game is proposed in which users in the network are allowed to choose their transmit powers to maximize their own utilities, and the Nash equilibrium for the proposed game is derived. It is shown that, due to the frequency selective multipath, the noncooperative solution is achieved at different signal-to-interference-plus-noise ratios, respectively of the channel realization. A large-system analysis is performed to derive explicit expressions for the achieved utilities. The Pareto-optimal (cooperative) solution is also discussed and compared with the noncooperative approach.
Uniqueness Domains in the Workspace of Parallel Manipulators
Venue: arXiv cs.RO 2007
Year: 2007

This work investigates new kinematic features of parallel manipulators. It is well known that parallel manipulators admit generally several direct kinematic solutions for a given set of input joint values. The aim of this paper is to characterize the uniqueness domains in the workspace of parallel manipulators, as well as their image in the joint space. The study focuses on the most usual case of parallel manipulators with only one inverse kinematic solution. The notion of aspect introduced for serial manipulators in [Borrel 86] is redefined for such parallel manipulators. Then, it is shown that it is possible to link several solutions to the forward kinematic problem without meeting a singularity, thus meaning that the aspects are not uniqueness domains. An additional set of surfaces, namely the characteristic surfaces, are characterized which divide the workspace into basic regions and yield new uniqueness domains. This study is illustrated all along the paper with a 3-RPR planar parallel manipulator. An octree model of spaces is used to compute the joint space, the workspace and all other newly defined sets.
Séparation des Solutions aux Modèles Géométriques Direct et Inverse pour les Manipulateurs Pleinement Parallèles
Venue: arXiv cs.RO 2007
Year: 2007

This article provides a formalism making it possible to manage the solutions of the direct and inverse kinematic models of the fully parallel manipulators. We introduce the concept of working modes to separate the solutions from the opposite geometrical model. Then, we define, for each working mode, the aspects of these manipulators. To separate the solutions from the direct kinematics model, we introduce the concept of characteristic surfaces. Then, we define the uniqueness domains, as being the greatest domains of the workspace in which there is unicity of solutions. The principal applications of this work are the design, the trajectory planning.
Multiple Antenna Secure Broadcast over Wireless Networks
Venue: arXiv cs.IT 2007
Year: 2007

In wireless data networks, communication is particularly susceptible to eavesdropping due to its broadcast nature. Security and privacy systems have become critical for wireless providers and enterprise networks. This paper considers the problem of secret communication over the Gaussian broadcast channel, where a multi-antenna transmitter sends independent confidential messages to two users with perfect secrecy. That is, each user would like to obtain its own message reliably and confidentially. First, a computable Sato-type outer bound on the secrecy capacity region is provided for a multi-antenna broadcast channel with confidential messages. Next, a dirty-paper secure coding scheme and its simplified version are described. For each case, the corresponding achievable rate region is derived under the perfect secrecy requirement. Finally, two numerical examples demonstrate that the Sato-type outer bound is consistent with the boundary of the simplified dirty-paper coding secrecy rate region.
Artificial Intelligence for Conflict Management
Venue: arXiv cs.AI 2007
Year: 2007

Militarised conflict is one of the risks that have a significant impact on society. Militarised Interstate Dispute (MID) is defined as an outcome of interstate interactions, which result on either peace or conflict. Effective prediction of the possibility of conflict between states is an important decision support tool for policy makers. In a previous research, neural networks (NNs) have been implemented to predict the MID. Support Vector Machines (SVMs) have proven to be very good prediction techniques and are introduced for the prediction of MIDs in this study and compared to neural networks. The results show that SVMs predict MID better than NNs while NNs give more consistent and easy to interpret sensitivity analysis than SVMs.
Rate Adaptation for Cognitive Radio under Interference from Primary Spectrum User
Venue: arXiv cs.IT 2007
Year: 2007

A cognitive radio can operate as a secondary system in a given spectrum. This operation should use limited power in order not to disturb the communication by primary spectrum user. Under such conditions, in this paper we investigate how to maximize the spectral efficiency in the secondary system. A secondary receiver observes a multiple access channel of two users, the secondary and the primary transmitter, respectively. We show that, for spectrally-efficient operation, the secondary system should apply Opportunistic Interference Cancellation (OIC). With OIC, the secondary system decodes the primary signal when such an opportunity is created by the primary rate and the power received from the primary system. For such an operation, we derive the achievable data rate in the secondary system. When the primary signal is decodable, we devise a method, based on superposition coding, by which the secondary system can achieve the maximal possible rate. Finally, we investigate the power allocation in the secondary system when multiple channels are used. We show that the optimal power allocation with OIC can be achieved through intercepted water-filling instead of the conventional water-filling. The results show a significant gain for the rate achieved through an opportunistic interference cancellation.
Design of a 3 Axis Parallel Machine Tool for High Speed Machining: The Orthoglide
Venue: arXiv cs.RO 2007
Year: 2007

The Orthoglide project aims at designing a new 3-axis machine tool for High Speed Machining. Basis kinematics is a 3 degree-of-freedom translational parallel mechanism. This basis was submitted to isotropic and manipulability constraints that allowed the optmization of its kinematic architecture and legs architecture. Thus, several leg morphologies are convenient for the chosen mechanism. We explain the process that led us to the choice we made for the Orthoglide. A static study is presented to show how singular configurations of the legs can cause stiffness problems.