Search results for "A* algorithm"
showing 10 items of 2538 documents
Fragtique: Applying an OO Database Distribution Strategy to Data Warehouse
2001
We propose a strategy for distribution of a relational data warehouse organized according to a star schema. We adapt fragmentation and allocation strategies that were developed for OO databases. We split the most-often-accessed dimension table into fragments by using primary horizontal fragmentation. The derived fragmentation then divides the fact table into fragments. Other dimension tables are not fragmented since they are presumed to be sufficiently small. Allocation of fragments encompasses duplication of non-fragmented dimension tables that we call a closure.
Distributed Consensus on Boolean Information
2009
Abstract In this paper we study the convergence towards consensus on information in a distributed system of agents communicating over a network. The particularity of this study is that the information on which the consensus is seeked is not represented by real numbers, rather by logical values or sets. Whereas the problems of allowing a network of agents to reach a consensus on logical functions of input events, and that of agreeing on set–valued information, have been separately addressed in previous work, in this paper we show that these problems can indeed be attacked in a unified way in the framework of Boolean distributed information systems. Based on a notion of contractivity for Bool…
Text Compression Using Antidictionaries
1999
International audience; We give a new text compression scheme based on Forbidden Words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. Our algorithms can also be presented as "compilers" that create compressors dedicated to any previously fixed source. The techniques used in this paper are from Information Theory and Finite Automata.
Asymmetric Comparison and Querying of Biological Networks
2011
Comparing and querying the protein-protein interaction (PPI) networks of different organisms is important to infer knowledge about conservation across species. Known methods that perform these tasks operate symmetrically, i.e., they do not assign a distinct role to the input PPI networks. However, in most cases, the input networks are indeed distinguishable on the basis of how the corresponding organism is biologically well characterized. In this paper a new idea is developed, that is, to exploit differences in the characterization of organisms at hand in order to devise methods for comparing their PPI networks. We use the PPI network (called Master) of the best characterized organism as a …
Communication complexity in a 3-computer model
1996
It is proved that the probabilistic communication complexity of the identity function in a 3-computer model isO(√n).
User Grouping and Power Allocation in NOMA Systems: A Reinforcement Learning-Based Solution
2020
In this paper, we present a pioneering solution to the problem of user grouping and power allocation in Non-Orthogonal Multiple Access (NOMA) systems. There are two fundamentally salient and difficult issues associated with NOMA systems. The first involves the task of grouping users together into the pre-specified time slots. The subsequent second phase augments this with the solution of determining how much power should be allocated to the respective users. We resolve this with the first reported Reinforcement Learning (RL)-based solution, which attempts to solve the partitioning phase of this issue. In particular, we invoke the Object Migration Automata (OMA) and one of its variants to re…
Algorithmics for the Life Sciences
2013
The life sciences, in particular molecular biology and medicine, have wit- nessed fundamental progress since the discovery of the “the Double Helix”. A rele- vant part of such an incredible advancement in knowledge has been possible thanks to synergies with the mathematical sciences, on the one hand, and computer science, on the other. Here we review some of the most relevant aspects of this cooperation focusing on contributions given by the design, analysis and engineering of fast al- gorithms for the life sciences.
Parallel Collision Queries on the GPU
2013
We present parallel algorithms to accelerate collision tests of rigid body objects for a high number of independent transformations as they occur in sampling-based motion planning and path validation problems. We compare various GPU approaches with a different level of parallelism against each other and against a parallel CPU implementation. Our algorithms require no sophisticated load balancing schemes. They make no assumption on the distribution of the input transformations and require no pre-processing. Yet, we can perform up to 1 million collision tests per second with our best GPU implementation in our benchmarks. This is about 2.5X faster than our reference multi-core CPU implementati…
A simple algorithm for drawing large graphs on small screens
1995
Viewing a large graph in limited display space has traditionally been accomplished using either reduced scale rendering of the graph or by attaching scrollbars to a view window which shows only a small portion of the entire graph. Recent work, however, has concentrated on integrating a locally detailed view with a globally scaled view. We present an algorithm for constructing a view which smoothly integrates local detail and global context in a single view window and describe user interaction with such a display.
A grid ant colony algorithm for the orienteering problem
2005
In this paper we propose a distributed ant colony algorithm to solve large scale orienteering problem instances. Our approach is based on a multi-colony strategy where each colony works in an independent portion (cluster) in the original graph. This results in no need for communicating pheromones information among colonies and in increasing speedup. We have implemented our algorithm as a .NET Web services infrastructure following a grid computing philosophy and we provide some promising experimental results to show the feasibility and effectiveness of our approach