On Locality-sensitive Indexing in Generic Metric Spaces

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	O indexovaní respektujícím vzdálenosti objektů v obecných metrických prostorech.
Autoři	NOVÁK David KYSELÁK Martin ZEZULA Pavel
Rok publikování	2010
Druh	Článek ve sborníku
Konference	3rd International Conference on Similarity Search and Applications
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	locality-sensitive hashing; metric space; similarity search; approximation; scalability
Popis	The concept of Locality-sensitive Hashing (LSH) has been successfully used for searching in high-dimensional data and a number of locality-preserving hash functions have been introduced. In order to extend the applicability of the LSH approach to a general metric space, we focus on a recently presented Metric Index (M-Index), we redefine its hashing and searching process in the terms of LSH, and perform extensive measurements on two datasets to verify that the M-Index fulfills the conditions of the LSH concept. We widely discuss "optimal" properties of LSH functions and the efficiency of a given LSH function with respect to kNN queries. The results also indicate that the M-Index hashing and searching is more efficient than the tested standard LSH approach for Euclidean distance.
Související projekty:	Institut Teoretické Informatiky Vyhledávání v rozsáhlých multimediálních databázích Podobnostní vyhledávání s konstantní škálovatelností Vizuální vyhledávání obrázků na Webu