Algorithm

Materials science

Data structure

Range (aeronautics)

Set (abstract data type)

Computer science

Mathematics

Composite material

Tree (set theory)

Combinatorics

Programming language

Balltrees are simple geometric data structures with a wide range of practical applica­ tions to geometric ·learning tasks. In this report we compare 5 different algorithms for . constructing ball trees from data. We study the trade-off between construction time and the quality of the constructed tree. Two of the algorithms are on-line, two construct the structures from the data set in a top down fashion, and one uses a bottom up approach. We empirically study the algorithms on random data drawn from eight different probability distributions representing smooth, clustered, and curve distributed data in different ambient space dimen­ sions. We find that the bottom up approach usually produces the best trees but has the longest construction time. The other approaches have uses in specific circumstances. 1. IntemauonaI.Computer Science Institute, Berkeley, CA.

Five Balltree Construction Algorithms