Skip to main navigation Skip to search Skip to main content

The distortion of locality sensitive hashing

  • Flavio Chierichetti
  • , Ravi Kumar
  • , Alessandro Panconesi
  • , Erisa Terolli

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    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
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959770293
    DOIs
    StatePublished - Nov 1 2017
    Event8th Innovations in Theoretical Computer Science Conference, ITCS 2017 - Berkeley, United States
    Duration: Jan 9 2017 → Jan 11 2017

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume67

    Other

    Other8th Innovations in Theoretical Computer Science Conference, ITCS 2017
    Country/TerritoryUnited States
    CityBerkeley
    Period1/9/17 → 1/11/17

    ASJC Scopus subject areas

    • Software

    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