1Five Balltree ConstructionAlgorithmsSTEPHEN M. OMOHUNDROInternational Computer Science Institute1947 Center Street, Suite 600Berkeley, California 94704Phone: 415-643-9153Internet: [email protected] 20, 1989Abstract. Balltrees are simple geometric data structures with a widerange of practical applications to geometric learning tasks. In this reportwe compare 5 different algorithms for constructing balltrees from data.We study the trade-off between construction time and the quality of theconstructed tree. Two of the algorithms are on-line, two construct thestructures from the data set in a top down fashion, and one uses a bot-tom up approach. We empirically study the algorithms on random datadrawn from eight different probability distributions representingsmooth, clustered, and curve distributed data in different ambientspace dimensions. We find that the bottom up approach usually produc-es the best trees but has the longest construction time. The other ap-proaches have uses in specific circumstances.2 IntroductionIntroductionMany tasks in robotics, vision, speech, and graphics require the construction and manipu-lation of geometric representations. Systems which build these representations by learningfrom examples can be both flexible and robust. We have developed a data structure whichwe call the balltree which is well suited to geometric learning tasks. Balltrees tune them-selves to the structure of the represented data, support dynamic insertions and deletions,have good average-case efficiency, deal well with high-dimensional entities, and are easyto implement. In this report we compare five different algorithms for building these struc-tures from data. We discuss the trade-off between the efficiency of the construction algo-rithm and the efficiency of the resulting structure. Two of the algorithms are on-line, twoanalyze the data in a top-down fashion, and one analyzes it in a bottom up manner.The balltree structure is related to other hierarchical representations such as k-d trees[Friedman, et. al., 1977] and oct-trees [Samet, 1984], but has specific advantages in the do-mains of interest. We are applying these structures to representing, learning, and manipu-lating point sets, smooth submanifolds, nonlinear mappings, and probability distributions.Some of these applications are described in [Omohundro, 1987, 1988, 1989] in the contextof k-d trees. The operations that are efficiently supported include nearest neighbor retriev-al, intersection and constraint queries, and probability maximization. The basic construc-tion techniques described here should be applicable to a wide variety of other hierarchicalgeometric data structures in which balls are replaced by boxes, cubes, ellipsoids, or sim-plices.BalltreesWe refer to the region bounded by a hyper-sphere in the n-dimensional Euclidean space as a ball. We represent balls by the n+1 floating point values which specify the coordi-nates of its center and the length of its radius. A balltree is a complete binary tree in whicha ball is associated with each node in such a way that an interior node’s ball is the smallestwhich contains the balls of its children. The leaves of the tree hold the information relevantto the application; the interior nodes are used only to guide efficient search through the leafstructures. Unlike the node regions in k-d trees or oct-trees, sibling regions in balltrees areallowed to intersect and need not partition the entire space. These two features are criticalℜnImplementation 3for the applications and give balltrees their representational power. Figure 1 shows an ex-ample of a two-dimensional balltree.In this report we study the problem of building a balltree from given leaf balls. Once thetree structure is specified, the internal balls are determined bottom up from the leaf balls.We would like to choose the tree structure to most efficiently support the queries neededin practical usage. Efficiency will depend both on the distribution of samples and queriesand on the type of retrieval required. We first discuss several important queries and thendescribe a cost function which appears to adequately approximate the costs for practicalapplications. We then compare five different construction algorithms in terms of both thecost of the resulting tree and the construction time. The algorithms are compared on sam-ples drawn from several probability distributions which are meant to be representative ofthose that arise in practice. ImplementationOur implementation is in the object oriented language Eiffel [Meyer, 1989]. There are class-es for balls, balltrees, and balltree nodes. “BALL” objects consist of a vector “ctr” whichholds the center of the ball and a real value “r” containing the radius. “BLT_ND” objectsconsist of a BALL “bl”, and pointers “par, lt,rt” to the node’s parents and children. “BALL-TREE” objects have a pointer “tree” to the underlying tree and a variety other slots to en-hance retrievals (such as local priority queues and caches). All reported times are inseconds on a Sun Sparcstation 1 with 16 Megabytes of memory, running Eiffel Version 2.2from Interactive Software Engineering. Compilation was done with assertion checking offand garbage collection, global class optimization, and C optimization on. As with any ob-ject oriented language, there is some extra overhead associated with dynamic dispatching,but this overhead should affect the different algorithms similarly.A)abcdefa b c d e fABCDEC)B)Figure 1. A) A set of balls in the plane. B) A binary tree over these balls. C) The balls in the resulting balltree. ABCDE4 Queries which use Simple PruningQueries which use Simple PruningThere are two broad classes of query which are efficiently supported by the balltree struc-ture. The first class employs a search with simple pruning of irrelevant branches. The sec-ond class requires the use of branch and bound during search. This section presents somesimple pruning queries and the next gives examples of the more complex variety.Given a query ball, we might require a list of all leaf balls which contain the query ball. Weimplement this as a recursive search down the balltree in which we prune away recursivecalls at internal nodes whose ball does not contain the query ball. If an internal node’s balldoesn’t contain the query ball, it is not possible for any of the leaf balls beneath it to containit either. In the balltree node class “BLT_ND”