[ANN] first release of bst: a bisector tree implementation

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:

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.

6 Likes

I can recall a few occasions when I would have really liked to have a datastructure like that.

Just curious, does anyone have a pdf for the paper linked? It’s annoying that a paper written in the 80s is still behind a paywall.

If you have an e-mail, someone would be able to send you the paper.