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: https://drops.dagstuhl.de/opus/volltexte/2017/8168/
Chierichetti, Flavio ; Kumar, Ravi ; Panconesi, Alessandro ; Terolli, Erisa
The Distortion of Locality Sensitive Hashing
| pdf-format: |
|
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 | |
| Seminar: | 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 28.11.2017 |
