package vpt

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Parameters
Signature

package vpt

vpt
- Vpt
  - Vp_tree
    
    Make
    
    P
    
    Point

Legend:
Library
Module
Module type
Parameter
Class
Class type

Parameters

module P : Point

Signature

type t

A vantage point tree.

type quality =

| Optimal
| Good of int
| Random

Quality of the constructed tree. Tree construction takes more time with higher quality. Tree query time takes less time with higher tree quality. If you have 100k or more points, use a Good or Random tree.

val create : quality -> P.t list -> t

create quality points create a vantage point tree of given quality containing all points.

val nearest_neighbor : P.t -> t -> float * P.t

nearest_neighbor p vpt return the distance along with the nearest neighbor to query point p in vpt. Warning: there may be several points at this distance from p in vpt, but a single (arbitrary) one is returned.

val neighbors : P.t -> float -> t -> P.t list

neighbors p tol vpt return all points in vpt within tol distance from query point p. I.e. all points returned are within (d <= tol) distance from p.

val to_list : t -> P.t list

to_list vpt return the list of points in vpt.

val is_empty : t -> bool

is_empty vpt test if vpt is empty.

val find : P.t -> t -> P.t

find query tree return the first point with distance to query = 0.0.

raises [Not_found]
if no such element exists.

val mem : P.t -> t -> bool

mem query tree return true if query can be found in tree; false otherwise.

val root : t -> P.t

root tree return the root point of the tree.

raises [Not_found]
if tree is empty.

val check : t -> bool

check tree test the tree invariant. Should always be true. If invariant doesn't hold, then this library has a bug.

val remove : quality -> P.t -> t -> t

remove quality query tree return an updated tree where the first element with distance = 0 to query was removed. The sub-tree that is reconstructed upon removal of query uses the specified quality.

raises [Not_found]
if not (mem query tree).