2026-08-15T15:04:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8168 2024-03-06T10:39:22Z ddc:004 open_access

The Distortion of Locality Sensitive Hashing Chierichetti, Flavio Kumar, Ravi Panconesi, Alessandro Terolli, Erisa locality sensitive hashing distortion similarity 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 Schloss Dagstuhl – Leibniz-Zentrum für Informatik Flavio Chierichetti and Ravi Kumar and Alessandro Panconesi and Erisa Terolli 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.54 urn:nbn:de:0030-drops-81688 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.54 eng https://creativecommons.org/licenses/by/3.0/legalcode