TY - GEN
T1 - The distortion of locality sensitive hashing
AU - Chierichetti, Flavio
AU - Kumar, Ravi
AU - Panconesi, Alessandro
AU - Terolli, Erisa
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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.
AB - 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.
KW - Distortion
KW - Locality sensitive hashing
KW - Similarity
UR - http://www.scopus.com/inward/record.url?scp=85038591335&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038591335&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2017.54
DO - 10.4230/LIPIcs.ITCS.2017.54
M3 - Conference contribution
AN - SCOPUS:85038591335
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
A2 - Papadimitriou, Christos H.
T2 - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
Y2 - 9 January 2017 through 11 January 2017
ER -