1 Search Results for "Terolli, Erisa"

Document
DOI: 10.4230/LIPIcs.ITCS.2017.54
The Distortion of Locality Sensitive Hashing

Authors: Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 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. We also experimentally show that our upper bounds translate to e
Cite as

Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli. The Distortion of Locality Sensitive Hashing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chierichetti_et_al:LIPIcs.ITCS.2017.54,
  author =	{Chierichetti, Flavio and Kumar, Ravi and Panconesi, Alessandro and Terolli, Erisa},
  title =	{{The Distortion of Locality Sensitive Hashing}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.54},
  URN =		{urn:nbn:de:0030-drops-81688},
  doi =		{10.4230/LIPIcs.ITCS.2017.54},
  annote =	{Keywords: locality sensitive hashing, distortion, similarity}
}
  • Refine by Author
  • 1 Chierichetti, Flavio
  • 1 Kumar, Ravi
  • 1 Panconesi, Alessandro
  • 1 Terolli, Erisa

  • Refine by Classification

  • Refine by Keyword
  • 1 distortion
  • 1 locality sensitive hashing
  • 1 similarity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact