The Sixth DIMACS Implementation Challenge:
Near Neighbor Searches

May 29, 1998

If you have any additional references which you would like added, please let us know at


Pankaj Agarwal and Jirí Matousek.
Ray shooting and parametric search.
In Proc. 24th ACM Symp. Theory Comp., pages 517-526, 1992.

Sunil Arya, David Mount, Nathan Netanyahu, Ruth Silverman, and Angela Wu.
An optimal algorithm for approximate nearest neighbor searching.
In Proc. 5th ACM Symp. on Discrete Algorithms, pages 573-583, 1994.

Jon L. Bentley.
Multidimensional binary search trees used for associative searching.
Communication of the ACM, 18(9):509-517, 1975.

Sergey Brin.
Near neighbor search in large metric spaces.
In Proc. 21st Inter. Conf. on Very Large Data Bases, pages 574-584, 1995.

Kenneth Clarkson.
A randomized algorithm for closest-point queries.
SIAM J. Comput., 17(4):830-847, 1988.

Kenneth Clarkson.
An algorithm for approximate closest-point queries.
In Proc. 10th ACM Symp. on Computational Geometry, pages 160-164, 1994.

Kenneth Clarkson.
Nearest neighbor queries in metric spaces.
In Proc. 39th ACM Symp. Theory Comp., pages 609-617, 1997.

David Dobkin and Richard Lipton.
Multidimensional searching problems.
SIAM J. Comput., 5(2):181-186, 1976.

C. Feustel and L. Shapiro.
The nearest neighbor problem in an abstract metric space.
Pattern Recognition Letters, 1:125-128, 1982.

Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, and Santosh Vempala.
Locality-preserving hashing in multidimensional spaces.
In Proc. 39th ACM Symp. Theory Comp., pages 618-625, 1997.

Jon Kleinberg.
Two algorithms for nearest-neighbor search in high dimensions.
In Proc. 39th ACM Symp. Theory Comp., pages 599-608, 1997.

Jirí Matousek.
Reporting points in halfspaces.
In Proc. 32nd Symp. on Found. Comput. Sci., pages 207-215, 1991.

Stefan Meiser.
Point location in arrangements of hyperplanes.
Information and Computation, 106(2):286-303, 1993.

Nimrod Megiddo and Uri Shaft.
Efficient nearest neighbor indexing based on a collection of space filling curves.
Technical Report IBM Research Report RJ 10093 (91909), IBM Almaden Research Center, San Jose California, 1997.

Ketan Mulmuley.
Randomized multidimensional search trees: Further results in dynamic sampling (extended abstract).
In Proc. 32nd Symp. on Found. Comput. Sci., pages 216-227, 1991.

Hanan Samet.
The Design and Analysis of Spatial Data Structures.
Addison-Wesley, Reading, Ma, 1989.

Jeffrey K. Uhlmann.
Satisfying general proximity/similarity queries with metric trees.
Information Processing Letters, 40(4):175-179, 1991.

Peter Yianilos.
Data structures and algorithms for nearest neighbor search in general metric spaces.
In Proc. 4th ACM Symp. on Discrete Algorithms, pages 311-321, 1993.

Andrew Yao and Frances Yao.
A general approach to d-dimensional geometric queries.
In Proc. 17th ACM Symp. Theory Comput., pages 163-168, 1985.

Index Sixth DIMACS Implementation Challenge.

Index Previous DIMACS Implementation Challenges.

Index DIMACS Home Page.

Maintained by Michael Goldwasser
Document last modified on January 16, 1998.