tag then put in opam

just increment z in x.y.z

Looks like this is the last package I'm using that still uses jbuilder:

% opam uninstall jbuilder 
The following actions will be performed:
  ⊘ remove vpt      4.0.1        [uses jbuilder]
  ⊘ remove jbuilder 1.0+beta20.2

c'est un peu abuse de ne filer qu'un .mli sans commentaires.

Very nice work !

However, VP trees are really useful for mining huge collection of data.
From a quick look at your implementation, I found two issues. One is minor, the second one is more complex.

The minor one is about to_list : it has at least quadratic complexity, since each right sub-tree is traversed twice, on during to_list and once during List.rev_append ; you must use a right-to-left traversal with an accumulator instead, and add each individual vp node with a O(1) cons on it.
Although, since VP tree are expected to be huge, a to-list function is not really useful.

The second issue is that you assume all the data is initially available into one single list, hence it must entirely fit into the memory. Of course, having initially a small list of representative points is useful for building good vantage points using their statistical distribution. But we might want to make that database huge later on.

A more interesting implementation would be to have an abstract layer to access and build the VP tree lazily, hence making us able to back it on disk and only caching some nodes into memory. If you look carefully at the algorithms provided in the reference paper, only a very thin slice of the VP tree is actually required to be loaded into memory when looking for some specific points. That's where VP tree are really amazing.

Although, you shall add a function to insert a new point in the VP tree.

That kind of gnuplot would be cool:
https://fribbels.github.io/vptree/Images/full.png

then do new major release in opam

instead of regular distance bounds.
Probably due to points very nearby in the tree.

by storing them in the same node in a list

will need remove

not only nearest neighbor queries are useful.

this is a new major version since the interface was changed

brute force is faster than vp-tree search for small N, hence we should have leaves storing N nodes
instead of just 1.