Metric tree

Source: Wikipedia, the free encyclopedia.
This article is about the data structure. For the type of metric space, see Real tree.

A metric tree is any

MVP trees, and BK-trees.[1]

Multidimensional search

Most algorithms and data structures for searching a dataset are based on the classical

range query
problems asking for every point 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

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]. 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. In particular, Peter Yianilos claimed to have independently discovered the same method, which he called a vantage point tree (VP-tree).[3] 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.[4] The first textbook on metric data structures was published in 2006.[1]

Open source implementations

References

  1. ^
    ISBN 978-0-12-369446-1
    .
  2. doi:10.1016/0020-0190(91)90074-r
    .
  3. ^ Yianilos, Peter N. (1993). "Data structures and algorithms for nearest neighbor search in general metric spaces". Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 311–321. pny93. Retrieved 2019-03-07.
  4. ^ Brin, Sergey (1995). "Near Neighbor Search in Large Metric Spaces" (PDF). 21st International Conference on Very Large Data Bases (VLDB).
  5. ^ "Tracker Component Library". Matlab Repository. Retrieved January 5, 2019.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Metric_tree&oldid=1133737686"