Carnegie Mellon University
Browse
file.pdf (242.39 kB)

Optimal lower bounds for locality sensitive hashing (except when q is tiny)

Download (242.39 kB)
journal contribution
posted on 2005-02-01, 00:00 authored by Ryan O'Donnell, Yi Wu, Yuan Zhou
We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in {0; 1}d under the Hamming distance. Recall that H is said to be an (r; cr; p; q)-sensitive hash family if all pairs x; y ∈ {0; 1}d with dist(x; y) ≤ r have probability at least p of collision under a randomly chosen h ∈ H, whereas all pairs x; y ∈ {0; 1}d with dist(x; y) ≥ cr have probability at most q of collision. Typically, one considers d → ∞, with c > 1 fixed and q bounded away from 0.

History

Publisher Statement

Appears in Journal of Computer Security, vol. 13(1) (Roberto Gorrieri, editor), pp. 3-47, IOS Press, February 2005.

Date

2005-02-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC