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

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

[Francois BERENGER]

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.

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

[François Bobot]

Le 27/03/2017 à 16:53, Francois BERENGER a écrit :
> 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).


It is very interesting and it is quite generic.

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

Does incremental version of the algorithm exists? Without constructing the optimal vp-tree?


Thank you!

-- 
François

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

[Francois BERENGER]

On 03/28/2017 03:47 AM, François Bobot wrote:
> Le 27/03/2017 à 16:53, Francois BERENGER a écrit :
>> 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).
>
> It is very interesting and it is quite generic.
>>
>> My implementation follows the paper:
>> "Data Structures and Algorithms for Nearest Neighbor Search in General
>> Metric Spaces" by Peter N. Yianilos.
>
> Does incremental version of the algorithm exists?

Maybe but I don't know about them.

Other related data structures (axis-aligned bounding boxes, kd-trees, 
etc.) are described in this book (but unfortunately nothing about vp-trees):

@book{ CompGeomThirdEdSpringer,
    title     = "Computational Geometry: Algorithms and Applications",
    author    = "M. {de Berg} and O. Cheong and M. {van Kreveld} and
    M. Overmars",
    edition   = "Third Edition",
    pages     = {223--224},
    doi       = "10.1007/978-3-540-77974-2",
    year      = "2008",
    publisher = "Springer"
    }

> Without constructing
> the optimal vp-tree?

There is another OCaml version I found on the web a while ago,
which is meant to work on large point sets.

I archived it here:
https://github.com/UnixJunkie/vantage_point_tree_from_codepad

It would be nice to know the author and the license of this code
by the way.

I wasn't fan of the code style and length, so I crafted an 
implementation for my own needs and put it into opam.

Regards,
F.