Adaptive Cluster Distance Bounding for High

Dimensional Indexing+
Abstract:
We consider approaches for similarity search in correlated, high-dimensional data
sets, which are derived within a clustering framework. We note that indexing by
vector approximation (!-"ile#, which was proposed as a techni$ue to combat the
%urse of &imensionality, employs scalar $uanti'ation, and hence necessarily
ignores dependencies across dimensions, which represents a source of sub
optimality. %lustering, on the other hand, exploits interdimensional correlations and
is thus a more compact representation of the data set. (owever, existing methods
to prune irrelevant clusters are based on bounding hyperspheres and)or bounding
rectangles, whose lack of tightness compromises their efficiency in exact nearest
neighbor search. We propose a new cluster-adaptive distance bound based on
separating hyperplane boundaries of oronoi clusters to complement our cluster
based index. *his bound enables efficient spatial filtering, with a relatively small
preprocessing storage overhead and is applicable to euclidean and +ahalanobis
similarity measures. ,xperiments in exact nearest-neighbor set retrieval, conducted
on real data sets, show that our indexing method is scalable with data set si'e and
data dimensionality and outperforms several recently proposed indexes. -elative to
the !-"ile, over a wide range of $uanti'ation resolutions, it is able to reduce
random ./ accesses, given (roughly# the same amount of se$uential ./ operations,
by factors reaching 0112 and more.
Existing Sstem:
(owever, existing methods to prune irrelevant clusters are based on bounding
hyperspheres and)or bounding rectangles, whose lack of tightness compromises
their efficiency in exact nearest neighbor search.
3patial $ueries, specifically nearest neighbor $ueries, in high-dimensional spaces
have been studied extensively. While several analyses have concluded that the
nearest neighbor search, with ,uclidean distance metric, is impractical at high
dimensions due to the notorious curse of dimensionality, others have suggested
that this may be over pessimistic. 3pecifically, the authors of have shown that what
&etermines the search performance (at least for --tree-like structures# is the
intrinsic dimensionality of the data set and not the dimensionality of the address
space (or the embedding dimensionality#.
We extend our distance bounding techni$ue to the +ahalanobis distance metric,
and note large gains over existing indexes.
!roposed Sstem:
We propose a new cluster-adaptive distance bound based on separating hyperplane
boundaries of oronoi clusters to complement our cluster based index. *his bound
enables efficient spatial filtering, with a relatively small pre-processing storage
overhead and is applicable to ,uclidean and +ahalanobis similarity measures.
,xperiments in exact nearest-neighbor set retrieval, conducted on real data-sets,
show that our indexing method is scalable with data-set si'e and data
dimensionality and outperforms several recently proposed indexes.
we outline our approach to indexing real high-dimensional data-sets. We focus on
the clustering paradigm for search and retrieval. *he data-set is clustered, so that
clusters can be retrieved in decreasing order of their probability of containing
entries relevant to the $uery.
We note that the ector !pproximation (!#-file techni$ue implicitly assumes
independence across dimensions, and that each component is uniformly distributed.
*his is an unrealistic assumption for real data-sets that typically exhibit significant
correlations across dimensions and non-uniform distributions. *o approach
optimality, an indexing techni$ue must take these properties into account. We
resort to a oronoi clustering framework as it can naturally exploit correlations
across dimensions (in fact, such clustering algorithms are the method of choice in
the design of vector $uanti'ers#. +oreover, we show how our clustering procedure
can be combined with any other generic clustering method of choice (such as
4.-%( # re$uiring only one additional scan of the data-set. 5astly, we note that the
se$uential scan is in fact a special case of clustering based index i.e. with only one
cluster.
3everal index structures exist that facilitate search and retrieval of multi-
dimensional data. .n low dimensional spaces, recursive partitioning of the space
with hyper-rectangles hyper-spheres or a combination of hyper-spheres and
hyper-rectangles have been found to be effective for nearest neighbor search and
retrieval. While the preceding methods speciali'e to ,uclidean distance (l6 norm#,
+-trees have been found to be effective for metric spaces with arbitrary distance
functions (which are metrics#.
3uch multi-dimensional indexes work well in low dimensional spaces, where they
outperform se$uential scan. 4ut it has been observed that the performance
degrades with increase in feature dimensions and, after a certain dimension
threshold, becomes inferior to se$uential scan. .n a celebrated result,
Weber et. !l have shown that whenever the dimensionality is above 01, these
methods are outperformed by simple se$uential scan. 3uch performance
degradation is attributed to 4ellman7s 8curse of dimensionality7, which refers to the
exponential growth of hyper-volume with dimensionality of the space.
"odule Description:
#$ A %e& Cluster Distance Bound
'$ Adaptabilit to (eighted Euclidean or "ahalanobis Distances
)$ An Efficient Search Index
*$ +ector Approximation ,iles
-$ Approximate Similarit Search
A %e& Cluster Distance Bound
%rucial to the effectiveness of the clustering-based search strategy is efficient
bounding of $uery-cluster distances. *his is the mechanism that allows the
elimination of irrelevant clusters. *raditionally, this has been performed with
bounding spheres and rectangles. (owever, hyperspheres and hyperrectangles are
generally not optimal bounding surfaces for clusters in high dimensional spaces. .n
fact, this is a phenomenon observed in the 3--tree, where the authors have used a
combination spheres and rectangles, to outperform indexes using only bounding
spheres (like the 33-tree# or bounding rectangles (--tree#.
*he premise herein is that, at high dimensions, considerable improvement in
efficiency can be achieved by relaxing restrictions on the regularity of bounding
surfaces (i.e., spheres or rectangles#. 3pecifically, by creating oronoi clusters,
withpiecewise-linear boundaries, we allow for more general convex polygon
structures that are able to efficiently bound the cluster surface. With the
construction of oronoi clusters under the ,uclidean distance measure, this is
possible. 4y pro9ection onto these hyperplane boundaries and complementing with
the cluster-hyperplane distance, we develop an appropriate lower bound on the
distance of a $uery to a cluster.
Adaptabilit to (eighted Euclidean or "ahalanobis Distances
While the ,uclidean distance metric is popular within the multimedia indexing
community it is by no means the correct distance measure, in that it may be a
poor approximation of user perceived similarities. *he +ahalanobis distance
measure has more degrees of freedom than the ,uclidean distance and by proper
updation (or relevance feedback#, has been found to be a much better estimator of
user perceptions and more recently# . We extend our distance bounding techni$ue
to the +ahalanobis distance metric, and note large gains over existing indexes.
An Efficient Search Index
*he data set is partitioned into multiple oronoi clusters and for any k:: $uery, the
clusters are ranked in order of the hyperplane bounds and in this way, the irrelevant
clusters are filtered out. We note that the se$uential scan is a special case of our
indexing, if there were only one cluster. !n important feature of our search index is
that we do not store the hyperplane boundaries (which form the faces of the
bounding polygons#, but rather generate them dynamically, from the cluster
centroids. *he only storage apart from the centroids are the cluster-hyperplane
boundary distances (or the smallest cluster-hyperplane distance#. 3ince our bound
is relatively tight, our search algorithm is effective in spatial filtering of
irrelevant clusters, resulting in significant performance gains. We expand on the
results and techni$ues initially presented in , with comparison against several
recently proposed indexing techni$ues.
+ector Approximation ,iles
! popular and effective techni$ue to overcome the curse of dimensionality is the
vector approximation file (!-"ile#. !-"ile partitions the space into hyper-
rectangular cells, to obtain a $uanti'ed approximation for the data that reside
inside the cells. :on-empty cell locations are encoded into bit strings and stored in
a separate approximation file, on the hard-disk. &uring a nearest neighbor search,
the vector approximation file is se$uentially scanned and upper and lower bounds
on the distance from the $uery vector to each cell are estimated. *he bounds are
used to prune irrelevant cells. *he final set of candidate vectors are then read from
the hard disk and the exact nearest neighbors are determined. !t this point, we
note that the terminology ector !pproximation is somewhat confusing, since
what is actually being performed is scalar quantization, where each component of
the feature vectors separately and uniformly quantized (in contradistinction with
vector $uanti'ation in the signal compression literature#.
!-"ile was followed by several more recent techni$ues to overcome the curse of
dimensionality. .n the !;-"ile, the data-set is rotated into a set of uncorrelated
dimensions, with more approximation bits being provided for dimensions with
higher variance. *he approximation cells are adaptively spaced according to the
data distribution. +ethods such as 5&- and the recently proposed non-linear
approximations aim to outperform se$uential scan by a combination of clustering
and dimensionality reduction. *here also exist a few hybrid methods, such as the !-
*ree, and .<-*ree, which combine !-style approximations within a tree based
index.
Approximate Similarit Search
5astly, it has been argued that the feature vectors and distance functions are often
only approximations of user perception of similarity. (ence, even the results of an
exact similarity search is inevitably perceptually approximate, with additional
rounds of $uery refinement necessary. %onversely, by performing an approximate
search, for a small penalty in
accuracy, considerable savings in $uery processing time would be possible.
,xamples of such search strategies are ++&- probabilistic searches and locality
sensitive hashing .*he reader is directed to for a more detailed survey of
approximate similarity search. *he limits of approximate indexing i.e. the optimal
tradeoffs between search $uality and search time has also been studied within an
information theoretic framework.
Sstem Architecture:
Hard&are Sstem .e/uirement
!rocessor 0 !entium 1III
3peed - 0.0 =h'
-!+ - 6>? +4(min#
(ard &isk - 61 =4
"loppy &rive - 0.@@ +4
Aey 4oard - 3tandard Windows Aeyboard
+ouse - *wo or *hree 4utton +ouse
+onitor - 3=!
S2( Sstem .e/uirement
3perating Sstem : Windows B>)BC)6111):*@.1.
Application Server : 4omcat5$6
,ront End : (*+5, Dava.
Scripts : Dava3cript.
Server side Script : Dava 3erver Eages.
Database : +ys$l.
Database Connectivit : D&4%.