[ANN] new release of vpt (a Vantage-point tree library)

UnixJunkie · January 15, 2018, 7:59am

vpt is the replacement of minivpt in opam.

The code is there:

The new interface is:

UnixJunkie/vp-tree/blob/master/vp_tree.mli


(** Functorial interface. *)

module type Point =
sig
  (** A point. *)
  type t

  (** [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
end

module Make: functor (P: Point) ->
sig
  (** A vantage point tree. *)
  type t

This file has been truncated. show original

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.

Regards,
F.

igarnier · January 15, 2018, 8:08am

This is an awesome data structure Thanks @UnixJunkie!

UnixJunkie · January 15, 2018, 9:58am

I can trigger a bug though.
With 300k points from the real world, some NaNs can appear in the data structure.
I am investigating …

UnixJunkie · January 15, 2018, 10:06am

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).

Topic		Replies	Views
[ANN] first release of bst: a bisector tree implementation Community	2	914	February 14, 2018
Minisat-ml: a reimplementation of minisat in OCaml Community performance	2	1159	April 10, 2019
[ANN] LLVM 15 is out! Community	9	1655	September 17, 2023
[ANN] rtree 0.1.0 Community	6	624	August 9, 2023
[ANN] varray 0.2 Ecosystem announce	1	520	November 25, 2023

[ANN] new release of vpt (a Vantage-point tree library)

Related Topics