Beyond Locality-Sensitive Hashing

Extensions of Lipschitz mappings into a Hilbert space

William B. Johnson and Joram Lindenstrauss · 1984

Earlier work this paper cites.

A randomized algorithm for closest-point queries

Kenneth L. Clarkson · 1988

Earlier work this paper cites.

Geometric algorithms and combinatorial optimization

Martin Grötschel, László Lovász, and Alexander Schrijver · 1988

Earlier work this paper cites.

FLASH: a fast look-up algorithm for string homology

Andrea Califano and Isidore Rigoutsos · 1993

Earlier work this paper cites.

Point location in arrangements of hyperplanes

Stefan Meiser · 1993

Earlier work this paper cites.

Multi-index hashing for information retrieval

Daniel H. Greene, Michal Parnas, and F. Frances Yao · 1994

Earlier work this paper cites.

The bit vector intersection problem (preliminary version)

Richard M. Karp, Orli Waarts, and Geoffrey Zweig · 1995

Earlier work this paper cites.

The geometry of graphs and some of its algorithmic applications

Nathan Linial, Eran London, and Yuri Rabinovich · 1995

Earlier work this paper cites.

The light bulb problem

Ramamohan Paturi, Sanguthevar Rajasekaran, and John H. Reif · 1995

Cited alongside, same era.

Filtering near-duplicate documents

Andrei Z. Broder · 1998

Cited alongside, same era.

Approximate nearest neighbors: towards removing the curse of dimensionality

Piotr Indyk and Rajeev Motwani · 1998

Cited alongside, same era.

Approximate graph coloring by semidefinite programming

David R. Karger, Rajeev Motwani, and Madhu Sudan · 1998

Cited alongside, same era.

Lectures on Discrete Geometry

Jiří Matoušek · 2002

Cited alongside, same era.

An elementary proof of a theorem of Johnson and Lindenstrauss

Sanjoy Dasgupta and Anupam Gupta · 2003

Cited alongside, same era.

A geometric approach to lower bounds for approximate near-neighbor search and partial match

Rina Panigrahy, Kunal Talwar, and Udi Wieder · 2008

Later among the works it cites.

Nearest Neighbor Search: the Old, the New, and the Impossible

Alexandr Andoni · 2009

Later among the works it cites.

Bucketing coding and information theory for the statistical highdimensional nearest-neighbor problem

Moshe Dubiner · 2010

Later among the works it cites.

Lower bounds on near neighbor search via metric expansion

Rina Panigrahy, Kunal Talwar, and Udi Wieder · 2010

Later among the works it cites.

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

Ryan O’Donnell, Yi Wu, and Yuan Zhou · 2011

Later among the works it cites.

Approximate nearest neighbor: towards removing the curse of dimensionality

Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani · 2012