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

Ilya Volnyansky

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 ba…