Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the vp-trees Reference Manual, version 0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 15:27:38 2020 GMT+0.
• Introduction | What vp-trees is all about | |
• Systems | The systems documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
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: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The vp-trees system |
Vasily Postnicov <shamaz.mazum@gmail.com>
2-clause BSD
Perceptual hash algorithms for images
0.1
vp-trees.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
• The vp-trees.asd file | ||
• The vp-trees/src/package.lisp file | ||
• The vp-trees/src/vp-trees.lisp file |
Next: The vp-trees/src/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
vp-trees.asd
vp-trees (system)
Next: The vp-trees/src/vp-trees․lisp file, Previous: The vp-trees․asd file, Up: Lisp files [Contents][Index]
Previous: The vp-trees/src/package․lisp file, Up: Lisp files [Contents][Index]
src/package.lisp (file)
vp-trees (system)
src/vp-trees.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The vp-trees package |
src/package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported functions | ||
• Exported structures |
Next: Exported structures, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
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).
src/vp-trees.lisp (file)
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))).
src/vp-trees.lisp (file)
Previous: Exported functions, Up: Exported definitions [Contents][Index]
src/vp-trees.lisp (file)
structure-object (structure)
print-object (method)
vp-node-center (function)
(setf vp-node-center) (function)
number
0
vp-node-radius (function)
(setf vp-node-radius) (function)
(or null vp-trees:vp-node)
vp-node-inner (function)
(setf vp-node-inner) (function)
(or null vp-trees:vp-node)
vp-node-outer (function)
(setf vp-node-outer) (function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal functions |
Previous: Internal definitions, Up: Internal definitions [Contents][Index]
src/vp-trees.lisp (file)
Divide a set in two halves depending on the value of predicate function
src/vp-trees.lisp (file)
src/vp-trees.lisp (file)
Return median value for a list
src/vp-trees.lisp (file)
Pick a random value from a list and return this value and a new list with this value removed.
src/vp-trees.lisp (file)
src/vp-trees.lisp (file)
src/vp-trees.lisp (file)
True if this node is a leaf
src/vp-trees.lisp (file)
src/vp-trees.lisp (file)
src/vp-trees.lisp (file)
src/vp-trees.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | F L V |
---|
Jump to: | F L V |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | (
C D F M P S V |
---|
Jump to: | (
C D F M P S V |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Jump to: | C I O R S |
---|
Jump to: | C I O R S |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | P S V |
---|
Jump to: | P S V |
---|