package vpt

  1. Overview
  2. Docs

Module Vp_tree.MakeSource

Parameters

module P : Point

Signature

Sourcetype t

A vantage point tree.

Sourcetype quality =
  1. | Optimal
  2. | Good of int
  3. | 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.

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

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

Sourceval 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. If you are not happy with that, use a point type that is deduplicated (i.e. a point that holds the info for all points with the same coordinates).

Sourceval 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.

Sourceval to_list : t -> P.t list

to_list vpt return the list of points in vpt.

Sourceval is_empty : t -> bool

is_empty vpt test if vpt is empty.

Sourceval 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. Warning: there may be several points at this distance from p in vpt, but a single (arbitrary) one is returned.

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

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

Sourceval root : t -> P.t

root tree return the root point of the tree.

  • raises [Not_found]

    if tree is empty.

Sourceval check : t -> bool

check tree test the tree invariant. Should always be true. If invariant doesn't hold, then this library has a bug (or your distance function is not a proper metric).

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

remove quality query tree return an updated tree where the first element with distance = 0.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).