Ball tree

This article is about the binary tree variant. For a metric-tree involving multi-way splits, see M-tree.

In computer science, a ball tree, balltree[1] or metric tree, is a space partitioning data structure for organizing points in a multi-dimensional space. A ball tree partitions data points into a nested set of balls. The resulting data structure has characteristics that make it useful for a number of applications, most notably nearest neighbor search.

  1. ^ Cite error: The named reference r1 was invoked but never defined (see the help page).