Nearest neighbor queries in metric spaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Nearest neighbor queries in metric spaces

Full text

Pdf (1.31 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 609 - 617

Year of Publication: 1997

ISBN:0-89791-888-6

Author

Kenneth L. Clarkson

Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 40, Citation Count: 11

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/258533.258655 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.

	Bri95	Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
	Cla83	K. L. Clarkson. Fast algorithms for the all nearest neighbors problem. In Proc. 24th Annu. IEEE Sympos. Found. Comput. $ci., pages 226-232, 1983.
	Cla92	K.L. Clarkson. Randomized geometric algorithms. In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, volume 1 of Lecture Notes Series on Computing, pages 117-162. World Scientific, Singapore, 1992.
	FC96	Christos Faloutsos , Volker Gaede, Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension, Proceedings of the 22th International Conference on Very Large Data Bases, p.40-50, September 03-06, 1996
	FS82	C.D. Feustel and L. G. Shapiro. The nearest neighbor problem in an abstract metric space. Pattern Recognition Letters, 1982.
	MR86	R Motwani , P Raghavan, Deferred data structuring: Query-driven preprocessing for geometric search problems, Proceedings of the second annual symposium on Computational geometry, p.303-312, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10548]
	Mul93	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, N J, 1993.
	Uhl91	Uhlmann. Satisfying general proximity/similarity queries with metric trees. Inform. Proc. Letters, 40, 1991.
	Vai89	P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]
	Yia93	Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States

CITED BY 11

	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
	Domenico Cantone , Alfredo Ferro , Alfredo Pulvirenti , Diego Reforgiato Recupero , Dennis Shasha, Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.535-550, April 2005
	Peter N. Yianilos, Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.361-370, January 09-11, 2000, San Francisco, California, United States
	Fabian Schwarzer , Itay Lotan, Approximation of protein structure for fast similarity measures, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.267-276, April 10-14, 2003, Berlin, Germany
	Kirsten Hildrum , John Kubiatowicz , Sean Ma , Satish Rao, A note on the nearest neighbor in growth-restricted metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover's Distance as a Metric for Image Retrieval, International Journal of Computer Vision, v.40 n.2, p.99-121, Nov. 2000
	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
	Flavio Chierichetti , Alessandro Panconesi , Prabhakar Raghavan , Mauro Sozio , Alessandro Tiberi , Eli Upfal, Finding near neighbors through cluster pruning, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Jonathan Goldstein , Raghu Ramakrishnan, Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbour Searches, Proceedings of the 26th International Conference on Very Large Data Bases, p.429-440, September 10-14, 2000