Piotr Indyk
Rajeev Motwani
- 1.P,K, Agarwal and J. Matou~ek. Ray shooting and parametric search. In: Proceedings o/the Twenty- Fourth Annual A CM Symposium on Theory of Computing, 1992, pp. 517-526. Google Scholar
Digital Library
- 2.$, Arya and D. Mount. Approximate nearest neighbor searching. In: Proceedings of the Fourth Annual A GM. SIAM Symposium on Discrete Algorithms, 1993, pp. 271-280, Google ScholarDigital Library
- 3.13, Arya, D,M, Mount, and O. Narayan, Accounting for boundary effects in nearest-neighbor searching. Discrete and Computational Geometry, 16(1996):155-176.Google ScholarDigital Library
- 4.S, Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. In: Proceedings of the Fi/th Annual A GM. SIAM Symposium on Discrete Al. gorithms, 1994, pp. 573-582. Google ScholarDigital Library
- 5.A, Andersson, P. B. Miltersen, $. Riis, M. Thorup, Static dictionaries on AC~ RAMs: Query time O( iogn! loglog n) is necessary and sufficient. In: Proceedings of the 37th Annual IEEE Symposium on Foundations o/Computer Science, 1996, pp. 441-450. Google ScholarDigital Library
- 6.J.L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the A CM, 18(m75):509-517. Google ScholarDigital Library
- 7.M. Bern. Approximate closest-point queries in high dimensions. Information Processing Letters, 45(1993):95- 99. Google ScholarDigital Library
- 8.M.W. Berry, S.T. Dumais, and A.T. Shippy. A case study of latent semantic indexing. U.T. Knoxville Technical Report; CS-95-271, January 1995. Google ScholarDigital Library
- 9.A. Broder, S. Glassman, M. Manasse, and G. Zweig. Syntactic clustering of the Web. In: Proceedings of the Sixth International F~rld F'fde l~b Conference, pp. 391-404, 1997. Google ScholarDigital Library
- 10.C. Buddey, A. Singhal, M. Mitra, and G. Salton. New Retrieval Approaches Using SMART: TREC 4. In: Pro. ceedings of the Fourth Text Retrieval Conference, National Institute of Standards and Technology, 1995.Google Scholar
- 11.W.A. Burkhard and R.M. Keller. Some approaches to Best-Match File Searching. Communications of the ACM, 16(1973):230-236. Google ScholarDigital Library
- 12.T. Bozkaya and M. Ozsoyoglu. Distance-Based Indexing for High-Dimensional Metric Spaces, In: Proceedings of the A CM SIGMOD International Conference on Management of Data (SIGMOD), 1997. Google ScholarDigital Library
- 13.F. Cazals. Effective Nearest Neighbours 13earchJng on the Hyper-Cube, with Applications to Molecular Clustering. In Proceedings of the l~th Annual A CM Symposium on Computational Geometry, 1998. Google ScholarDigital Library
- 14.T.M. Chan. Approximate Nearest Neighbor Queries Revisited. In: Proceedings of the 18th Annual A CM Symposium on Computational Geometry, 1997, pp. 352-358. Google ScholarDigital Library
- 15.K. Clarkson. A randomized algorithm for closest-point queries. SlAM Journal on Computing, 17(1988):830- 847. Google ScholarDigital Library
- 16.K. Clarkson. An algorithm for approximate closestpoint queries. In: Proceedings of the Tenth Annual ACM Symposium on Computational Geometry, 1994, pp. 160-164. Google ScholarDigital Library
- 17.K. Clarkson. Nearest Neighbor Queries in Metric Spaces. in: Proceedings of the Twenty. Ninth Annual ACM Symposium on Theory of Computing, 1997, pp. 609-617. Google ScholarDigital Library
- 18.$. Cost and S. Salzberg. A weighted nearest neighbor algorithm for learning with symbolic features. Machine Learning, 10(1993):57-67. Google ScholarDigital Library
- 19.T.M. Cover and P.E. Hart, Nearest neighbor pattern classification. {EEE Transactions on Information The. ory, 13(1967):21-27.Google Scholar
- 20.$. Deerwester, S. T. Dumais, T.K. Landaner, G.W. Furhas, and R.A. Harshman. Indexing by latent semantic analysis. Journal of the Society fo~ Information Sci. ences, 41(1990):391-407.Google Scholar
- 21.L. Devroye and T.J. Wagner, Nearest neighbor methods in discrimination. In: Handbook of Statistics, vol. 2, P.R. Krishnaiah and L.N. Kanal, eds., North-Holland, 1982.Google Scholar
- 22.D. Dobkin and R. Lipton. Multidimensional search problems. SIAM Journal on Computing, 5(1976):181- 186.Google ScholarCross Ref
- 23.D. Dolev, Y. Harari, N. Linial, N. Nisan, and M. Parhas. Neighborhood preserving hashing and approximate queries. In: Proceedings of the Fifth Annual A CM-SIAM Symposium on Discrete Algorithms, 1994, pp. 251-259. Google ScholarDigital Library
- 24.D. Dolev, Y. Harari, and M. Parnas. Finding the neighborhood of a query in a dictionary. In: Proceedings of the ~nd Israel Symposium on Theory and Computing Systems, 1993, pp. 33-42.Google ScholarCross Ref
- 25.R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. John Wiley & Sons, NY, 1973. Google ScholarDigital Library
- 26.H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, 1987. Google ScholarDigital Library
- 27.D. Eppstein, Fast hierarchical clustering and other applicatiom~ of dynamic closest pairs. In: Proceedings of the Ninth A CM-SIAM Symposium on Discrete Algo. rithms, 1998. Google ScholarDigital Library
- 28.C. Faloutso$, R. Barber, M. Fliclmer, W. Niblack, D. Petkovic, and W. Equitz. Efficient and effective querying by image content. Journal of Intelligent Information Systems, 3( 1994):231-262. Google ScholarDigital Library
- 29.W. Feller. An introduction to Probability Theory and its Applications. John Wiley & Sons, NY, 1991.Google Scholar
- 30.M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dora, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: the QBIC system. IEEE Computer, 2s(199~):ea-32. Google ScholarDigital Library
- 31.W. Frakes and R. Baeza-Yates, editors. Information Retrieval: Data Structures and Algorithms. Prentice- Hall, 1992. Google ScholarDigital Library
- 32.P. Franld and H. Maehara. The Johnson-Lindenstrauss Lemma and the Sphericity of Some Graphs. Journal of Combinatorial Theory B, 44(1988):355-362. Google ScholarDigital Library
- 33.M.L. Fredman, J. Koml6s, and E. Szemer~di. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(1984):538-544. Google ScholarDigital Library
- 34.J.K. Friedman, J.L. Bentley, and R.A. Finkel. An algorithm for finding best matches in logarithmic expected time. A CM Transactions on Mathematical Software, 3(1977):209-226. Google ScholarDigital Library
- 35.A. Gersho and R.M. Gray. Vector Quantization and Data Compression. Kluwer, 1991. Google ScholarDigital Library
- 36.A. Gionis, P. Indyk, and R. Motwani. Similarity Search in High Dimensions via Hashing. Manuscript, 1997.Google Scholar
- 37.D. Greene, M. Parnas, and F. Yao. Multi-index hashing for information retrieval. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 722-731.Google ScholarDigital Library
- 38.T. Hastie and R. Tibshirani. Discriminant adaptive nearest neighbor classification. In: First InternaSonal Conference on Knowledge Discovery f.4 Data Mining, 1995, pp. 142-149.Google Scholar
- 39.H. HoteUing. Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 27( 1933):417-441.Google ScholarCross Ref
- 40.P. Indyk, R. Motwani, and S. Venkatasubramanian. Geometric Matching Under Noise- Combinatorial Bounds and Algorithms. Manuscript, 1997.Google Scholar
- 41.W.B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. Contemporary Mathematics, 26(1984):189-206.Google ScholarCross Ref
- 42.W.B. Jotmson and G. Schechtman. Embedding l~~ into l{'. Acta Mathematica, 149(1982):71-85.Google Scholar
- 43.K. Karhunen. Uber lineare Methoden in dew Wahrscheinlichkeitsrechnung. Ann. Acad. Sci. Fennicae, Set. A137, 1947.Google Scholar
- 44.V. Koivune and S. Kassam. Nearest neighbor filters for multivariate data. IEEE l'~rkshop on Nonlinear Signal and Image Processing, 1995.Google Scholar
- 45.J. Kleinberg. Two Algorithms for Nearest-Neighbor Search in High Dimensions. In: Proceeding.~ of the Twenty. Ninth Annual A CM Symposium on Theory of Computing, 1997. Google ScholarDigital Library
- 46.E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. These proceedings. Google ScholarDigital Library
- 47.R.M. Karp, O. Waarts, and G. Zweig. The bit. vector intersection problem. In: Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, pp. 621-630. Google ScholarDigital Library
- 48.N. Linial, E. London, and Y. Rabinovich. The geomctry of graphs and some of its algorithmic appllcation~. In: Proceedings of 85th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 577-591.Google ScholarDigital Library
- 49.M. Loire. Fonctions aleastoires de second ordere. Processus Stochastiques et mouvcment Brownian, Hermann, Paris, 1948.Google Scholar
- 50.J. Matou~ek. Reporting points in halfspacc~. In: Computational Geometry: Theory and Applications, 2(1992):169-186. Google ScholarDigital Library
- 51.S. Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106( 1993):236-- 303. Google ScholarDigital Library
- 52.N. Megiddo. Applying parallel computation algorlthm~ in the design of serial algorithms. Journal of the A CM al(1983), pp. $52-865. Google ScholarDigital Library
- 53.M. Minsky and S. Papert. Perceptrona. MIT Prcs~, Cambridge, MA, 1969.Google Scholar
- 54.R. Mot~wani and P. Raghavan. Randomized Aigorithma. Cambridge University Press, 1995. Google ScholarDigital Library
- 55.A. Pentland, R.W. Picard, and S. Sdaroff. Photobook: tools for content-based manipulation of image databases. In Proceedings of the SPiE Confercncc on Storage and Retrieval of Image and Vidco Databases II, 1994.Google ScholarCross Ref
- 56.G. Pisier. The volume of convex bodies and Banach space geometry. Cambridge Universit4' Press, 1989.Google Scholar
- 57.G. Salton and M.J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill Book Company, New York, NY, 1983. Google ScholarDigital Library
- 58.H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1989. Google ScholarDigital Library
- 59.T. SeUis, N. Roussopoulos and C. Faloutso.q. Multidimensional Access Methods: Trees Have Grown Everywhere. Proceedings of the ~3rd International Conference on Very Large Data Bases (VLDB), 1997, pp. 13-15. Google ScholarDigital Library
- 60.A.W.M. Smeulders and R. JaJn, eds. Image Databaaca and Multi-media Search. Proceedings of the First International Workshop, IDB-MIvIS '96, Amsterdam Unlversky Press, Amsterdam, 1996.Google Scholar
- 61.J.K. Uhlm~. Satisfying General Pro.,dmity/Similarit.y Queries with Metric Trees. Information ProccaMng Letters, 40(1991):175-179.Google ScholarCross Ref
- 62.P.N. YiannJlos. Data Structures and Algorithms for Nearest Neighbor Search in General Met. tic Spaces. In: Proceedings of the Second Annual A CM. SIAM Symposium on Discrete Algorithms, 1993, pp. 311-321. Google ScholarDigital Library
- 63.T. Welch. Bounds on the information retrieval efficiency of static file structures. Technical Report 88, MIT, June 1971. Google ScholarDigital Library
- 64.A.C. Yao and F.F. Yao, A general approach to ddimensional geometric queries. In: Proceedings of thc Seventeenth Annual A CM Symposium on Theory of Computing, 1985, pp. 163-168. Google ScholarDigital Library
Index Terms
- Approximate nearest neighbors: towards removing the curse of dimensionality
Recommendations
On Approximate Nearest Neighbors under l∞ Norm
The nearest neighbor search (NNS) problem is the following: Given a set of n points P={p1, , pn} in some metric space X, preprocess P so as to efficiently answer queries which require finding a point in P closest to a query point q X. The approximate ...
Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours
Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern RecognitionMany pattern recognition tasks make use of the k nearest neighbour (k-NN) technique. In this paper we are interested on fast k- NN search algorithms that can work in any metric space i.e. they are not restricted to Euclidean-like distance functions. ...
Improving Locality Sensitive Hashing by Efficiently Finding Projected Nearest Neighbors
Similarity Search and ApplicationsAbstractSimilarity search in high-dimensional spaces is an important task for many multimedia applications. Due to the notorious curse of dimensionality, approximate nearest neighbor techniques are preferred over exact searching techniques since they can ...
Comments