Accelerating Evolutionary Construction Tree Extraction via Graph Partitioning
Extracting a Construction Tree from potentially noisy point clouds is an important aspect of Reverse Engineering tasks in Computer Aided Design. Solutions based on algorithmic geometry impose constraints on usable model representations (e.g. quadric surfaces only) and noise robustness. Re-formulating the problem as a combinatorial optimization problem and solving it with an Evolutionary Algorithm can mitigate some of these constraints at the cost of increased computational complexity. This paper proposes a graph-based search space partitioning scheme that is able to accelerate Evolutionary Construction Tree extraction while exploiting parallelization capabilities of modern CPUs. The evaluation indicates a speed-up up to a factor of $46.6$ compared to the baseline approach while resulting tree sizes increased by $25.2\%$ to $88.6\%$.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial Optimizationgraph partitioningSimilar Papers 제목 키워드 기반
PhyloGen: Language Model-Enhanced Phylogenetic Inference via Graph Structure Generation
Phylogenetic trees elucidate evolutionary relationships among species, but phylogenetic inference remains challenging due to the complexity of combining continuous (branch lengths) and discrete parameters (tree topology)…
Language ModelingLanguage ModellingVariational InferenceSDSR: A Spectral Divide-and-Conquer Approach for Species Tree Reconstruction
Recovering a tree that represents the evolutionary history of a group of species is a key task in phylogenetics. Performing this task using sequence data from multiple genetic markers poses two key challenges. The first …
Computing the Bounds of the Number of Reticulations in a Tree-Child Network That Displays a Set of Trees
Phylogenetic network is an evolutionary model that uses a rooted directed acyclic graph (instead of a tree) to model an evolutionary history of species in which reticulate events (e.g., hybrid speciation or horizontal ge…
Distance-based Learning of Hypertrees
We study the problem of learning hypergraphs with shortest-path queries (SP-queries), and present the first provably optimal online algorithm for a broad and natural class of hypertrees that we call orderly hypertrees. O…
Spectral neighbor joining for reconstruction of latent tree models
A common assumption in multiple scientific applications is that the distribution of observed data can be modeled by a latent tree graphical model. An important example is phylogenetics, where the tree models the evolutio…