L’outil de licence Creative Commons du formulaire de soumission ne fonctionne pas actuellement. Pour ajouter une licence CC à votre thèse ou publication, contactez ruor@uottawa.ca après le dépôt. -- The Creative Commons licence tool in the submission form is currently unavailable. To apply a CC licence to your thesis or publication, contact ruor@uottawa.ca after the deposit.

Curse of dimensionality in the application of pivot-based indexes to the similarity search problem

En cours de chargement...
Vignette d'image

Date

Nom de la revue

ISSN de la revue

Titre du volume

Éditeur

University of Ottawa (Canada)

Résumé

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 (O d) from which we pick datasets Xd in an i.i.d. fashion. We call the subscript d the dimension of the space Od (e.g. for Rd the dimension is just the usual one) and we allow the size of the dataset n = nd 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 Od 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.

Description

Mots-clés

Citation

Source: Masters Abstracts International, Volume: 48-04, page: 2297.

Approbation

Évaluation

Complété par

Référencé par