On Locality-sensitive Indexing in Generic Metric Spaces

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors

NOVÁK David KYSELÁK Martin ZEZULA Pavel

Type Article in Proceedings
Conference 3rd International Conference on Similarity Search and Applications
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords locality-sensitive hashing; metric space; similarity search; approximation; scalability
Description 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: