The vp-trees Reference Manual

Table of Contents

The vp-trees Reference Manual

This is the vp-trees Reference Manual, version 0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Thu Mar 11 15:15:52 2021 GMT+0.

1 Introduction

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.

2.1 vp-trees

Author

Vasily Postnicov <shamaz.mazum@gmail.com>

License

2-clause BSD

Description

Perceptual hash algorithms for images

Version

0.1

Source

vp-trees.asd (file)

Components

• src/package.lisp (file)
• src/vp-trees.lisp (file)

3 Files

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

3.1 Lisp

3.1.1 vp-trees.asd

Location

vp-trees.asd

Systems

vp-trees (system)

3.1.2 vp-trees/src/package.lisp

Parent

vp-trees (system)

Location

src/package.lisp

Packages

vp-trees

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

Dependency

src/package.lisp (file)

Parent

vp-trees (system)

Location

src/vp-trees.lisp

Exported Definitions

• make-vp-tree (function)
• search-close (function)
• vp-node (structure)

Internal Definitions

• copy-vp-node (function)
• divide-list (function)
• make-vp-node (function)
• median (function)
• pick-random (function)
• vp-node-center (function)
• (setf vp-node-center) (function)
• vp-node-inner (function)
• (setf vp-node-inner) (function)
• vp-node-leaf-p (function)
• vp-node-outer (function)
• (setf vp-node-outer) (function)
• vp-node-p (function)
• vp-node-radius (function)
• (setf vp-node-radius) (function)

4 Packages

Packages are listed by definition order.

4.1 vp-trees

Source

src/package.lisp (file)

Use List

common-lisp

Exported Definitions

• make-vp-tree (function)
• search-close (function)
• vp-node (structure)

Internal Definitions

• copy-vp-node (function)
• divide-list (function)
• make-vp-node (function)
• median (function)
• pick-random (function)
• vp-node-center (function)
• (setf vp-node-center) (function)
• vp-node-inner (function)
• (setf vp-node-inner) (function)
• vp-node-leaf-p (function)
• vp-node-outer (function)
• (setf vp-node-outer) (function)
• vp-node-p (function)
• vp-node-radius (function)
• (setf vp-node-radius) (function)

5 Definitions

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

5.1 Exported definitions

5.1.1 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

vp-trees

Source

src/vp-trees.lisp (file)

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

vp-trees

Source

src/vp-trees.lisp (file)

5.1.2 Structures

Structure: vp-node ()

Package

vp-trees

Source

src/vp-trees.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots

Slot: center

Readers

vp-node-center (function)

Writers

(setf vp-node-center) (function)

Slot: radius

Type

number

Initform

0

Readers

vp-node-radius (function)

Writers

(setf vp-node-radius) (function)

Slot: inner

Type

(or null vp-trees:vp-node)

Readers

vp-node-inner (function)

Writers

(setf vp-node-inner) (function)

Slot: outer

Type

(or null vp-trees:vp-node)

Readers

vp-node-outer (function)

Writers

(setf vp-node-outer) (function)

5.2 Internal definitions

5.2.1 Functions

Function: copy-vp-node INSTANCE

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: divide-list LIST PREDICATE

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

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: make-vp-node &key (CENTER CENTER) (RADIUS RADIUS) (INNER INNER) (OUTER OUTER)

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: median LIST &optional NLEFT NRIGHT KEY

Return median value for a list

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: pick-random LIST

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

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: vp-node-center INSTANCE

Function: (setf vp-node-center) VALUE INSTANCE

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: vp-node-inner INSTANCE

Function: (setf vp-node-inner) VALUE INSTANCE

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: vp-node-leaf-p NODE

True if this node is a leaf

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: vp-node-outer INSTANCE

Function: (setf vp-node-outer) VALUE INSTANCE

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: vp-node-p OBJECT

Package

vp-trees

Source

src/vp-trees.lisp (file)

Function: vp-node-radius INSTANCE

Function: (setf vp-node-radius) VALUE INSTANCE

Package

vp-trees

Source

src/vp-trees.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types