The distortion of locality sensitive hashing

Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, Erisa Terolli

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

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.

Original languageEnglish
Title of host publication8th Innovations in Theoretical Computer Science Conference, ITCS 2017
EditorsChristos H. Papadimitriou
ISBN (Electronic)9783959770293
DOIs
StatePublished - 1 Nov 2017
Event8th Innovations in Theoretical Computer Science Conference, ITCS 2017 - Berkeley, United States
Duration: 9 Jan 201711 Jan 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume67
ISSN (Print)1868-8969

Conference

Conference8th Innovations in Theoretical Computer Science Conference, ITCS 2017
Country/TerritoryUnited States
CityBerkeley
Period9/01/1711/01/17

Keywords

  • Distortion
  • Locality sensitive hashing
  • Similarity

Fingerprint

Dive into the research topics of 'The distortion of locality sensitive hashing'. Together they form a unique fingerprint.

Cite this