[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] minivpt 2.0.0 in opam Community	2	1148	November 22, 2017
[ANN] first release of bst: a bisector tree implementation Community	2	962	February 14, 2018
[ANN] patricia-tree 0.9.0 - library for patricia tree based maps and sets Community announce	7	605	April 25, 2024
Minisat-ml: a reimplementation of minisat in OCaml Community performance	2	1223	April 10, 2019
[ANN] First release of oma Community announce	5	1133	August 7, 2024

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

Related topics