Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space

Full text

Pdf (546 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 5 , Issue 2 (June 1979) table of contents

Pages: 183 - 192

Year of Publication: 1979

ISSN:0098-3500

Author

John Gerald Cleary

University of Canterbury, Christchurch 1, New Zealand

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 83, Citation Count: 16

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/355826.355832 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	ABRAMOWITZ, M, AND STEGUN, I.A. Handbook of Mathematwal Functions Appl. Math Ser. 55, Nat. Bureau Standards, Washington, D.C, 1965
	2	Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
	3	W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
	4	FINKEL, R.A, AND BENTLEY, J.L Quad treesma data structure used for associative searching. Acta Inform 4, 1 (1974), 1-9.
	5	FRIEDMAN, J H, BASKETT, F, AND SHUSTEK, L J. An algorithm for finding nearest neighbors IEEE Trans. Comput. C-24 (1975), 1000-1006.
	6	Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
	7	FUKUNAGA, K, AND NARENDRA, P.M. A branch and bound algorithm for computing k-nearest neighbors IEEE Trans. Comput C-24 (1975), 750-753.
	8	MlcmE, D. Memo functions and machine learning. Nature 281, 19 (April 1968), 306
	9	MINSKY, M., AND PAPERT, S Perceptzons. M.I.T. Press, Cambridge, Mass, 1969
	10	RIVEST, R L. On the optimality of Ehas's algorithm for performing best-match searches. Infor. marion Processing "74 North Holland Publ Co., 1974, pp. 678-681
	11	SAMPSON, J.R., AND TARTAR, J Improved memo functions with apphcahons m real time computing. INFOR 12, 2 (June 1974), 117-130.
	12	YUVAL, G. Finding near neighbors in K-dimensional space, IFPL 3, 4 (March 1975), 113-114.

CITED BY 16

	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
	Christian Böhm, A cost model for query processing in high dimensional data spaces, ACM Transactions on Database Systems (TODS), v.25 n.2, p.129-178, June 2000
	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
	Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001
	Sunil Arya , David M. Mount , Onuttom Narayan, Accounting for boundary effects in nearest neighbor searching, Proceedings of the eleventh annual symposium on Computational geometry, p.336-344, June 05-07, 1995, Vancouver, British Columbia, Canada
	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
	Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
	Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States
	Yufei Tao , Jun Zhang , Dimitris Papadias , Nikos Mamoulis, An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1169-1184, October 2004
	Francisco Azuaje , Werner Dubitzky , Norman Black , Kenny Adamson, Retrieval strategies for case-based reasoning: a categorised bibliography, The Knowledge Engineering Review, v.15 n.4, p.371-379, December 2000
	Ping Yan , Kevin W. Bowyer, A fast algorithm for ICP-based 3D shape biometrics, Computer Vision and Image Understanding, v.107 n.3, p.195-202, September, 2007
	Xiaobin Ma , Shashi Shekhar , Hui Xiong , Pusheng Zhang, Exploiting a page-level upper bound for multi-type nearest neighbor queries, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
	Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
	Mirko Zadravec , Andrej Brodnik , Markus Mannila , Merja Wanne , Borut alik, A practical approach to the 2D incremental nearest-point problem suitable for different point distributions, Pattern Recognition, v.41 n.2, p.646-653, February, 2008
	Jiann-Der Lee , Chung-Hsien Huang , Li-Chang Liu , Shin-Tseng Lee , Shih-Sen Hsieh , Shuen-Ping Wang, A Modified Soft-Shape-Context ICP Registration System of 3-D Point Data, IEICE - Transactions on Information and Systems, v.E90-D n.12, p.2087-2095, December 2007