Search results for "Tree"
showing 10 items of 1841 documents
A SOM/ARSOM Hierarchy for the Description of Dynamic Scenes
2001
A neural architecture is presented, aimed to describe the dynamic evolution of complex structures inside a video sequence. The proposed system is arranged as a tree of self-organizing maps. Leaf nodes are implemented by ARSOM networks as a way to code dynamic inputs, while classical SOM's are used to implement the upper levels of the hierarchy. Depending on the application domain, inputs are made by suitable low level features extracted frame by frame of the sequence. Theoretical foundations of the architecture are reported along with a detailed outline of its structure, and encouraging experimental results.
Boosting Textual Compression in Optimal Linear Time
2005
We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn any memoryless compressor into a compression algorithm that uses the “best possible” contexts; (b) it is very simple and optimal in terms of time; and (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.Technically, our boosting technique builds upon three main ingredients: the Burrows--Wheeler Transform, the Suffix Tree d…
Non-interleaved Quadtree Node Codification
2004
The usual quadtree node non-pointer codification is based on interleaved binary representations of node coordinates, in such a way that every operation that concerns to the spatial position or to the specific orientation of the region represented by the node needs to undo this interleaving process. So, the computation time of such operations is linear with the node depth. In this paper an alternative codification is presented called “non-interleaved codification”. The new codification has a simpler management and a higher intuitiveness than current codifications that use the interleaving approach. The proposed codification is more efficient than previous ones for the following set of operat…
Random Tanglegram Partitions (Random TaPas): An Alexandrian Approach to the Cophylogenetic Gordian Knot
2018
Abstract Symbiosis is a key driver of evolutionary novelty and ecological diversity, but our understanding of how macroevolutionary processes originate extant symbiotic associations is still very incomplete. Cophylogenetic tools are used to assess the congruence between the phylogenies of two groups of organisms related by extant associations. If phylogenetic congruence is higher than expected by chance, we conclude that there is cophylogenetic signal in the system under study. However, how to quantify cophylogenetic signal is still an open issue. We present a novel approach, Random Tanglegram Partitions (Random TaPas) that applies a given global-fit method to random partial tanglegrams of …
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).
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.
Challenges of Program Synthesis with Grammatical Evolution
2020
Program synthesis is an emerging research topic in the field of EC with the potential to improve real-world software development. Grammar-guided approaches like GE are suitable for program synthesis as they can express common programming languages with their required properties. This work uses common software metrics (lines of code, McCabe metric, size and depth of the abstract syntax tree) for an analysis of GE’s search behavior and the resulting problem structure. We find that GE is not able to solve program synthesis problems, where correct solutions have higher values of the McCabe metric (which means they require conditions or loops). Since small mutations of high-quality solutions str…
High Locality Representations for Automated Programming
2011
We study the locality of the genotype-phenotype mapping used in grammatical evolution (GE). GE is a variant of genetic programming that can evolve complete programs in an arbitrary language using a variable-length binary string. In contrast to standard GP, which applies search operators directly to phenotypes, GE uses an additional mapping and applies search operators to binary genotypes. Therefore, there is a large semantic gap between genotypes (binary strings) and phenotypes (programs or expressions). The case study shows that the mapping used in GE has low locality leading to low performance of standard mutation operators. The study at hand is an example of how basic design principles o…
Optimal Resource Discovery Paths of Gnutella2
2008
This paper shows that the performance of peer-to-peer resource discovery algorithms is upper bounded by a k-Steiner minimum tree and proposes an algorithm locating near-optimal query paths for the peer-to-peer resource discovery problem. Global knowledge of the topology and the resources from the peer-to-peer network are required as an input to the algorithm. The algorithm provides an objective measure for defining how good local search algorithms are. The performance is evaluated in simulated peer-to-peer scenarios and in the measured Gnutella2 P2P network topology with four local search algorithms: breadth-first search, self-avoiding random walker, highest degree search and Dynamic Query …
Filling the Eastern European gap in millennium-long temperature reconstructions
2013
Tree ring–based temperature reconstructions form the scientific backbone of the current global change debate. Although some European records extend into medieval times, high-resolution, long-term, regional-scale paleoclimatic evidence is missing for the eastern part of the continent. Here we compile 545 samples of living trees and historical timbers from the greater Tatra region to reconstruct interannual to centennial-long variations in Eastern European May–June temperature back to 1040 AD. Recent anthropogenic warming exceeds the range of past natural climate variability. Increased plague outbreaks and political conflicts, as well as decreased settlement activities, coincided with tempera…