Near neighbor search in nonmetric space - Archive ouverte HAL Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2005

Near neighbor search in nonmetric space

Joannès Vermorel
  • Fonction : Auteur
  • PersonId : 830055

Résumé

We consider the computational problem of the Near Neighbor Search (NNS) in nonmetric spaces. Nonmetric spaces are the generalization of the metric spaces because they do not require the triangular inequality assumption. Nonmetric spaces are important because many similarity measures (between images, proteins, etc) do not verify the triangular inequality. We show the nonmetric situation calls for different evaluation criterions of NNS algorithms. As a first attempt, to our knowledge, to perform general nonmetric NNS, we introduce such evaluation criterions. The insights provided by those criterions lead us to introduce a new category of search structures, called "densitrees", that extend the classical metric tree algorithm for the nonmetric NNS. Against well established datasets, our preliminary empirical results lead us to a counter-intuitive conclusion: "the triangular inequality has only a secondary contribution on the efficiency metric". Additionally, the densitrees, although very naively implemented, performs reasonably well both in metric and nonmetric situations.
Fichier principal
Vignette du fichier
densitree-v2.pdf (426.22 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-00004887 , version 1 (09-05-2005)
hal-00004887 , version 2 (30-08-2005)

Identifiants

  • HAL Id : hal-00004887 , version 2

Citer

Joannès Vermorel. Near neighbor search in nonmetric space. 2005. ⟨hal-00004887v2⟩
124 Consultations
603 Téléchargements

Partager

Gmail Facebook X LinkedIn More