A balanced tree for similarity search in generic metric spaces (any distance satisfying the triangle inequality), not just Euclidean. Stores routing objects with covering radii so the triangle inequality can prune subtrees during search.
Key formulas
Triangle inequality: d(x,z)≤d(x,y)+d(y,z)
Pruning rule: skip subtree at routing object r with radius ρ if d(q,r)>ε+ρ for ε-range query.
Range / kNN query: O(logn) in low intrinsic dimension.