Five Balltree Construction Algorithms

By S. Omohundro. 2009

530 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Efficient retrieval of recommendations in a matrix factorization framework (2012, methodology): “We use a simple metric tree construction heuristic that tries to approximately pick a pair of pivot points farthest apart from each other [15](2), and splits the data by assigning points to their closest pivot.”
A unified deep artificial neural network approach to partial differential equations in complex geometries (2017, methodology): “9) can be computed efficiently with nearest-neighbor searches, using for example k-d trees [1], or ball trees [29] for very high-dimensional input.”
Speeded-Up Robust Features (SURF) (2008, methodology): “Methods include the best-binfirst proposed by Lowe [24], balltrees [35], vocabulary trees [34], locality sensitive hashing [9], or redundant bit vectors [13].”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, methodology): “Hence, we use a balltree structure [Omohundro, 1989] to implement an eﬃcient approximate GS rule based on the connection to the NNS problem discovered by Dhillon et al. [2011].”
Accelerated Hierarchical Density Based Clustering (2017, background): “trees [28] or cover trees [29] for generic metric spaces, provide”
Parallel search of k-nearest neighbors with synchronous operations (2012, background): “Tree-type data structures are typically associated with regular space partitions [8], [9], [10].”
Generalized Product of Experts for Automatic and Principled Fusion of Gaussian Process Predictions (2014, background): “…individual GP experts: ( SoD ) random subset of data; ( local ) local GP around a randomly selected point; ( tree ) a tree based construction, where a ball tree [5] built on training set recursively partitions the space, and on each level of the tree, a random subset of data is drawn to build a GP.”
Automatic analysis of malware behavior using machine learning (2011, unknown): “By maintaining the prototypes in specialized tree structures, the run-time complexity can be reduced toO(n log k) in the worst-case (Omohundro, 1989; Beygelzimer et al., 2006).”
Finding and Characterizing Information Warfare Campaigns (2020, methodology): “We attempted to use the ball tree algorithm [186], which partitions meme features into a nested set of fixed dimensional hyper-spheres (balls) such that each hyper-sphere contains a set of memes based on its distance from the ball’s center.”
Study on density peaks clustering based on k-nearest neighbors and principal component analysis (2016, methodology): “Some efficient methods such as K-D tree [26] or ball trees [27] can be used to compute the neighbors in O(N logN) time.”
A learning framework for nearest neighbor search (2007, background): “Metric trees [8] and the recently suggested spill trees [3] are based on similar ideas and are related to KD-trees.”
MINT: Multi-Vector Search Index Tuning (2025, unknown): “The single-vector search is known as Nearest Neighbor search and dates back to 1960s [44–46].”