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

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

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.