Approximate nearest neighbor queries revisited

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate nearest neighbor queries revisited

Full text

Pdf (1.03 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 352 - 358

Year of Publication: 1997

ISBN:0-89791-878-9

Author

Timothy M. Chan

Dept. of Math. and Computer Science, University of Miami, Coral Gables, FL

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 28, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.263001 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
	2	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
	3	Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
	4	Sunil Arya , David M. Mount, Approximate range searching, Proceedings of the eleventh annual symposium on Computational geometry, p.172-181, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220298]
	5	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	6	S. Arya, D. M. Mount, and O. Naraya#. Accounting for boundary effects in nearest neighbor searching. Discrete Comput. Geom., 16:155-176, 1996.
	7	Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
	8	Paul B. Callahan , S. Rao Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.291-300, January 25-27, 1993, Austin, Texas, United States
	9	Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
	10	Kenneth L. Clarkson, An algorithm for approximate closest-point queries, Proceedings of the tenth annual symposium on Computational geometry, p.160-164, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177609]
	11	Sanjiv Kapoor , Michiel Smid, New Techniques for Exact and Approximate Dynamic Closest-point, SIAM Journal on Computing, v.25 n.4, p.775-798, Aug. 1996 [doi>10.1137/S0097539793259458]
	12	J. Matou#ek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Cornput. Geom., 10:215- 232, 1993.
	13	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	14	Jeffrey S. Salowe, Construction of multidimensional spanner graphs, with applications to minimum spanning trees, Proceedings of the seventh annual symposium on Computational geometry, p.256-261, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109677]
	15	Pravin M. Vaidya, A sparse graph almost as good as the complete graph on points in K dimensions, Discrete & Computational Geometry, v.6 n.4, p.369-381, 1991 [doi>10.1007/BF02574695]
	16	A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11:721-736, 1982.

CITED BY 10

	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998
	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States
	Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.305-311, May 01-04, 1999, Atlanta, Georgia, United States
	Sunil Arya , Ho-Yam Addy Fu, Expected-case complexity of approximate nearest neighbor searching, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.379-388, January 09-11, 2000, San Francisco, California, United States
	Ding Liu, A strong lower bound for approximate nearest neighbor searching, Information Processing Letters, v.92 n.1, p.23-29, 16 October 2004
	Fabrizio Angiulli , Clara Pizzuti, An approximate algorithm for top-k closest pairs join query in large high dimensional data, Data & Knowledge Engineering, v.53 n.3, p.263-281, June 2005
	Fabrizio Angiulli , Clara Pizzuti, Outlier Mining in Large High-Dimensional Data Sets, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.203-215, February 2005
	Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States
	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999