vpt is the replacement of minivpt in opam.
The code is there:
The new interface is:
This file has been truncated.
(** Functorial interface. *)
module type Point =
(** A point. *)
(** [dist] should be a distance function: symmetric, zero and
the diagonal and verifying the triangular inequality.
Be _very_ careful with the implementation of your metric
(dist x x = 0.0, NaN is not a proper distance, etc). *)
val dist: t -> t -> float
module Make: functor (P: Point) ->
(** A vantage point tree. *)
There are more functionalities than before (all neighbors within distance d from query point, find, mem, root and remove) and it is no more a minimalist implementation.
It also works for large number of points now if you construct a random vpt, unlike before.
This is an awesome data structure
I can trigger a bug though.
With 300k points from the real world, some NaNs can appear in the data structure.
I am investigating …
also, I should use buckets of points; once there are too few points left, put them all in the same bucket instead of constructing sub trees. This will save storage space, time when constructing the tree and maybe even accelerate queries (starting at some small N, brute force search is faster than vpt search).