From: Francois BERENGER <berenger@bioreg.kyushu-u.ac.jp>
To: caml-list@inria.fr
Subject: [Caml-list] [ANN] first release of bst: a bisector tree implementation
Date: Wed, 7 Feb 2018 11:00:34 +0900 [thread overview]
Message-ID: <51b207da-d84e-dec9-7953-7d776361d756@bioreg.kyushu-u.ac.jp> (raw)
In-Reply-To: <a521c84c-7189-4b62-f217-fa9c0c7f001a@bioreg.kyushu-u.ac.jp>
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.
next prev parent reply other threads:[~2018-02-07 2:00 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-01-23 14:54 [Caml-list] Are record types generative? Oleg
2018-01-23 16:05 ` Jeremy Yallop
2018-01-23 17:39 ` Chet Murthy
2018-01-23 20:35 ` Jeremy Yallop
2018-01-23 21:36 ` Chet Murthy
2018-01-23 22:06 ` Jeremy Yallop
2018-01-23 23:14 ` Hendrik Boom
2018-01-24 1:06 ` Chet Murthy
2018-01-24 1:35 ` Francois BERENGER
2018-02-07 2:00 ` Francois BERENGER [this message]
2018-02-07 12:40 ` [Caml-list] [ANN] first release of bst: a bisector tree implementation Ivan Gotovchits
2018-02-08 0:46 ` Francois BERENGER
2018-01-24 1:56 ` [Caml-list] Are record types generative? Yawar Amin
2018-01-25 10:49 ` Matej Košík
2018-01-25 13:39 ` Simon Cruanes
2018-01-25 16:24 ` Yawar Amin
2018-01-24 1:05 ` Chet Murthy
2018-01-24 8:43 ` Jacques Garrigue
2018-02-02 23:07 ` Toby Kelsey
2018-02-02 23:23 ` Evgeny Roubinchtein
2018-02-04 1:27 ` Jacques Garrigue
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=51b207da-d84e-dec9-7953-7d776361d756@bioreg.kyushu-u.ac.jp \
--to=berenger@bioreg.kyushu-u.ac.jp \
--cc=caml-list@inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).