Jon M. Kleinberg
- 1.M. Adler, P. Gemmell, M. Harchol, R.M. Karp, C. Kenyon, "Selection in the presence of noise: the design of playoff systems,' Proc. 5th ACM-SIAM SODA, 1994. Google Scholar
Digital Library
- 2.P.K. Agarwal, J. Matousek, "Ray shooting and parametric search," Proc. 24th ACM STOC, 1992. Google ScholarDigital Library
- 3.N. AIon, J. Spencer, The Probabilistic Method, Wiley, 1992.Google Scholar
- 4.S. Arya, Nearest Neighbor Searching and Applications, PhD thesis, University of Maryland technical report CS-TR-3490, June 1995. Google ScholarDigital Library
- 5.S. Arya, D. Mount, N. Netanyahu, R. Silvennan, A. Wu, "An optimal algorithm for approximate nearest neighbor searching in fixed dimensions;' Proc. 5th ACM-SIAM SODA, 1994. Extended version appears as University of Maryland technical report CS-TR-3568, December 1995. Google ScholarDigital Library
- 6.J.L. Bentley, "Multidimensional binary search trees used for associative searching," Comm. ACM, 18( 1975), pp. 509-517. Google ScholarDigital Library
- 7.M.W. Berry, S.T. Dumais, A.T. Shippy, "A case study of latent semantic indexing," U.T. Knoxville technical report CS- 95-271, January 1995. Google ScholarDigital Library
- 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.Google Scholar
- 9.P.B. Callahan, S.R. Kosaraju, "A decomposition of multidimensional point sets with applications to k-nearestneighbors and n-body potential fields," Proc. 24th ACM STOC, 1992. Google ScholarDigital Library
- 10.B. Chor, M. Sudan, "A geometric approach to betweenness," Proc. 3rd European Symposium on Algorithms, 1995. Google ScholarDigital Library
- 11.K. Clarkson, "A randomized algorithm for closest-point queries," SIAM J. Computing, 17(1988), pp. 830-847. Google ScholarDigital Library
- 12.K. Clarkson, "An algorithm for approximate closest.point queries;' Proc. lOth ACM Symp. on Computational Geometry, 1994. Google ScholarDigital Library
- 13.E. Cohen, D. Lewis, "Approximating matrix multiplication for pattern recognition tasks," Proc. 8th ACM-SIAM SODA, 1997. Google ScholarDigital Library
- 14.T.M. Cover, P.E. Hart, "Nearest neighbor pattern classification;' IEEE Transactions on information Theory, 13(1967), pp. 21-27.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 17.D. Dobkin, R. Lipton, "Multidimensional search problems," SIAM J. Computing, 5(1976), pp. 181-186.Google ScholarCross Ref
- 18.R.O. Duda, P.E. Hart, Pattern Classification and Scene Analysis, Wiley, 1973. Google ScholarDigital Library
- 19.R.M. Dudley, "Central limit theorems for empirical measures;' Annals of Prob., 6(1978), pp. 899-929.Google Scholar
- 20.H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, 1987. Google ScholarDigital Library
- 21.U. Feige, D. Peleg, P. Raghavan, E. Upfal, "Computing with unreliable information," Proc. 22nd ACM STOC, 1990. Google ScholarDigital Library
- 22.R.A. Finkel, J.L. Bentley, "Quad trees - a data structure for retrieval on composite keys," Acta Inform. 4(1974), pp. 1-9.Google ScholarDigital Library
- 23.M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, P. Yanker "Query by image and video content: the QBIC system,'' IEEE Computer 28(1995), pp. 23-32. Google ScholarDigital Library
- 24.P. Frankl, H. Maehara, "The Johnson-Lindenstrauss lemma and the sphericity of some graphs," J. Combinatorial Theory Set. B, 44(1988), pp. 355-362. Google ScholarDigital Library
- 25.M.L. Fredman, R.E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms," Journal of the ACM 34(i 987), pp. 596-615, Google ScholarDigital Library
- 26.J.K. Friedman, J.L. Bentley, R.A. Finkel, "An algorithm for finding best matches in logarithmic expected time," ACM Trans. on Math. Software, 3(1977), pp. 209-226. Google ScholarDigital Library
- 27.A. Gersho, R.M. Gray, Vector Quantization and Signal Compression, Kluwer Academic, 199 i. Google ScholarDigital Library
- 28.M. Goemans, D.P. Williamson, "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming;' Journal of the ACM, 42(1995), pp. 1115-1145. Google ScholarDigital Library
- 29.H. Hotelling, "Analysis of a complex of statistical variables into principal components," J. Educational Psychology, 27(1933), pp. 417-441.Google ScholarCross Ref
- 30.W.B. Johnson, J. Lindenstrauss, "Extensions of Lipschitz mappings into Hilbert space;' Contemporary Mathematics 26(1984), pp. 189-206.Google Scholar
- 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.Google ScholarDigital Library
- 32.J. Matousek, "Reporting points in halfspaces," Proc. 32nd IEEE FOCS, 1991. Google ScholarDigital Library
- 33.S. Meiser, "Point location in arrangements of hyperplanes," Information and Computation, 106(1993), pp. 286-303. Google ScholarDigital Library
- 34.R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995. Google ScholarDigital Library
- 35.Panel on Discriminant Analysis and Clustering, National Research Council, Discriminant Analysis and Clustering, National Academy Press, 1988.Google Scholar
- 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.Google Scholar
- 37.C.J. van Rijsbergen, Information Retrieval, Butterworths, 1979. Google ScholarDigital Library
- 38.G. Salton. Automatic Text Processing. Addison-Wesley, Reading, MA, i 989. Google ScholarDigital Library
- 39.H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1989. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 42.A.C. Yao, EF. Yao, "A general approach to d-dimensional geometric queries;' Proc. 17th ACM STOC, 1985. Google ScholarDigital Library
Index Terms
- Two algorithms for nearest-neighbor search in high dimensions
Recommendations
Entropy based nearest neighbor search in high dimensions
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithmIn this paper we study the problem of finding the approximate nearest neighbor of a query point in the high dimensional space, focusing on the Euclidean space. The earlier approaches use locality-preserving hash functions (that tend to map nearby points ...
A GPGPU Algorithm for c-Approximate r-Nearest Neighbor Search in High Dimensions
IPDPSW '13: Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD ForumNearest Neighbor search is one of the simplest and most intuitive ideas in data mining. Due to it's simplicity and diverse utility, Nearest Neighbor search is often found to be the workhorse of a variety of data mining, machine learning, and computer ...
Comments