package vpt
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=9bdc6bd62397b4237979a00f802fa81346882a72a4e3ab039979414dc00c8d0d
md5=898aec0cf703c15443f26ca42cde76d0
Description
A vantage point 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.
Bibliography
Yianilos, P. N. (1993, January). Data structures and algorithms for nearest neighbor search in general metric spaces. In Soda (Vol. 93, No. 194, pp. 311-21). http://dx.doi.org/10.1145/313559.313789
Published: 05 Nov 2021
README
vp-tree
A vantage point tree implementation in OCaml.
Cf. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.4193&rep=rep1&type=pdf for details.
A vantage point tree allows to do fast but exact nearest neighbor searches in any space provided that you have a distance function to measure the distance between any two points in that space.
This implementation might need some tweaks in case it is used to index a very large number of points (especially the select_vp function in the code).