Metric tree

Metric 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 M-tree, vp-trees, 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 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 \mbox{min}_x \leq x \leq \mbox{max}_x and \mbox{min}_y \leq y \leq \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 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 co-founder Sergey Brin of their use for very large databases.[3] The first textbook on metric data structures was published in 2006.[1]


  1. ^ a b Samet, Hanan (2006). Foundations of multidimensional and metric data structures. Morgan Kaufmann. ISBN 978-0-12-369446-1. 
  2. ^ Uhlmann, Jeffrey (1991). "Satisfying General Proximity/Similarity Queries with Metric Trees". Information Processing Letters 40 (4). 
  3. ^ Brin, Sergey (1995). "Near Neighbor Search in Large Metric Spaces". 21st International Conference on Very Large Data Bases (VLDB). 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Metric (band) — Metric James Shaw, Joules Scott Key and Emily Haines, live in 2010 Background information Origin Toronto, Ontario, Canada …   Wikipedia

  • Metric dimension (graph theory) — In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP …   Wikipedia

  • Tree rotation — A tree rotation is an operation on a binary search tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. They are used to change the shape of the tree …   Wikipedia

  • Tree-graded space — A geodesic metric space X is called tree graded with respect to a collection of connected proper subsets (called pieces ) if any two distinct pieces intersect by atmost one point, and every non trivial simple geodesic triangle ofX is contained in …   Wikipedia

  • Cover tree — The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed up of a nearest neighbor search. It is a refinement of the Navigating Net data structure, and related to a variety of other data… …   Wikipedia

  • Real tree — A real tree, or an mathbb R tree, is a metric space ( M , d ) such thatfor any x , y in M there is a unique arc from x to y and this arc is a geodesic segment. Here by an arc from x to y we mean the image in M of a topological embedding f from an …   Wikipedia

  • BK-tree — A BK tree is a metric tree suggested by Burkhard and Keller ref|BK73 specifically adapted to discrete metric spaces.For simplicity, let us consider integer discrete metric varrho(x,y). Then, BK tree is defined in the following way. An arbitrary… …   Wikipedia

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Radix tree — In computer science, a radix tree (also patricia trie or radix trie) is a space optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”