# The vp-trees Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

# The vp-trees Reference Manual

This is the vp-trees Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 06:30:57 2022 GMT+0.

# vp-trees  vp-trees is an implementation of vantage point tree data structure in Common Lisp. It allows to perform fast (O(log N) in the best case) fixed-radius near neighbors searches in some set of a metric space.

Look at the following example. Let's choose the space ℝ²[0, 1] and generate some points belonging to this space:

``````(defun gen-point ()
(vector (random 1.0)
(random 1.0)))

(defun gen-points (n)
(loop repeat n collect (gen-point)))
``````

Then introduce a metric on this space (usual Euclidean metric):

``````(defun dist (a b)
(sqrt
(reduce #'+
(map 'vector (lambda (x y) (expt (- x y) 2))
a b))))
``````

Build a tree consisting of 1000000 elements in ℝ²[0, 1]:

``````(defparameter *tree*
(vp-trees:make-vp-tree (gen-points 1000000) #'dist))
``````

Now return points which are closer than 0.1 to the origin:

``````(vp-trees:search-close *tree* #(0.0 0.0) 0.1 #'dist)
``````

The advantage of VP trees is that you don't have to stick to Euclidean metric: you may choose whatever metric you want as long as four metric axioms hold. For example, VP trees can be used for multidimensional sp

## 2 Systems

The main system appears first, followed by any subsystem dependency.

Previous: , Up: Systems   [Contents][Index]

### 2.1 vp-trees

Perceptual hash algorithms for images

Author

Vasily Postnicov <shamaz.mazum@gmail.com>

2-clause BSD

Version

0.1

Source
Child Components

## 3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

Previous: , Up: Files   [Contents][Index]

### 3.1 Lisp

Next: , Previous: , Up: Lisp   [Contents][Index]

#### 3.1.1 vp-trees/vp-trees.asd

Source
Parent Component

vp-trees (system).

ASDF Systems

#### 3.1.2 vp-trees/src/package.lisp

Source
Parent Component

vp-trees (system).

Packages

#### 3.1.3 vp-trees/src/vp-trees.lisp

Dependency

src/package.lisp (file).

Source
Parent Component

vp-trees (system).

Public Interface
Internals

## 4 Packages

Packages are listed by definition order.

Previous: , Up: Packages   [Contents][Index]

Source
Use List

common-lisp.

Public Interface
Internals

## 5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

Next: , Previous: , Up: Definitions   [Contents][Index]

### 5.1 Public Interface

#### 5.1.1 Ordinary functions

Function: make-vp-tree (list distance &key key)

Make vantage point tree from a set @c(list) using a distance function @c(distance). Optional @c(key) function can be specified as a mapping between elements in @c(list) and elements in your metric space, so @c(ρ(x,y) = distance (key(x), key(y))) where x and y are in the @c(list).

Package
Source
Function: search-close (tree item threshold distance &key key)

Find all items in the tree @c(tree) closer to @c(item) than @c(threshold). @c(item) and elements of the tree must belong to a metric space with @c(distance) as a metric function. Optional @c(key) function can be used to calculate a distance between two objects in the following way: @c(ρ(x,y) = distance (key(x), key(y))).

Package
Source

#### 5.1.2 Standalone methods

Method: print-object ((object vp-node) stream)
Source

#### 5.1.3 Structures

Structure: vp-node
Package
Source
Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: center
Writers
Type

number

Initform

0

Writers
Slot: inner
Type

(or null vp-trees:vp-node)

Writers
Slot: outer
Type

(or null vp-trees:vp-node)

Writers

### 5.2 Internals

Previous: , Up: Internals   [Contents][Index]

#### 5.2.1 Ordinary functions

Function: copy-vp-node (instance)
Package
Source
Function: divide-list (list predicate)

Divide a set in two halves depending on the value of predicate function

Package
Source
Function: make-vp-node (&key center radius inner outer)
Package
Source
Function: median (list &optional nleft nright key)

Return median value for a list

Package
Source
Function: pick-random (list)

Pick a random value from a list and return this value and a new list with this value removed.

Package
Source
Writer: (setf vp-node-center) (instance)
Package
Source
Target Slot
Writer: (setf vp-node-inner) (instance)
Package
Source
Target Slot
Function: vp-node-leaf-p (node)

True if this node is a leaf

Package
Source
Writer: (setf vp-node-outer) (instance)
Package
Source
Target Slot
Function: vp-node-p (object)
Package
Source
Writer: (setf vp-node-radius) (instance)
Package
Source
Target Slot

## Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.1 Concepts

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.3 Variables

Jump to: C   I   O   R   S
Jump to: C   I   O   R   S

Previous: , Up: Indexes   [Contents][Index]