[Caml-list] [ANN] first release of minivpt: a minimalist vantage-point tree implementation in OCaml

[Francois BERENGER <francois.c.berenger@vanderbilt.edu>]

Dear list,

A vantage point tree allows to do fast (but exact) nearest neighbor 
searches in a space of any dimension provided that you have a distance 
function (to measure the distance between any two points in that space).

The code is here:
https://github.com/UnixJunkie/vp-tree

The interface looks like this:
---
type 'a t

val create: ('a -> 'a -> float) -> 'a list -> 'a t

val nearest_neighbor: ('a -> 'a -> float) -> 'a -> 'a t -> float * 'a

val to_list: 'a t -> 'a list

val is_empty: 'a t -> bool
---

The creation of a vp-tree can take some time.
Queries are supposed to be fast.
In my tests, queries can run several times faster than a brute
force search once you have enough points indexed by your vpt.

The implementation creates an optimal vp-tree; don't use it
on large points set (> 10,000 points).

You can install it via:
$ opam install minivpt

Contributions are very welcome to support large point sets, queries
with a tolerance parameter (as in "only points within distance to query
less than the tolerance"), and returning all points (instead of just 
one) if there are several points within the same distance to your query 
point.

A usage example might be:
---
let vpt = Vp_tree.create distance_fun points in
let dist_to_query, nearest_point = \
Vp_tree.nearest_neighbor distance_fun query_point vpt in
[...]
---

My implementation follows the paper:
"Data Structures and Algorithms for Nearest Neighbor Search in General 
Metric Spaces" by Peter N. Yianilos.

Regards,
Francois.