 Metric tree

This article is about the data structure. For the type of metric space, see Real tree.
A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle inequality to make accesses to the data more efficient. Examples include the Mtree, vptrees, cover trees, MVP Trees, and bk trees.^{[1]}
Multidimensional search
Most algorithms and data structures for searching a dataset are based on the classical binary search algorithm, and generalizations such as the kd tree or range tree work by interleaving the binary search algorithm over the separate coordinates and treating each spatial coordinate as an independent search constraint. These data structures are wellsuited for range query problems asking for every point (x,y) that satisfies and .
A limitation of these multidimensional search structures is that they are only defined for searching over objects that can be treated as vectors. They aren't applicable for the more general case in which the algorithm is given only a collection of objects and a function for measuring the distance or similarity between two objects. If, for example, someone were to create a function that returns a value indicating how similar one image is to another, a natural algorithmic problem would be to take a dataset of images and find the ones that are similar according to the function to a given query image.
Metric data structures
If there is no structure to the similarity measure then a brute force search requiring the comparison of the query image to every image in the dataset is the best that can be done. If, however, the similarity function satisfies the triangle inequality then it is possible to use the result of each comparison to prune the set of candidates to be examined.
The first article on metric trees, as well as the first use of the term "metric tree", published in the open literature was by Jeffrey Uhlmann in 1991.^{[2]} Other researchers were working independently on similar data structures, and research on metric tree data structures blossomed in the late 1990s and included an examination by Google cofounder Sergey Brin of their use for very large databases.^{[3]} The first textbook on metric data structures was published in 2006.^{[1]}
References
 ^ ^{a} ^{b} Samet, Hanan (2006). Foundations of multidimensional and metric data structures. Morgan Kaufmann. ISBN 9780123694461. http://books.google.dk/books?id=KrQdmLjTSaQC.
 ^ Uhlmann, Jeffrey (1991). "Satisfying General Proximity/Similarity Queries with Metric Trees". Information Processing Letters 40 (4).
 ^ Brin, Sergey (1995). "Near Neighbor Search in Large Metric Spaces". 21st International Conference on Very Large Data Bases (VLDB).
Trees in computer science Binary trees Selfbalancing binary search trees Btrees B+ tree · B*tree · B^{x}tree · UBtree · 23 tree · 234 tree · (a,b)tree · Dancing tree · HtreeTries Binary space partitioning (BSP) trees Nonbinary trees Exponential tree · Fusion tree · Interval tree · PQ tree · Range tree · SPQR tree · Van Emde Boas treeSpatial data partitioning trees Other trees Heap · Hash tree · Finger tree · Metric tree · Cover tree · BKtree · Doublychained tree · iDistance · Linkcut tree · Fenwick treeCategories: Trees (structure)
 Data structure stubs
Wikimedia Foundation. 2010.