Publication details

<< back
 

On Locality-sensitive Indexing in Generic Metric Spaces

Basic information
Original title:On Locality-sensitive Indexing in Generic Metric Spaces
Authors:David Novák, Martin Kyselák, Pavel Zezula
Further information
Citation:NOVÁK, David - KYSELÁK, Martin - ZEZULA, Pavel. On Locality-sensitive Indexing in Generic Metric Spaces. In 3rd International Conference on Similarity Search and Applications. New York : ACM Press, 2010. ISBN 978-1-4503-0420-7, pp. 59-66. 18.9.2010, Istanbul, Turkey.
Original language:English
Field:Informatika
Type:Article in Proceedings
Keywords:locality-sensitive hashing; metric space; similarity search; approximation; scalability

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.

Related projects:

 
 
top