Study notes for Metric Trees

最编程 2024-07-25 07:04:37

...

A metric tree is any tree data structure specialized to index data in metric spaces. Formally, a metric tree

is a metric space such that between any two of its points there is an unique arc that is isometric to an interval in

, and (to ensure the uniqueness)

, where

Metric trees exploit properties of metric spaces such as the triangle inequality to make accesses to the data more efficiently.

Essentially, metric trees are designed to resolve the problem of "similarity indexing", in order to access or query similar objects much faster.

Examples:

M-tree, vp-trees, cover trees, MVP Trees, and bk trees.
(The Radial Metric, Spider Tree) Define by

We can observe that is in fact a metric and that is a metric tree.

Metric trees are useful in the case where

there are a collection of objects and a function for measuring the distance or similarity between two objects.
the objects cannot be represented by vectors of feature values; otherwise multi-dimensional (spatial) search methods such as k-d tree or range tree should be used. Beside, spatial search methods use an Lp distance functions, which means there is no correlation between features.
the similarity measure or function should satisfy the triangle inequality such that it is possible to use the result of each comparison to prune the set of candidates to be examined.

In principle, there are two basic types of similarity queries:

range: given a query object q, and a maximum searching distance r, it selects all indexed objects o, such that d(q, o)<=r.
k nearest neighbors (k-NN): given a query object q, and an integer k>=1, it selects the k indexed objects which have the shortest distance d(q, o).

[Hadoop Big Data Technologies] - ZooKeeper Distributed Orchestration Service (Study Notes) - 🕒 3.ZooKeeper 的观察者机制