Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem

Details Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem

2009-05-13

arxiv.org/abs/0905.2141v1

Computer Science

Data Structures and Algorithms

56 pages, 7 figures Master's Thesis in Mathematics, University of Ottawa (Canada) Supervisor: Vladimir Pestov

Scientific paper

In this work we study the validity of the so-called curse of dimensionality for indexing of databases for similarity search. We perform an asymptotic analysis, with a test model based on a sequence of metric spaces $(\Omega_d)$ from which we pick datasets $X_d$ in an i.i.d. fashion. We call the subscript $d$ the dimension of the space $\Omega_d$ (e.g. for $\mathbb{R}^d$ the dimension is just the usual one) and we allow the size of the dataset $n=n_d$ to be such that $d$ is superlogarithmic but subpolynomial in $n$. We study the asymptotic performance of pivot-based indexing schemes where the number of pivots is $o(n/d)$. We pick the relatively simple cost model of similarity search where we count each distance calculation as a single computation and disregard the rest. We demonstrate that if the spaces $\Omega_d$ exhibit the (fairly common) concentration of measure phenomenon the performance of similarity search using such indexes is asymptotically linear in $n$. That is for large enough $d$ the difference between using such an index and performing a search without an index at all is negligeable. Thus we confirm the curse of dimensionality in this setting.

Affiliated with

Also associated with

No associations

Rating

Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-129378