License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.54
URN: urn:nbn:de:0030-drops-81688
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8168/
Chierichetti, Flavio ;
Kumar, Ravi ;
Panconesi, Alessandro ;
Terolli, Erisa
The Distortion of Locality Sensitive Hashing
Abstract
Given a pairwise similarity notion between objects, locality sensitive hashing (LSH) aims to construct a hash function family over the universe of objects such that the probability two objects hash to the same value is their similarity. LSH is a powerful algorithmic tool for large-scale applications and much work has been done to understand LSHable similarities, i.e., similarities that admit an LSH.
In this paper we focus on similarities that are provably non-LSHable and propose a notion of distortion to capture the approximation of such a similarity by a similarity that is LSHable. We consider several well-known non-LSHable similarities and show tight upper and lower bounds on their distortion. We also experimentally show that our upper bounds translate to e
BibTeX - Entry
@InProceedings{chierichetti_et_al:LIPIcs:2017:8168,
author = {Flavio Chierichetti and Ravi Kumar and Alessandro Panconesi and Erisa Terolli},
title = {{The Distortion of Locality Sensitive Hashing}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {54:1--54:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8168},
URN = {urn:nbn:de:0030-drops-81688},
doi = {10.4230/LIPIcs.ITCS.2017.54},
annote = {Keywords: locality sensitive hashing, distortion, similarity}
}
Keywords: |
|
locality sensitive hashing, distortion, similarity |
Collection: |
|
8th Innovations in Theoretical Computer Science Conference (ITCS 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
28.11.2017 |