Optimal Data-Dependent Hashing for Approximate Near Neighbors

Worst-case optimal insertion and deletion methods for decomposable searching problems

Mark H. Overmars and Jan van Leeuwen · 1981

Earlier work this paper cites.

Storing a sparse table with O(1) worst case access time

Michael L. Fredman, János Komlós, and Endre Szemerédi · 1984

Earlier work this paper cites.

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.

Refinements to nearest-neighbor searching in

Robert F. Sproull · 1991

Earlier work this paper cites.

Point location in arrangements of hyperplanes

Stefan Meiser · 1993

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.

Approximate nearest neighbors: towards removing the curse of dimensionality

Piotr Indyk and Rajeev Motwani · 1998

Earlier work this paper cites.

Approximate graph coloring by semidefinite programming

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

Earlier work this paper cites.

A fast nearest-neighbor algorithm based on a principal axis search tree

James McNames · 2001

Earlier work this paper cites.

Similarity estimation techniques from rounding algorithms

Moses Charikar · 2002

Earlier work this paper cites.

An elementary proof of a theorem of Johnson and Lindenstrauss

Sanjoy Dasgupta and Anupam Gupta · 2003

Earlier work this paper cites.

Locality-sensitive hashing scheme based on p-stable distributions

Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni · 2004

Cited alongside, same era.

Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions

Alexandr Andoni and Piotr Indyk · 2006

Cited alongside, same era.

Lower bounds on locality sensitive hashing

Rajeev Motwani, Assaf Naor, and Rina Panigrahy · 2007

Cited alongside, same era.

Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions

Alexandr Andoni and Piotr Indyk · 2008

Cited alongside, same era.

Random projection trees and low dimensional manifolds

Sanjoy Dasgupta and Yoav Freund · 2008

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

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.

The power of comparative reasoning

Jay Yagnik, Dennis Strelow, David A. Ross, and Ruei-Sung Lin · 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

Later among the works it cites.

Finding correlations in subquadratic time, with applications to learning parities and juntas

Gregory Valiant · 2012

Later among the works it cites.

Frontiers in Massive Data Analysis

National Research Council · 2013

Later among the works it cites.

Spectral approaches to nearest neighbor search

Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, and Robert Krauthgamer · 2014

Later among the works it cites.