Hello,

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

It also allows proximity queries, as in "all points within distance d
from my query point".

Cf. this article for details: "A Data Structure and an Algorithm for the
Nearest Point Problem"; Iraj Kalaranti and Gerard McDonald.
ieeexplore.ieee.org/iel5/32/35936/01703102.pdf

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

It might interest users of vantage point trees (minivpt, and vpt in
opam), kd-trees and such.
I think bst should be faster than vpt in most use cases.

It should appear in opam shortly.

Regards,
Francois.


--
Caml-list mailing list.  Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs