Peter N. Yianilos
NEC Resarch Institute
We consider the computational problem of finding nearest neighbors in general metric spaces. Of particular interest are spaces that may not be conveniently embedded or approximated in Euclidian space, or where the dimensionality of a Euclidian representation is very high.
Also relevant are high-dimensional Euclidian settings in which the distribution of data is in some sense of lower dimension and embedded in the space.
The vp-tree (vantage point tree) is introduced in several forms,
together with associated algorithms, as an improved method for these
difficult search problems. Tree construction executes in time, and search is under certain circumstances and in the
limit,
expected time.
The theoretical basis for this approach is developed and the results of several experiments are reported. In Euclidian cases, kd-tree performance is compared.
Keywords: Metric Space, Nearest Neighbor, Computational Geometry, Associative Memory, Randomized Methods, Pattern Recognition, Clustering.
Nearest neighbor analysis is a well established technique for non-parametric density estimation, pattern recognition, memory-based reasoning, and vector quantization. It is also highly intuitive notion that seems to correspond in some way with the kind of inexact associative recall that is clearly a component of biological intelligence.
One useful abstraction of nearness is provided by the
classical notion of a mathematical metric space
[1]. Euclidian -space is but one example
of a metric space.
The Nearest Neighbor field includes the study of decision making and learning based on neighborhoods, the underlying metrics and spaces, and the matter of computing/searching for the neighborhood about a point. See [2] for a recent survey. Our focus is on search, and, for simplicity, on locating any single nearest neighbor.
Given a fixed finite subset of the space and calling it the database, our task is then to locate for each new query drawn from the space, a database element nearest to it.
As the database is finite, we might search by considering
every member. But in a somewhat analogous setting, binary
search can locate a queries position within a finite ordered
database while considering only elements.
Moreover, binary search proceeds given only ordinal knowledge.
I.e., it doesn't matter what the database objects are.
So while the notions of ordering and metric-distance are only loosely analogous, we are nevertheless motivated to look for improved search methods that depend only on the information received through metric evaluation.
Now binary search presumes that the database has been sorted
- an process. We then seek to organize our
database in as much time so that under some circumstances,
logarithmic time search is possible.
We introduce the vp-tree (vantage point tree) in several forms as one solution. This data structure and the algorithms to build and search it were first discovered and implemented by the author during 1986-871 in conjunction with the development of improved retrieval techniques relating to the PF474 device [3]. Motivation was provided by the fact that this chip's notion of string distance is non-Euclidian. Here elements of the metric space are strings, E.g., a database of city names and associated postal codes. This early work was described in [4].
Independently, Uhlmann has reported the same basic structure [5,6] calling it a metric tree.
There is a sizable Nearest Neighbor Search literature, and the vp-tree should properly be viewed as related to and descended from many earlier contributions which we now proceed to summarize.
Burkhard and Keller in [7] present three file structures for nearest neighbor retrieval. All three involve picking distinguished elements, and structuring according to distance from these members. Their techniques are coordinate free. The data structures amount to multi-way trees corresponding to integral valued metrics only.
Fukunaga in [8,9] exploits the triangle inequality to reduce distance computations searching a hierarchical decomposition of Euclidian Space. His methods are restricted to a Euclidian setting only by his use of a computed mean point for each subset. However this is not an essential component of his approach - at least conceptually. He recursively employs standard clustering [10] techniques to effect the decomposition and then branch-and-bound searches the resulting data structure. During search, the triangle inequality implies that a cluster need not be explored if the query is far enough outside of it. While exploring a cluster at the lowest level, Fukunaga further points out that the triangle inequality may be used to eliminate additional distance computations. A key point apparently overlooked, is that when the query is well inside of a cluster, the exterior need not be searched.
Collections of graphs are considered in [11] as
an abstract metric space with a metric assuming discrete
values only. This work is thus highly related to the
constructions of [7]. In their concluding
remarks the authors correctly anticipate generalization to
more continuous settings such as
.
The kd-tree of Friedman and Bentley [12,13,14,15] has emerged as a useful tool in Euclidian spaces of moderate dimension. Improvements relating to high-dimensional settings, distribution adaptation, and incremental searches, are described in [16], [17], and [18] respectively.
A kd-tree is built by recursively bisecting the database using single coordinate position cuts. For a given coordinate, the database is cut at the median of the distribution generated by projection onto that coordinate. An optimized kd-tree results by choosing the cutting coordinate to be that whose distribution exhibits the most spread.
In addition to various vp-tree forms, we have implemented optimized kd-tree software so that experimental comparisons can be made operating on identical spaces and given identical query sequences.
Like the kd-tree, each vp-tree node cuts/divides the space. But rather than using coordinate values, a vp-tree node employs distance from a selected vantage point. Near points make up the left/inside subspace while the right/outside subspace consists of far points. Proceeding recursively, a binary tree is formed. Each of its nodes identifies a vantage point, and for its children (left/right), the node contains bounds of their associated subspace as seen by the vantage point. Other forms of the vp-tree include additional subspace bounds and may employ buckets near leaf level.
To build these structures, the metric space is decomposed
using large spherical cuts centered in a sense at elements
near the corners of the space. This contrasts with the
coordinate aligned hyperplanar cuts of the kd-tree (See
Figures 1 & 2), and
the use of computed Euclidian cluster centroids in
[8]. Randomized algorithms for vp-tree
construction execute in
time and the
resulting tree occupies linear space.
For completeness, early work dealing with two special cases
should be mentioned. Retrieval of similar binary keys is
considered by Rivest in [19] and the
(max) metric setting is the focus of [20].
More recently, the Voronoi digram [21] has provided a useful tool in low- dimensional Euclidian settings - and the overall field and outlook of Computational Geometry has yielded many interesting results such as those of [22,23,24,25] and earlier [26].
Unfortunately neither the kd-tree, or the constructions of computational geometry, seem to provide a practical solution for high dimensions. As dimension increases, the kd-tree soon visits nearly every database element while other constructions rapidly consume storage space.
Furthermore, even if the database is in some sense of only moderately high dimension, it may not be possible or convenient to find or implement a dimension reducing transformation. So it is important that we develop techniques that can deal with raw untransformed data, and exhibit behavior as close as possible to intrinsic rather than representational dimension.
So despite considerable progress for Euclidian space, the development of more general techniques is important; not just because of the problems with high dimension, but also because there is no a priori reason to believe that all or even most useful metrics are Euclidian.
In the sections that follow we will consider a probabilistic
formulation of the problem and obtain certain theoretical
results, present the algorithms and data structures for the
vp-tree in several forms, and report on a number of
experiments. These experiments include Euclidian cases with
side-by-side kd-tree comparisons, non-Euclidian spaces, and
the difficult real-world problem of image fragment
retrieval. Here fragments as large as pixels
are treated corresponding to representational dimension
.
In this section we develop a simple but fairly general result which says that under certain circumstances, one may organize a database so that expected search time is logarithmic. It should be thought of as justifying in the limit the algorithms and data structures presented later. Only elementary concepts from General Topology and Measure/Probability Theory are employed.
For a query
, the nearest neighbor problem
then consists of finding a single minimally distant member of
. We may write
to stand for this
operation where the space may be omitted for brevity.
Now the element nearest to may be quite far, and for a
particular problem it may be reasonable to impose a distance
threshold
, at or beyond which one is uninterested in
the existence of neighbors. Also observe that while computing
, one may by reduce
as ever nearer neighbors
are encountered. We write
to denote this
important notion of
restricted search.
Next we will assume that the range of the space's distance
distance function is . Since any metric's range may
be compressed to this interval without affecting the
nearest-neighbor relation2, this restriction may be made without loss of generality3.
We begin by formalizing this notion of perspective and defining a related pseudo-distance function:
Let be a
bounded metric space. Given
a distinguished element
, we make the
following definitions for all
:
Function is best thought of as a projection of
into
, from the perspective of
. I.e. it
is
as seen by
, via
. Function
is
not in general a metric since if
and
are distinct but
equidistant from
,
. It is however a clearly
symmetric function and satisfies the triangle inequality,
making it a pseudo-metric.
Now since is a metric we may rely on symmetry and the
triangle inequality to arrive at:
Hence, distances shrink when measured by so that
in a sense dominates it. One useful consequence of this
behavior is given by the following obvious implication:
So if during a search we've already encountered a database
element at distance
from
, then as our search
progresses, we need not consider any element for which
. Thus, in the absence of coordinates or
Euclidian structure, we can begin to see how query's distance
to a distinguished vantage point may be exploited to
effectively direct and limit the search.
For some
consider now the image
of
in
. Next denote by
the median of
thus dividing
into
and
. The first of these intervals contains points from
the inside the sphere
, while the second consists of
points from outside and on the surface. We denote the inverse
images of these
and
respectively; and
imagine that
is divided in this way into left
and right subspaces.
Now
counts the points of
mapped
left to
, while
counts those
sent right to
. We can say little in general
about the comparative sizes of
and
since nothing
has been assumed about the nature of the metric space. In
particular if there are many points of
exactly
distance
from
, then
may be much larger than
.
But if spheres in
typically have on their
surface relatively few members of
, then we can say
that
, i.e, we have partitioned
into
two subsets of roughly equal size.
Now suppose for a given , that our objective is
,
and that
. Then it follows from
EQ- 1 that
may be excluded from
consideration. Similarly if
, we
may ignore
. In both cases then, roughly half the
space is excluded from consideration. Thus, the information
gleaned from a single point's perspective is sometimes
sufficient to significantly prune the search. However if
, then no such reduction
is possible.
So it is clear that our ability to prune is dependent on a
fortuitous choice of and
, on
, and on our
ability to choose
. We will succeed to the
extent that it is improbable that
(Figure 3).
If our probability distribution is in some sense nice
(see §2.3), then we can make this probability
approach zero as does. So that for
sufficiently
small, we will with high probability exclude approximately
half of the space from consideration.
It is easy now to see how we may recursively proceed to form a binary tree. This then forms the most basic vp-tree. Specific construction and search algorithms are presented in §3.
We therefore define probability measure which we
assume reflects the distribution from which both database
elements and queries are drawn4. It is worthwhile noting that
the arguments that follow may be generalized to deal with
separate distributions.
Now from EQ- 1 it is clear that mapping
is uniformly continuous, from which it follows that the
inverse images of any point or interval (whether open, closed,
or half-open) must have defined probability.
Thus, given some such point or interval , we may for the
sake of notational simplicity refer to
which is
understood to mean
. So if
, then
is the probability of the surface of
sphere
.
Now in the case of the discrete metric, there is about every point a spherical surface of probability one. This is in stark contrast to Euclidian settings where any volume related probability measure results in zero probability spherical surfaces. Remembering that the discrete metric is pathological to nearest neighbor schemes, we are led to consider metrics which share this property.
Let
be a metric space with associated
probability measure
, the combination is said to have
the ZPS (Zero Probability Spheres) property if and only
if:
,
where
.
The discrete metric is thus excluded along with many other cases. This is however a very strong condition. We assume it for simplicity's sake but comment that there are several ways to weaken it while preserving the essence of the arguments that follow.
We now make more rigorous our earlier comments regarding procedures for recursive space bisection.
proof: Let
and if
draw additional elements until equality.
Pick some
and consider
. Set value
so that
equally many image points are to its left and right.
Continue recursively bisecting the space - forming a
binary tree and establishing
for each non-leaf
element of
. By ZPS this is almost always
possible (failure probability zero).
Define
so
.
Associate with values
and
. Now by
our earlier comments we may choose
such that
.
In what follows we will proceed recursively to
associate and
values to each non-leaf
node.
The root's probability function is just . We
define that of its left child to be essentially
but more formally
.
To understand this observe that
search
will explore leftward only if
. An alternative view is that the
left subtree is only concerned with the subspace
and sees it
as the entire space. In a similar way we associate a
new probability function with the right child. Now it
must be noted that these modified functions remain
probability measures, and inherit ZPS.
Having done this, and
values may be
associated with the left and right child. This
enables the process to continue down the tree until
all non-leaf nodes have values. Finally set
.
For a query drawn by
, We compute
starting at the root. Thus a single metric evaluation
is always performed. Then with probability of no more
than
, we will be required to
explore leftward. The probability of rightward
exploration is similarly bounded by
. In both cases the subtrees
will see the query as random within their
subspaces of interest.
If leaf level is reached, a single evaluation is
always performed. It then follows that the overall
cost (metric evaluations) of the search is on an
expected basis is the value where
and
. This recursion
evaluates to
which
is bounded above by
A result similar in flavor may be proven in which a tree is built and used to classify additional members of the space so that all buckets (leaf levels) have equal probability. Each of these leaves then correspond to a subspace of the metric space and we have in effect then equipartitioned the space with respect to the probability distribution. This is analogous to vector quantization in Euclidian space. Thinking of the root-leaf path as a binary code, we might also interpret it as metric space hashing.
proof: For brevity's sake assume is a power of 2. As in
the previous theorem we will build a binary tree.
Before we were forced to bisect a particular finite
database at each level so that in general
. Here we begin by building a balanced binary
tree so that its initial
levels
have
. We may do this
by picking for the root an arbitrary element, then
setting the root's
so that
.
Having done this we may pick a vantage point for the
left and right children from the associated subspaces
and proceed recursively to the required depth.
Observe that the leaf level subspaces have equal
probability of . As for
theorem- 1 we may find
for this tree so that we expect to visit at most
nodes. So clearly no more
than this number of leaf nodes will be visited on an
expected basis.
Now each element of a particular drawn database may
be classified and then attached to this
tree by first identifying which of the leaf
partitions it belongs to, and adding it to an
initially empty list rooted at and replacing the
corresponding leaf node. The expected size of each
list is clearly one. So the final expected number of
metric evaluations remains
.
These theorems describe binary constructions to motivate the
algorithms and experiments which follow; but higher degree
trees may be built by further partitioning . In the
extreme case the root has degree
and only three metric
evaluations are expected. As a practical matter however, the
values necessary to approach even
search
are so small as to be of little practical value. So the
basic theorems presented are best thought of as existence
results which establish a theoretical foundation while
motivating algorithm development.
As an example consider the unit square with uniform
probability distribution. Here we must choose so that
two regions of area
result. Three natural choices for
consist of the square's midpoint (denoted
), a corner
(denoted
), and the midpoint of an edge (denoted
).
These along with their associated division boundaries are
illustrated in Figure 4.
To choose among them, notice that for small the length
of the boundary will be proportional in the limit to the
probability that no pruning takes place. Thus minimizing
these boundary lengths (denoted
in the figure) is the
obvious strategy.
Observe that is by far the worst choice as its boundary
length is double that of
. Choice
is also much
better than
, but not quite as good as
. It is
interesting to note that from a traditional clustering
viewpoint,
is the natural centroid. But we have seen
that it is far from the best choice. From this example we
draw the intuition that points near the corners of the
space make the best vantage points. (See again the vp-tree
decomposition of Figure- 1).
These simple results then suggest a strategy for vantage point selection, and given a particular distribution, provide a framework for drawing more conclusions. The ZPS distribution restriction is key to achieving them; and our overall outlook in which finite cases are imagined to be drawn from a larger more continuous space, distinguishes in part this work from the discrete distance setting of [7,11].
Under then, distances in the Euclidian range space
are always dominated by distances in the domain. This amounts
to Euclidian approximation of the original metric.
This mapping and elementary observation will help us later
define enhanced forms of the vp-tree.
An optimized tree results because function Select_vp endevours to pick better than random vantage
points. Replacing it with a simple random selection generates
a valid and effective tree; but experiments have shown that
some effort towards making better choices, results in
non-trivial search-time savings.
Our algorithm constructs a set of vantage point candidates by random
sampling, and then evaluates each of them.
Evaluation is accomplished by extracting another sample, from
which the median of
, and a corresponding moment
are estimated. Finally, based on these statistical images, the candidate with the largest moment is chosen.
Given constant size samples, execution time is
.
Our experimental implementation includes several sampling and
evaluation parameters.
function Make_vp_tree(S)
if then return
new(node);
node.p
Select_vp(S);
node.mu
;
L
;
R
;
node.left
Make_vp_tree(L);
node
.right
Make_vp_tree(R);
return node;
function Select_vp(S)
P Random sample of S;
best_spread 0;
for
D Random sample of S;
mu
;
spread
;
if spread best_spread
best_spread
spread; best_p
p;
return best_p;
In the simple construction above, only mu is retained in a node to describe the metric relationship of the left/right subspaces to the node's vantage point. At the expense of storage space, one may retain instead four values representing lower/upper bounds of each subspace as seen by the vantage point. It is this form of tree that is actually used in the experiments we later report.
The central working structure employed consists of a database
element identifier `id', and a list `hist' of
distances from the item to each vantage point tracing back to
the root. A list of these structures is initialized from the
entire database, with the history set to null. The algorithm
then recursively splits the list into two lists and
,
while adding to the history of each item. Each resulting tree
node then contains a list `bnds' giving lower and upper
bounds (a range interval) for its corresponding subspace as
seen by each ancestral vantage point.
Execution time remains . Assuming fixed
precision is used to represent the bounds, the tree occupies
linear space. But this is an asymptotic statement, and over
the practical range of
, and given fixed machine word
sizes, the space is better described by
.
function Make_vps_tree(S)
list = ;
for
new(item); item
.id
; item
.hist
;
add item to list;
return Recurse_vps_tree(list);
function Recurse_vps_tree(list)
if list then return
new(node); node.p
Select_vp(list);
delete node.p from list;
for item list
append d(p,item
.id) to item
.hist;
mu
tail(item
.hist);
L
; R
;
for item list
if tail(item
.hist)
then
add item to L, delete from list;
else
add item to R, delete from list;
node.left
Recurse_vps_tree(L);
node
.right
Recurse_vps_tree(R);
node.bnds
Merge(node
.left
.bnds,
node
.right
.bnds,node
.p
.hist);
return node;
function Merge(range_list1,range_list2,value_list) ``The two range lists are combined with the value list to yield a single range list which is returned.''5
There's no guaranty that these algorithms build a balanced tree7 - for in practice, the ZPS assumption may not hold. Furthermore, even if it does, we may draw a rather pathological database. So in the end, the balance achieved is problem dependent.
One may think of these vectors of distances, as the image of an element under the set perspective mapping defined by the ordered set of its ancestors. (§2.6)
The data structures corresponding to these three tree types
are depicted in Figure- 5. Database
elements are represented by a 4-byte integer, real values by a
4-byte float, and bucket distances by a 2-byte integer. These
correspond closely to our experimental implementation; except
that the
-tree we implement contains subspace bounds rather
than the single value mu.
![]() |
procedure Search(n)
if n then return ;
x d(q,n
.id);
if x tau then
tau
x;
best
n
.id;
middle (n
.left_bnd[high] + n
.right_bnd[low])/2;
if x middle then
if x
then
Search(n
.left);
if x
then
Search(n
.right);
else
if x
then
Search(n
.right);
if x
then
Search(n
.left);
Notice that the order of exploration is determined by comparison with the middle value computed. This is properly viewed as a heuristic. In high dimensions this may not be the best choice and branching order represents an interesting area for future work.
Actual databases, particularly those consisting of signals or
images, frequently contain large clusters of very
similar items. In these cases one may find that search
rapidly locates a very near neighbor, and then performs much
more work which yields only a very slightly nearer item.
Because of this problem, our implementation includes an
error tolerance setting which in effect narrows intervals
and
. E.g. Given tolerance 0.01, the procedure
will return a neighbor which is guaranteed to be at most 0.01
more distant from the query than its true nearest neighbor.
Now having summarized and sketched our algorithms and data structures, we turn to experimental results.
A modular software system was built with plug-in metric spaces and search routines. Two basic metric space settings were implemented: hypercubes, and image fragments. Both support various metrics including the standard Minkowski family.
The vp-tree8 and kd-tree are compared for the ,
, and
metrics as dimension ranges from 2 to 14. Since interior
vp-tree nodes contain data elements while the kd-tree contains data
elements at its leaf level only, we use total nodes visited to measure
complexity. The resulting statistics were observed to agree well with
actual CPU time used.
Figure 6 demonstrates the remarkable agreement
between these two methods for the metric. Similar agreement is
found for the
metric, while for
, the vp-tree maintains
a small constant advantage. Detailed examination of the results does
however reveal one qualitative difference which increases with
dimension. By dimension 14, the kd-tree visits roughly
times as
many nodes under
versus
. The ratio for vp-tree
search is only
. This suggests that vp-tree performance may be
flatter with respect to choice of metric.
If dimension is fixed and database size grows, we expect and find asymptotically logarithmic growth in search time. For dimension 8 (Figure 7), kd-tree performance is in the limit between that of the vps-tree and vp-tree. Examining CPU time, the same is true although the differences are smaller. In dimensions 2 and 4, the performance ordering from best to worst is vps-tree, vp-tree, then kd-tree for all database sizes.
The kd-tree does however eventually catch up in this random
hypercube environment. By dimension 12 for example, it visits fewer
nodes than vps-tree search once database size grows beyond .
By this point however, neither perform very well - visiting roughly
of the nodes.
So despite their ignorance of the coordinate structure of the space, and randomized construction, vp-trees compare well in this setting with the kd-tree.
Comparisons with the experiments of [8] are more
difficult because leaf level buckets are employed. Nevertheless, based
purely on metric evaluations, the kd-tree and vp/
-tree methods
produce superior results.
Pseudorandom databases are then drawn in a coordinate-wise uniform fashion
within
and mapped to the longer vectors of
.
To study this setting we define three types of query distribution - all pseudo-random but confined to different subspaces:
The first two of these are fairly clear; the third requires explanation. It is proposed as a better model for the independent effects of subspace and observational error.
We first embed a plane into 10-dimensional space (,
) and
draw a 2,000 element database. Table 1 contains the
results. The values shown are average nodes visited. Its first and
last columns contain for comparison purposes, performance for fully-
random 2 and 10 dimensional hypercubes. The
`
' columns contain results for a 2-dimensional space embedded in 10-space given
types 1 and 2 queries.
All trees perform well given type 1 queries and degrade for type 2. But notice that the kd-tree searches nearly every node 9 when presented with type 2 queries. In fact, its performance is markedly worse that in the fully random 10-dimensional setting. This illustrates the weakness of coordinate-based schemes and the pitfalls of assuming that random cases are indicative in any way of overall performance.
If this same database is now embedded into ever higher dimensions (3
through 50) and type 3 queries presented, Figure 8
results. In this graph, (the amplitude of added noise) is
expressed on the horizontal axis in normalized units.10The bottom group of six curves corresponds to vp-tree performance for
range spaces of increasing dimension. The upper group provides
kd-tree results. It is apparent that vp-tree performance degrades in
a more reasonable fashion for queries increasingly distant from the
data plane.
Similar results are obtained given much larger databases and given
databases as simple as a mere line embedded in
.
These results suggest that if one is given a database of unknown internal structure, the vp-tree may represent a better approach to organization for nearest neighbor retrieval.
The Euclidian metric is then applied and nearest neighbor retrieval effectiveness studied. The vp-trees built were very nearly balanced although large uniform regions (e.g. the sky) represent pathological subspaces creating occasional deep subtrees. Databases built from as many as 8 library images were considered corresponding to a metric space and vp-tree having over two million members.
For queries from the database, our depth-first branch and bound search reduces
to standard binary tree search and the query is located without
backtracking. Exactly node visits are then required where this refers
to the depth in the tree of the element matching the query.
For queries even slightly distant from a database member, considerably
more work is necessary. For window size and trees of
roughly one million elements, 5% of the nodes are visited on average
to satisfy very near queries while 15% are visited in the general
case.
In one series of experiments we choose subsets of four images each, and formed vp-trees. Searches were then performed using two query sources. The first source (general) consisted of a subset of six images different from each of the database images. The second source (similar) consisted of a pair of images captured so as to correspond very closely to a database image in each of the subsets. The results are summarized in table- 2 where the percentages shown are averages over the two databases.11
Figures 9 and 10 depict -pixel query/nearest-neighbor pairs for the similar and general
cases respectively.12
![]() |
![]() |
Limited experiments with
-tree trees result in performance improvements
that vary greatly, but seem to fall in the
range.
We do not expect the kd-tree to perform well for large windows but perform
experiments to verify our intuition. Indeed, little advantage is
gained over exhaustive search for window sizes as small as .
Reducing search radius does decrease vp-tree search time but
significant savings are achieved only at the expense of search
effectiveness. In one experiment
was reduced until search time
was roughly halved. At this radius however, a nearest neighbor was
located for only half of the queries. In another radius related
experiment using single queries, we reduced
to only slightly
more than the known distance to their nearest neighbor - thus
insuring search success. In one case, the nearest neighbor was
located after only 1200 node visits, with an additional 13,799
required to complete the search. We offer this as illustration that
finding a nearest neighbor and being sure are two separate
matters - with the latter often dominating total cost.
This and other experiments suggest that heuristic search techniques represent an interesting area for further investigation. Indeed, independent of its ability to find nearest neighbors and prove it, the vp-tree method using only the simple search technique described, seems to very rapidly locate highly similar database elements. In some applications this may suffice.
Image searches with error tolerance (§3.4) also result in reduced work. Our limited experiments suggest however that reasonable tolerance values provide savings of at most perhaps a factor of two.
Finally, independent of search-time refinements, better data structures and construction techniques, represent a clear opportunity for future work.
We have come to view the vp-tree construction and search processes as somewhat analogous to standard sort and binary search in one dimension - first because of their complexity, but perhaps more importantly because both primarily exploit ordinal rather than cardinal/representational information.
One may sort a file or build a binary tree of arbitrary objects given only an appropriate comparison function. By analogy, we have shown that a metric space may be organized for nearest neighbor retrieval given only the metric - without consideration of any particular representation such as a coordinate form. So for example, we will build the same vp-tree for a database in Euclidian space, independent of coordinate system.
We propose that techniques such as those of this paper should be used to develop application portable utility software for dynamic organization of and nearest neighbor retrieval from databases under application specific metrics.
Finally we observe that both kd-trees and vp-trees may be viewed as very special cases arising from particular uniformly continuous functionals and lying within the divide-and-conquer algorithmic paradigm. In one case coordinate projection, and in the other, distance from distinguished elements is used to hierarchically decompose space.
I thank Eric Baum, Bill Gear, Igor Rivin, and Warren Smith for helpful discussions.
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.47)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -image_type gif -nonext_page_in_navigation -noprevious_page_in_navigation -up_url ../main.html -up_title 'Publication homepage' -numbered_footnotes vptree.tex
The translation was initiated by Peter N. Yianilos on 2002-07-07