Next: Introduction, Previous: (dir), 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.
Table of Contents
Next: Systems, Previous: The vp-trees Reference Manual, Up: The vp-trees Reference Manual [Contents][Index]
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
Next: Files, Previous: Introduction, Up: The vp-trees Reference Manual [Contents][Index]
2 Systems
The main system appears first, followed by any subsystem dependency.
2.1 vp-trees
Perceptual hash algorithms for images
- Author
Vasily Postnicov <shamaz.mazum@gmail.com>
- License
2-clause BSD
- Version
0.1
- Source
- Child Components
- src/package.lisp (file).
- src/vp-trees.lisp (file).
Next: Packages, Previous: Systems, Up: The vp-trees Reference Manual [Contents][Index]
3 Files
Files are sorted by type and then listed depth-first from the systems components trees.
3.1 Lisp
Next: vp-trees/src/package.lisp, Previous: Lisp, Up: Lisp [Contents][Index]
3.1.1 vp-trees/vp-trees.asd
- Source
- Parent Component
vp-trees (system).
- ASDF Systems
Next: vp-trees/src/vp-trees.lisp, Previous: vp-trees/vp-trees.asd, Up: Lisp [Contents][Index]
3.1.2 vp-trees/src/package.lisp
- Source
- Parent Component
vp-trees (system).
- Packages
Previous: vp-trees/src/package.lisp, Up: Lisp [Contents][Index]
3.1.3 vp-trees/src/vp-trees.lisp
- Dependency
src/package.lisp (file).
- Source
- Parent Component
vp-trees (system).
- Public Interface
- make-vp-tree (function).
- print-object (method).
- search-close (function).
- vp-node (structure).
- Internals
- copy-vp-node (function).
- divide-list (function).
- make-vp-node (function).
- median (function).
- pick-random (function).
- vp-node-center (reader).
- (setf vp-node-center) (writer).
- vp-node-inner (reader).
- (setf vp-node-inner) (writer).
- vp-node-leaf-p (function).
- vp-node-outer (reader).
- (setf vp-node-outer) (writer).
- vp-node-p (function).
- vp-node-radius (reader).
- (setf vp-node-radius) (writer).
Next: Definitions, Previous: Files, Up: The vp-trees Reference Manual [Contents][Index]
4 Packages
Packages are listed by definition order.
4.1 vp-trees
- Source
- Use List
common-lisp.
- Public Interface
- make-vp-tree (function).
- search-close (function).
- vp-node (structure).
- Internals
- copy-vp-node (function).
- divide-list (function).
- make-vp-node (function).
- median (function).
- pick-random (function).
- vp-node-center (reader).
- (setf vp-node-center) (writer).
- vp-node-inner (reader).
- (setf vp-node-inner) (writer).
- vp-node-leaf-p (function).
- vp-node-outer (reader).
- (setf vp-node-outer) (writer).
- vp-node-p (function).
- vp-node-radius (reader).
- (setf vp-node-radius) (writer).
Next: Indexes, Previous: Packages, Up: The vp-trees Reference Manual [Contents][Index]
5 Definitions
Definitions are sorted by export status, category, package, and then by lexicographic order.
Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]
5.1 Public Interface
Next: Standalone methods, Previous: Public Interface, Up: Public Interface [Contents][Index]
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
Next: Structures, Previous: Ordinary functions, Up: Public Interface [Contents][Index]
5.1.2 Standalone methods
Previous: Standalone methods, Up: Public Interface [Contents][Index]
5.1.3 Structures
- Structure: vp-node ¶
Previous: Public Interface, Up: Definitions [Contents][Index]
5.2 Internals
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
- Reader: vp-node-center (instance) ¶
- Writer: (setf vp-node-center) (instance) ¶
-
- Package
- Source
- Target Slot
- Reader: vp-node-inner (instance) ¶
- 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
- Reader: vp-node-outer (instance) ¶
- Writer: (setf vp-node-outer) (instance) ¶
-
- Package
- Source
- Target Slot
- Function: vp-node-p (object) ¶
-
- Package
- Source
- Reader: vp-node-radius (instance) ¶
- Writer: (setf vp-node-radius) (instance) ¶
-
- Package
- Source
- Target Slot
Previous: Definitions, Up: The vp-trees Reference Manual [Contents][Index]
Appendix A Indexes
A.2 Functions
| Jump to: | (
C D F M P S V |
|---|
| Jump to: | (
C D F M P S V |
|---|
Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]
A.3 Variables
| Jump to: | C I O R S |
|---|
| Index Entry | Section | ||
|---|---|---|---|
| | |||
| C | |||
center: | Public structures | ||
| | |||
| I | |||
inner: | Public structures | ||
| | |||
| O | |||
outer: | Public structures | ||
| | |||
| R | |||
radius: | Public structures | ||
| | |||
| S | |||
Slot, center: | Public structures | ||
Slot, inner: | Public structures | ||
Slot, outer: | Public structures | ||
Slot, radius: | Public structures | ||
| | |||
| Jump to: | C I O R S |
|---|
A.4 Data types
| Jump to: | F P S V |
|---|
| Jump to: | F P S V |
|---|