Two algorithms for nearest-neighbor search in high dimensions

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	Micah Adler , Peter Gemmell , Mor Harchol-Balter , Richard M. Karp , Claire Kenyon, Selection in the presence of noise: the design of playoff systems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.564-572, January 23-25, 1994, Arlington, Virginia, United States
	2	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129763]
	3	N. AIon, J. Spencer, The Probabilistic Method, Wiley, 1992.
	4	Sunil Arya, Nearest neighbor searching and applications, University of Maryland at College Park, College Park, MD, 1996
	5	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching in fixed dimensions, University of Maryland at College Park, College Park, MD, 1995
	6	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]
	7	M. W. Berry , S. T. D %A , A. T. Shippy, A Case Study of Latent Semantic Indexing, University of Tennessee, Knoxville, TN, 1995
	8	C. Buckley, A. Singhal, M. Mitra, and G. Salton, "New Retrieval Approaches Using SMART: TREC 4," Proceedings of the Fourth Text Retrieval Conference, National Institute of Standards and Technology, 1995.
	9	Paul B. Callahan , S. Rao Kosaraju, A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.546-556, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129766]
	10	Benny Chor , Madhu Sudan, A Geometric Approach to Betweenness, Proceedings of the Third Annual European Symposium on Algorithms, p.227-237, September 25-27, 1995
	11	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	12	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]
	13	Edith Cohen , David D. Lewis, Approximating matrix multiplication for pattern recognition tasks, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.682-691, January 05-07, 1997, New Orleans, Louisiana, United States
	14	T.M. Cover, P.E. Hart, "Nearest neighbor pattern classification;' IEEE Transactions on information Theory, 13(1967), pp. 21-27.
	15	S. Deerwester, S. Dumais, T. Landauer, G. Furnas, R. Harshman, "Indexing by latent semantic analysis," J. Soc. Info. Sci., 41 ( 1990), pp. 391-407.
	16	L. Devroye, T.J. Wagner, "Nearest neighbor methods in discrimination;' Handbook of Statistics, vol. 2, P.R. Krishnaiah, L.N. Kanal, eds., North-Holland, 1982.
	17	D. Dobkin, R. Lipton, "Multidimensional search problems," SIAM J. Computing, 5(1976), pp. 181-186.
	18	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	19	R.M. Dudley, "Central limit theorems for empirical measures;' Annals of Prob., 6(1978), pp. 899-929.
	20	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	21	U. Feige , D. Peleg , P. Raghavan , E. Upfal, Computing with unreliable information, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.128-137, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100230]
	22	R.A. Finkel, J.L. Bentley, "Quad trees - a data structure for retrieval on composite keys," Acta Inform. 4(1974), pp. 1-9.
	23	Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
	24	P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
	25	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	26	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]
	27	Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
	28	Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
	29	H. Hotelling, "Analysis of a complex of statistical variables into principal components," J. Educational Psychology, 27(1933), pp. 417-441.
	30	W.B. Johnson, J. Lindenstrauss, "Extensions of Lipschitz mappings into Hilbert space;' Contemporary Mathematics 26(1984), pp. 189-206.
	31	D. Karger, R. Motwani and M. Sudan, "Approximate graph coloring by semidefinite programming," Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994, pp. 2-I 3.
	32	Jiří Matoušek, Reporting points in halfspaces, Proceedings of the 32nd annual symposium on Foundations of computer science, p.207-215, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185370]
	33	S. Meiser, Point location in arrangements of hyperplanes, Information and Computation, v.106 n.2, p.286-303, Oct. 1993 [doi>10.1006/inco.1993.1057]
	34	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	35	Panel on Discriminant Analysis and Clustering, National Research Council, Discriminant Analysis and Clustering, National Academy Press, 1988.
	36	A. Pentland, R.W. Picard, and S. Sclaroff, "Photobook: tools for content-based manipulation of image databases;' Proceedings of the SPiE Conference on Storage and Retrieval of lmage and Video Databases II, 1994.
	37	C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
	38	Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	39	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	40	A.W.M. Smeulders and R. Jain, editors. Image Databases and Multi-media Search. Proceedings of the First International Workshop, IDB-MMS '96, Amsterdam. Amsterdam University Press, 1996.
	41	V.N. Vapnik, A.Y. Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities;' Theory of Prob. App., 16(1971 ), pp. 264-280.
	42	A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]