On the adversarial robustness of Locality-Sensitive Hashing in Hamming space

Michael Kapralov, Mikhail Makarov, Christian Sohler

Locality-sensitive hashing~[Indyk,Motwani'98] is a classical data structure for approximate nearest neighbor search. It allows, after a close to linear time preprocessing of the in…