Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem
| dc.creator | Volnyansky, Ilya | |
| dc.date | 2009-05-13 | |
| dc.date.accessioned | 2026-07-07T13:14:32Z | |
| dc.date.available | 2026-07-07T13:14:32Z | |
| dc.description | 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 $(Ω_d)$ from which we pick datasets $X_d$ in an i.i.d. fashion. We call the subscript $d$ the dimension of the space $Ω_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 $Ω_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. | |
| dc.description | 56 pages, 7 figures Master's Thesis in Mathematics, University of Ottawa (Canada) Supervisor: Vladimir Pestov | |
| dc.identifier | https://arxiv.org/abs/0905.2141 | |
| dc.identifier | http://arxiv.org/abs/0905.2141 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/230237 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Curse of Dimensionality in the Application of Pivot-based Indexes to the Similarity Search Problem | |
| dc.type | text |