VpTree
Defined in: packages/data/src/similarity/vp-tree.ts:58
A vantage-point tree: nearest-neighbour search over an arbitrary metric space.
Unlike a k-d tree it needs no coordinates — only a distance function — so it
indexes edit distance over strings, cosine distance over embeddings, or any
other metric, at any dimensionality. That generality is why this is the only
generic spatial structure in the repository; @ac-kit/math-geometry’s
KdTree2/KdTree3 stay fixed-dimension and Euclidean.
Each node splits its items by their distance from a chosen vantage point, inside or outside the median radius. A query then prunes whichever half the triangle inequality proves cannot hold anything closer than what is already found.
Time complexity: O(n log n) to build. Queries are O(log n) for well-behaved metrics and degrade toward O(n) as the intrinsic dimensionality rises — the curse of dimensionality is real here, and on high-dimensional data a linear scan can win.
Adding is deferred. A VP tree is built from a known point set; inserting
incrementally would unbalance it. add buffers, and the next query rebuilds
the whole tree in O(n log n). Add in batches, then query.
Type Parameters
Section titled “Type Parameters”T
The item type.
Implements
Section titled “Implements”Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new VpTree<
T>(iterable,options):VpTree<T>
Defined in: packages/data/src/similarity/vp-tree.ts:65
Parameters
Section titled “Parameters”iterable
Section titled “iterable”Iterable<T, any, any> | undefined
options
Section titled “options”Returns
Section titled “Returns”VpTree<T>
Methods
Section titled “Methods”add(
item):void
Defined in: packages/data/src/similarity/vp-tree.ts:84
O(1); the tree is rebuilt on the next query.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”addAll()
Section titled “addAll()”addAll(
items):void
Defined in: packages/data/src/similarity/vp-tree.ts:90
O(m); the tree is rebuilt once, on the next query.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/similarity/vp-tree.ts:77
Returns
Section titled “Returns”void
count()
Section titled “count()”count():
number
Defined in: packages/data/src/similarity/vp-tree.ts:73
Returns
Section titled “Returns”number
nearest()
Section titled “nearest()”nearest(
query,count):IterableIterator<Candidate<T>>
Defined in: packages/data/src/similarity/vp-tree.ts:104
The count items closest to query, nearest first.
Fewer than count are yielded when the tree holds fewer. Ties are broken
arbitrarily but deterministically for a given tree.
Parameters
Section titled “Parameters”T
number
Returns
Section titled “Returns”IterableIterator<Candidate<T>>
Implementation of
Section titled “Implementation of”within()
Section titled “within()”within(
query,maxDistance):IterableIterator<Candidate<T>>
Defined in: packages/data/src/similarity/vp-tree.ts:135
Every item within maxDistance of query, in no particular order.
Parameters
Section titled “Parameters”T
maxDistance
Section titled “maxDistance”number
Returns
Section titled “Returns”IterableIterator<Candidate<T>>