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.

The distortion of locality sensitive hashing / Chierichetti, Flavio; Kumar, Ravi; Panconesi, Alessandro; Terolli, Erisa. - 67:(2017). (Intervento presentato al convegno 8th Innovations in Theoretical Computer Science Conference, ITCS 2017 tenutosi a University of California at Berkeley, usa) [10.4230/LIPIcs.ITCS.2017.54].

The distortion of locality sensitive hashing

Chierichetti, Flavio;Panconesi, Alessandro;
2017

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.
2017
8th Innovations in Theoretical Computer Science Conference, ITCS 2017
Distortion; Locality sensitive hashing; Similarity; Software
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
The distortion of locality sensitive hashing / Chierichetti, Flavio; Kumar, Ravi; Panconesi, Alessandro; Terolli, Erisa. - 67:(2017). (Intervento presentato al convegno 8th Innovations in Theoretical Computer Science Conference, ITCS 2017 tenutosi a University of California at Berkeley, usa) [10.4230/LIPIcs.ITCS.2017.54].
File allegati a questo prodotto
File Dimensione Formato  
Chierichetti_Distortion_2017.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 764.67 kB
Formato Adobe PDF
764.67 kB Adobe PDF
Chierichetti_index_2017.pdf

accesso aperto

Tipologia: Altro materiale allegato
Licenza: Creative commons
Dimensione 293.22 kB
Formato Adobe PDF
293.22 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1170551
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact