Metric measure

The fact that a measure is a metric allows optimizations in many applications. For example, many efficient algorithms for searching shortest paths in graphs, such as Dijkstra’s algorithm, make use of the fact that the underlying measure is a metric.

$d: U \times U \rightarrow R^+ \cup \{0\}$ is called metric if the following holds:

$d(x,y) \geq 0$ non-negativity
$d(x,y) = d(y,x)$ symmetry
$x = y \Leftrightarrow d(x,y) = 0$ identity
$d(x,z) \leq d(x,y) + d(y,z)$ triangle inequality

Metric measure sometimes called (mathematical) distance. But not every string measure which is historically called “distance” is a metric, so it’s better to use word metric to avoid confusion.

Minkowski distance

Minkowski distance is an example of metric measure (not typically used as string measure though, given here as an example)

D\left(X,Y\right) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{\frac{1}{p}}

where $X = (x_1,x_2,\ldots,x_n) \text{ and } Y = (y_1,y_2,\ldots,y_n) \in R^n$ . For $p \geq 1$ , the Minkowski distance is a metric.

$p = 1$ Manhattan distance
$p = 2$ Euclidean distance
$p \rightarrow \infty$ Chebyshev distance

Indexing metric spaces

Use two fingers to pan and zoom

from Exploring intersection trees for indexing metric spaces ↗

Data Structure	Space Complexity	Construction Complexity	Claimed Query Complexity	Extra CPU Query Time
BKT	$n$ ptrs	$n \log n$	$n^α$	—
FQT	$n \ldots n \log n$ ptrs	$n \log n$	$n^α$	—
FHQT	$n \ldots nh$ ptrs	$nh$	$\log n^b$	$n^α$
FQA	$nhb$ bits	$nh$	$log n^b$	$n^α \log n$
VPT	$n$ ptrs	$n \log n$	$\log n^c$	—
MVPT	$n$ ptrs	$n \log n$	$\log n^c$	—
VPF	$n$ ptrs	$n^{2−α}$	$n^{1−α} \log n^c$	—
BST	$n$ ptrs	$n\log n$	not analyzed	—
GHT	$n$ ptrs	$n\log n$	not analyzed	—
GNAT	$nm^2$ dsts	$nm \log_m n$	not analyzed	—
VT	$n$ ptrs	$n\log n$	not analyzed	—
MT	$n$ ptrs	$n(m \ldots m^2) \log_m n$	not analyzed	—
SAT	$n$ ptrs	$n \log n / \log \log n$	$n^{1− \Theta(1 / \log \log n)}$	—
AESA	$n^2$ dsts	$n^2$	$O(1)^d$	$n\ldots n^2$
LAESA	$kn$ dsts	$kn$	$k + O(1)^d$	$\log n \ldots kn$
LC	$n$ ptrs	$n^2/m$	not analyzed	$n/m$

from Searching in Metric Spaces ↗

BKT - Burkhard–Keller Tree
FQT - A further development over BKTs is the fixed queries tree
FHQT - fixedheight FQT
FQA - fixed queries array
VPT - vantage-point trees
MVPT - multi-vantage-point tree
VPF - excluded middle vantage point forest
BST - bisector trees
GHT - generalized-hyperplane tree
GNAT - The GHT is extended to an m-ary tree. Geometric near-neighbor access tree
VT - Voronoi tree
MT - M-tree
SAT - spatial approximation tree
AESA - approximating eliminating search algorithm
LAESA - linear AESA
LC - list of clusters

Category	Index	Storage	Distance Domain
Pivot-based tables	AESA, LAESA, EPT, CPT	Main-memory	Continuous
Pivot-based trees	BKT, FQT, FQA	Main-memory	Discrete
	VPT, MVPT	Main-memory	Continuous
Pivot-based external indexes	PM-tree, Omni-family, M-index, SPB-tree	Disk	Continuous

from Pivot-based Metric Indexing ↗

Metric measure

Minkowski distance

Indexing metric spaces

Other