Metric tree

Most algorithms and data structures for searching a dataset are based on the classical binary search algorithm, and generalizations such as the k-d 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 well-suited for range query problems asking for every point $(x,y)$ that satisfies $\backslash mbox\{min\}\_x\; \backslash leq\; x\; \backslash leq\; \backslash mbox\{max\}\_x$ and $\backslash mbox\{min\}\_y\; \backslash leq\; y\; \backslash leq\; \backslash mbox\{max\}\_y$.

A limitation of these multidimensional search structures is that they are only defined for searching over objects that can be treated as vectors. They are not 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.

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 {{Citation needed|date=May 2015}}. 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.{{cite journal |last=Uhlmann |first=Jeffrey |title=Satisfying General Proximity/Similarity Queries with Metric Trees |journal=Information Processing Letters |volume=40 |number=4 |year=1991|pages=175–179 |doi=10.1016/0020-0190(91)90074-r }} Other researchers were working independently on similar data structures. In particular, Peter Yianilos claimed to have independently discovered the same method, which he called a vantage point tree (VP-tree).{{cite conference

|first=Peter N.

|last=Yianilos

|title=Data structures and algorithms for nearest neighbor search in general metric spaces

|book-title=Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms

|pages=311–321

|publisher=Society for Industrial and Applied Mathematics Philadelphia, PA, USA

|year=1993

|url=http://pnylab.com/papers/vptree/main.html

|access-date=2019-03-07

|id=pny93

}}

The research on metric tree data structures blossomed in the late 1990s and included an examination by Google co-founder Sergey Brin of their use for very large databases.{{cite conference |last=Brin |first=Sergey |title=Near Neighbor Search in Large Metric Spaces |book-title=21st International Conference on Very Large Data Bases (VLDB) |year=1995 |url=http://www.vldb.org/conf/1995/P574.PDF}} The first textbook on metric data structures was published in 2006.

• Matlab: Metric trees are implemented in the metricTree class that is part of the United States Naval Research Laboratory's free Tracker Component Library.{{cite web |title=Tracker Component Library | work=Matlab Repository| access-date=January 5, 2019|url=https://github.com/USNavalResearchLaboratory/TrackerComponentLibrary }}

{{Reflist}}

{{CS-Trees}}

Category:Trees (data structures)