Approximate nearest neighbors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate nearest neighbors: towards removing the curse of dimensionality

Full text

Pdf (1.33 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 604 - 613

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Piotr Indyk	Department of Computer Science, Stanford University, Stanford, CA
Rajeev Motwani	Department of Computer Science, Stanford University, Stanford, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 80, Downloads (12 Months): 598, Citation Count: 185

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/276698.276876 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	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]
	2	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
	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.
	4	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
	5	A. Andersson, Static Dictionaries on RAMs: Query Time is Necessary and Sufficient, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.441, October 14-16, 1996
	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	Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
	8	M. W. Berry , S. T. D %A , A. T. Shippy, A Case Study of Latent Semantic Indexing, University of Tennessee, Knoxville, TN, 1995
	9	Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
	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.
	11	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]
	12	Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
	13	F. Cazals, Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering, Proceedings of the fourteenth annual symposium on Computational geometry, p.222-230, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276910]
	14	Timothy M. Chan, Approximate nearest neighbor queries revisited, Proceedings of the thirteenth annual symposium on Computational geometry, p.352-358, June 04-06, 1997, Nice, France [doi>10.1145/262839.263001]
	15	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]
	16	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]
	17	Kenneth L. Clarkson, Nearest neighbor queries in metric spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.609-617, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258655]
	18	Scott Cost , Steven Salzberg, A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features, Machine Learning, v.10 n.1, p.57-78, Jan. 1993 [doi>10.1023/A:1022664626993]
	19	T.M. Cover and P.E. Hart, Nearest neighbor pattern classification. {EEE Transactions on Information The. ory, 13(1967):21-27.
	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.
	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.
	22	D. Dobkin and R. Lipton. Multidimensional search problems. SIAM Journal on Computing, 5(1976):181- 186.
	23	Danny Dolev , Yuval Harari , Nathan Linial , Noam Nisan , Michal Parnas, Neighborhood preserving hashing and approximate queries, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.251-259, January 23-25, 1994, Arlington, Virginia, United States
	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.
	25	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	26	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	27	David Eppstein, Fast hiearchical clustering and other applications of dynamic closet pairs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 25-27, 1998, San Francisco, California, United States
	28	C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
	29	W. Feller. An introduction to Probability Theory and its Applications. John Wiley & Sons, NY, 1991.
	30	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]
	31	William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	32	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
	33	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	34	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]
	35	Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
	36	A. Gionis, P. Indyk, and R. Motwani. Similarity Search in High Dimensions via Hashing. Manuscript, 1997.
	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.
	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.
	39	H. HoteUing. Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 27( 1933):417-441.
	40	P. Indyk, R. Motwani, and S. Venkatasubramanian. Geometric Matching Under Noise- Combinatorial Bounds and Algorithms. Manuscript, 1997.
	41	W.B. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. Contemporary Mathematics, 26(1984):189-206.
	42	W.B. Jotmson and G. Schechtman. Embedding l~~ into l{'. Acta Mathematica, 149(1982):71-85.
	43	K. Karhunen. Uber lineare Methoden in dew Wahrscheinlichkeitsrechnung. Ann. Acad. Sci. Fennicae, Set. A137, 1947.
	44	V. Koivune and S. Kassam. Nearest neighbor filters for multivariate data. IEEE l'~rkshop on Nonlinear Signal and Image Processing, 1995.
	45	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
	46	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
	47	R. M. Karp , O. Waarts , G. Zweig, The bit vector intersection problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.621, October 23-25, 1995
	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.
	49	M. Loire. Fonctions aleastoires de second ordere. Processus Stochastiques et mouvcment Brownian, Hermann, Paris, 1948.
	50	Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
	51	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]
	52	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	53	M. Minsky and S. Papert. Perceptrona. MIT Prcs~, Cambridge, MA, 1969.
	54	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	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.
	56	G. Pisier. The volume of convex bodies and Banach space geometry. Cambridge Universit4' Press, 1989.
	57	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	58	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	59	Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, Multidimensional Access Methods: Trees Have Grown Everywhere, Proceedings of the 23rd International Conference on Very Large Data Bases, p.13-14, August 25-29, 1997
	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.
	61	J.K. Uhlm~. Satisfying General Pro.,dmity/Similarit.y Queries with Metric Trees. Information ProccaMng Letters, 40(1991):175-179.
	62	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
	63	T. A. Welch, BOUNDS ON INFORMATION RETRIEVAL EFFICIENCY IN STATIC FILE STRUCTURES., Massachusetts Institute of Technology, Cambridge, MA, 1971
	64	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]

CITED BY 185

	Ashish Goel , Piotr Indyk , Kasturi Varadarajan, Reductions among high dimensional proximity problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.769-778, January 07-09, 2001, Washington, D.C., United States
	F. Cazals, Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering, Proceedings of the fourteenth annual symposium on Computational geometry, p.222-230, June 07-10, 1998, Minneapolis, Minnesota, United States
	Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, ACM SIGMOD Record, v.29 n.2, p.70-81, June 2000
	Sariel Har-Peled , Piotr Indyk, When crossings count — approximating the minimum spanning tree, Proceedings of the sixteenth annual symposium on Computational geometry, p.166-175, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Helmut Alt, The nearest neighbor, Computational Discrete Mathematics: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2001
	D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Robert Krauthgamer , Ori Sasson, Property testing of data dimensionality, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Piotr Indyk, Approximate nearest neighbor algorithms for Frechet distance via product metrics, Proceedings of the eighteenth annual symposium on Computational geometry, p.102-106, June 05-07, 2002, Barcelona, Spain
	Anupam Gupta, Embedding tree metrics into low dimensional Euclidean spaces, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.694-700, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
	Aristides Gionis , Dimitrios Gunopulos , Nick Koudas, Efficient and tumble similar set retrieval, ACM SIGMOD Record, v.30 n.2, p.247-258, June 2001
	Rafail Ostrovsky , Yuval Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM (JACM), v.49 n.2, p.139-156, March 2002
	Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.305-311, May 01-04, 1999, Atlanta, Georgia, United States
	Ella Bingham , Heikki Mannila, Random projection in dimensionality reduction: applications to image and text data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.245-250, August 26-29, 2001, San Francisco, California
	Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Kristin P. Bennett , Usama Fayyad , Dan Geiger, Density-based indexing for approximate nearest-neighbor queries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.233-243, August 15-18, 1999, San Diego, California, United States
	H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States
	Dimitrios Gunopulos , Gautam Das, Time series similarity measures (tutorial PM-2), Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.243-307, August 20-23, 2000, Boston, Massachusetts, United States
	Jeremy Buhler , Martin Tompa, Finding motifs using random projections, Proceedings of the fifth annual international conference on Computational biology, p.69-76, April 22-25, 2001, Montreal, Quebec, Canada
	Jian Zhang , Joan Feigenbaum, Finding highly correlated pairs efficiently with powerful pruning, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Omer Barkol , Yuval Rabani, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Journal of Computer and System Sciences, v.64 n.4, p.873-896, June 2002
	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
	S. Muthukrishnan , Süleyman Cenk Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.416-424, May 21-23, 2000, Portland, Oregon, United States
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Subquadratic approximation algorithms for clustering problems in high dimensional spaces, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.435-444, May 01-04, 1999, Atlanta, Georgia, United States
	Graham Cormode , Mike Paterson , Süleyman Cenk Sahinalp , Uzi Vishkin, Communication complexity of document exchange, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.197-206, January 09-11, 2000, San Francisco, California, United States
	Cheng Yang, Efficient acoustic index for music retrieval with various degrees of similarity, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France
	Ali Saman Tosun , Hakan Ferhatosmanoglu, Vulnerabilities in similarity search based systems, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	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
	Changzhou Wang , Xiaoyang Sean Wang, High-dimensional nearest neighbor search with remote data centers, Knowledge and Information Systems, v.4 n.4, p.440-465, October 2002
	Dimitris Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, v.66 n.4, p.671-687, 1 June 2003
	Piotr Indyk, Better algorithms for high-dimensional proximity problems via asymmetric embeddings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Belur V. Dasarathy, Data mining tasks and methods: Classification: nearest-neighbor approaches, Handbook of data mining and knowledge discovery, Oxford University Press, Inc., New York, NY, 2002
	T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Surajit Chaudhuri , Kris Ganjam , Venkatesh Ganti , Rajeev Motwani, Robust and efficient fuzzy match for online data cleaning, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Alistair Morrison , Greg Ross , Matthew Chalmers, Fast multidimensional scaling through sampling, springs and interpolation, Information Visualization, v.2 n.1, p.68-77, March 2003
	Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Guang-Ho Cha, Bitmap indexing method for complex similarity queries with relevance feedback, Proceedings of the 1st ACM international workshop on Multimedia databases, November 07-07, 2003, New Orleans, LA, USA
	C. C. Aggarwal , P. S. Yu, Redefining Clustering for High-Dimensional Applications, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.210-225, March 2002
	Alistair Morrison , Greg Ross , Matthew Chalmers, A Hybrid Layout Algorithm for Sub-Quadratic Multidimensional Scaling, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.152, October 28-29, 2002
	Sanjoy Dasgupta , Anupam Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures & Algorithms, v.22 n.1, p.60-65, January 2003
	Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Dmitriy Fradkin , David Madigan, Experiments with random projections for machine learning, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Michael E. Houle, Navigating massive data sets via local clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Helmut Alt , Laura Heinrich-Litan, Exact L_∞ nearest neighbor search in high dimensions, Proceedings of the seventeenth annual symposium on Computational geometry, p.157-163, June 2001, Medford, Massachusetts, United States
	Sunil Arya , Ho-Yam Addy Fu, Expected-case complexity of approximate nearest neighbor searching, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.379-388, January 09-11, 2000, San Francisco, California, United States
	Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
	Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States
	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States
	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States
	Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January 2003
	Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	Jie Gao , Leonidas J. Guibas , An Nguyen, Deformable spanners and applications, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	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
	Anna C. Gilbert , S. Muthukrishnan , Martin J. Strauss, Approximation of functions over redundant dictionaries using coherence, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Piotr Indyk, Approximate Nearest Neighbor under edit distance via product metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Sid-Ahmed Berrani , Laurent Amsaleg , Patrick Gros, Robust content-based image searches for copyright protection, Proceedings of the 1st ACM international workshop on Multimedia databases, November 07-07, 2003, New Orleans, LA, USA
	Yan Ke , Rahul Sukthankar , Larry Huston, An efficient parts-based near-duplicate and sub-image retrieval system, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces, Machine Learning, v.56 n.1-3, p.153-167
	Benjamin Raphael , Lung-Tien Liu , George Varghese, A Uniform Projection Method for Motif Discovery in DNA Sequences, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.2, p.91-94, April 2004
	Richard Cole , Lee-Ad Gottlieb , Moshe Lewenstein, Dictionary matching and indexing with errors and don't cares, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ding Liu, A strong lower bound for approximate nearest neighbor searching, Information Processing Letters, v.92 n.1, p.23-29, 16 October 2004
	Charu C. Aggarwal, An Efficient Subspace Sampling Framework for High-Dimensional Data Reduction, Selectivity Estimation, and Nearest-Neighbor Search, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1247-1262, October 2004
	Alistair Morrison , Matthew Chalmers, A pivot-based routine for improved parent-finding in hybrid MDS, Information Visualization, v.3 n.2, p.109-122, June 2004
	Qin Lv , Moses Charikar , Kai Li, Image similarity search with compact data structures, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Sanjoy Dasgupta , Wee Sun Lee , Philip M. Long, A Theoretical Analysis of Query Selection for Collaborative Filtering, Machine Learning, v.51 n.3, p.283-298, June 2003
	Rakesh Agrawal , Ramakrishnan Srikant, Searching with numbers, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA
	Gísli R. Hjaltason , Hanan Samet, Properties of Embedding Methods for Similarity Searching in Metric Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.530-549, May 2003
	Jeremy Buhler, Provably sensitive Indexing strategies for biosequence similarity search, Proceedings of the sixth annual international conference on Computational biology, p.90-99, April 18-21, 2002, Washington, DC, USA
	Edith Cohen , Mayur Datar , Shinji Fujiwara , Aristides Gionis , Piotr Indyk , Rajeev Motwani , Jeffrey D. Ullman , Cheng Yang, Finding Interesting Associations without Support Pruning, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.64-78, January 2001
	Chen Li , Edward Chang , Hector Garcia-Molina , Gio Wiederhold, Clustering for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.792-808, July 2002
	Sergey Bereg , Michael Segal, Dynamic algorithms for approximating interdistances, Nordic Journal of Computing, v.11 n.4, p.344-355, December 2004
	Boris Aronov , Sariel Har-Peled, On approximating the depth and related problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Bin Cui , Heng Tao Shen , Jialie Shen , Kian-Lee Tan, Exploring bit-difference for approximate KNN search in high-dimensional databases, Proceedings of the sixteenth Australasian database conference, p.165-174, January 01, 2005, Newcastle, Australia
	Christos Papadimitriou , Shmuel Safra, The complexity of low-distortion embeddings between point sets, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Mayank Bawa , Tyson Condie , Prasanna Ganesan, LSH forest: self-tuning indexes for similarity search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Cheng Yang, Peer-to-peer architecture for content-based music retrieval on acoustic data, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
	Rina Panigrahy, Entropy based nearest neighbor search in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1186-1195, January 22-26, 2006, Miami, Florida
	Bo Brinkman , Moses Charikar, On the impossibility of dimension reduction in l₁, Journal of the ACM (JACM), v.52 n.5, p.766-788, September 2005
	Arun Qamra , Yan Meng , Edward Y. Chang, Enhanced Perceptual Distance Functions and Indexing for Image Replica Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.379-391, March 2005
	Greg Mori , Serge Belongie , Jitendra Malik, Efficient Shape Matching Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.11, p.1832-1837, November 2005
	Leslie Ikemoto , Okan Arikan , David Forsyth, Knowing when to put your foot down, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California
	T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Journal of Computer and System Sciences, v.69 n.3, p.435-447, November 2004
	Alexandr Andoni , Piotr Indyk, Efficient algorithms for substring near neighbor problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1203-1212, January 22-26, 2006, Miami, Florida
	Robert Krauthgamer , James R. Lee, The black-box complexity of nearest-neighbor search, Theoretical Computer Science, v.348 n.2, p.262-276, 8 December 2005
	Ping Li , Trevor J. Hastie , Kenneth W. Church, Very sparse random projections, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Matthew L. Miller , Manuel Acevedo Rodriguez , Ingemar J. Cox, Audio Fingerprinting: Nearest Neighbor Search in High Dimensional Binary Spaces, Journal of VLSI Signal Processing Systems, v.41 n.3, p.285-291, November 2005
	Jie Gao , Leonidas J. Guibas , An Nguyen, Deformable spanners and applications, Computational Geometry: Theory and Applications, v.35 n.1, p.2-19, August 2006
	Sunil Arya , Theocharis Malamatos , David M. Mount, Space-efficient approximate Voronoi diagrams, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Vincent C. H. Ma , Michael D. McCool, Low latency photon mapping using block hashing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
	Sunil Arya , Theocharis Malamatos, Linear-size approximate voronoi diagrams, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.147-155, January 06-08, 2002, San Francisco, California
	Amitabha Bagchi , Ankur Bhargava , Torsten Suel, Approximate maximum weight branchings, Information Processing Letters, v.99 n.2, p.54-58, 31 July 2006
	Rosa I. Arriaga , Santosh Vempala, An algorithmic theory of learning: Robust concepts and random projection, Machine Learning, v.63 n.2, p.161-182, May 2006
	A. M. Sokolov, Vector representations for efficient comparison and search for similar strings, Cybernetics and Systems Analysis, v.43 n.4, p.484-498, July 2007
	Martin Theobald , Jonathan Siddharth , Andreas Paepcke, SpotSigs: robust and efficient near duplicate detection in large web collections, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore
	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
	Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States
	Omer Barkol , Yuval Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.388-396, May 21-23, 2000, Portland, Oregon, United States
	Vladimir Pestov , Aleksandar Stojmirović, Indexing schemes for similarity search: an illustrated paradigm, Fundamenta Informaticae, v.70 n.4, p.367-385, April 2006
	Yogish Sabharwal , Nishant Sharma , Sandeep Sen, Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions, Journal of Computer and System Sciences, v.72 n.6, p.955-977, September 2006
	Maria-Florina Balcan , Avrim Blum , Santosh Vempala, Kernels as features: On kernels, margins, and low-dimensional mappings, Machine Learning, v.65 n.1, p.79-94, October 2006
	Rajeev Motwani , Assaf Naor , Rina Panigrahi, Lower bounds on locality sensitive hashing, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Qin Lv , William Josephson , Zhe Wang , Moses Charikar , Kai Li, Efficient filtering with sketches in the ferret toolkit, Proceedings of the 8th ACM international workshop on Multimedia information retrieval, October 26-27, 2006, Santa Barbara, California, USA
	Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006
	José J. Amador, Random projection and orthonormality for lossy image compression, Image and Vision Computing, v.25 n.5, p.754-766, May, 2007
	Navneet Panda , Edward Y. Chang, Efficient top-k hyperplane query processing for multimedia information retrieval, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
	Sreenivas Gollapudi , Rina Panigrahy, A dictionary for approximate string search and longest prefix search, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	James Gorman , James R. Curran, Scaling distributional similarity to large corpora, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.361-368, July 17-18, 2006, Sydney, Australia
	Deepak Ravichandran , Patrick Pantel , Eduard Hovy, Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.622-629, June 25-30, 2005, Ann Arbor, Michigan
	Qin Lv , William Josephson , Zhe Wang , Moses Charikar , Kai Li, Ferret: a toolkit for content-based similarity search of feature-rich data, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
	Roberto J. Bayardo , Yiming Ma , Ramakrishnan Srikant, Scaling up all pairs similarity search, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Pankaj K. Agarwal , Sariel Har-Peled , Hai Yu, Embeddings of surfaces, curves, and moving points in euclidean space, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Pavan Kumar C. Singitham , Mahathi S. Mahabhashyam , Prabhakar Raghavan, Efficiency-quality tradeoffs for vector score aggregation, Proceedings of the Thirtieth international conference on Very large data bases, p.624-635, August 31-September 03, 2004, Toronto, Canada
	Nick Koudas , Beng Chin Ooi , Kian-Lee Tan , Rui Zhang, Approximate NN queries on streams with guaranteed error/performance bounds, Proceedings of the Thirtieth international conference on Very large data bases, p.804-815, August 31-September 03, 2004, Toronto, Canada
	Zhe Wang , Wei Dong , William Josephson , Qin Lv , Moses Charikar , Kai Li, Sizing sketches: a rank-based analysis for similarity search, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
	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
	Abhinandan S. Das , Mayur Datar , Ashutosh Garg , Shyam Rajaram, Google news personalization: scalable online collaborative filtering, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Yingwu Zhu , Yiming Hu, Efficient semantic search on DHT overlays, Journal of Parallel and Distributed Computing, v.67 n.5, p.604-616, May, 2007
	Jun Jie Foo , Ranjan Sinha, Pruning SIFT for scalable near-duplicate image matching, Proceedings of the eighteenth conference on Australasian database, p.63-71, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Toshiya Hachisuka , Wojciech Jarosz , Richard Peter Weistroffer , Kevin Dale , Greg Humphreys , Matthias Zwicker , Henrik Wann Jensen, Multidimensional adaptive sampling and reconstruction for ray tracing, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
	Hisashi Koga , Tetsuo Ishibashi , Toshinori Watanabe, Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing, Knowledge and Information Systems, v.12 n.1, p.25-53, May 2007
	Nir Ailon , Edo Liberty, Fast dimension reduction using Rademacher series on dual BCH codes, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-9, January 20-22, 2008, San Francisco, California
	Piotr Indyk , Nick Koudas , S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Proceedings of the 26th International Conference on Very Large Data Bases, p.363-372, September 10-14, 2000
	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
	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	T-H. Hubert Chan , Anupam Gupta , Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.333-342, January 20-22, 2008, San Francisco, California
	Ping Li , Kenneth W. Church, A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations, Computational Linguistics, v.33 n.3, p.305-354, September 2007
	Qin Lv , William Josephson , Zhe Wang , Moses Charikar , Kai Li, Multi-probe LSH: efficient indexing for high-dimensional similarity search, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Ahmed M. Khedr , Ahmed Salim, Decomposable algorithms for nearest neighbor computing, Journal of Parallel and Distributed Computing, v.68 n.7, p.902-912, July, 2008
	Alexandr Andoni , Piotr Indyk , Robert Krauthgamer, Overcoming the l₁ non-embeddability barrier: algorithms for product metrics, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.865-874, January 04-06, 2009, New York, New York
	William B. Johnson , Assaf Naor, The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.885-891, January 04-06, 2009, New York, New York
	Wei Dong , Moses Charikar , Kai Li, Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore
	Sreenivas Gollapudi , Rina Panigrahy, The power of two min-hashes for similarity search among hierarchical data objects, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Yury Lifshits , Shengyu Zhang, Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.318-326, January 04-06, 2009, New York, New York
	Avrim Blum , Katrina Ligett , Aaron Roth, A learning theory approach to non-interactive database privacy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Alexandr Andoni , Piotr Indyk , Robert Krauthgamer, Earth mover distance over high-dimensional spaces, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.343-352, January 20-22, 2008, San Francisco, California
	Smriti Bhagat , Irina Rozenbaum , Graham Cormode, Applying link-based classification to label blogs, Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, p.92-101, August 12-12, 2007, San Jose, California
	Alexandr Andoni , Piotr Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Communications of the ACM, v.51 n.1, January 2008
	Piotr Indyk , Assaf Naor, Nearest-neighbor-preserving embeddings, ACM Transactions on Algorithms (TALG), v.3 n.3, p.31-es, August 2007
	Piotr Indyk , Assaf Naor, Nearest-neighbor-preserving embeddings, ACM Transactions on Algorithms (TALG), v.3 n.3, p.31-es, August 2007
	Rui Cai , Chao Zhang , Lei Zhang , Wei-Ying Ma, Scalable music recommendation by search, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany
	Bernard Chazelle , Ding Liu , Avner Magen, Approximate range searching in higher dimension, Computational Geometry: Theory and Applications, v.39 n.1, p.24-29, January, 2008
	Gregory Buehrer , Kumar Chellapilla, A scalable pattern mining approach to web graph compression with communities, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA
	Peyman Afshani , Hamed Hatami, Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, Information Processing Letters, v.105 n.3, p.83-87, January, 2008
	Chuan Xiao , Wei Wang , Xuemin Lin , Jeffrey Xu Yu, Efficient similarity joins for near duplicate detection, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Pranab Sen , S. Venkatesh, Lower bounds for predecessor searching in the cell probe model, Journal of Computer and System Sciences, v.74 n.3, p.364-385, May, 2008
	Yunyoung Nam , Eenjun Hwang , Dongyoon Kim, A similarity-based leaf image retrieval scheme: Joining shape and venation features, Computer Vision and Image Understanding, v.110 n.2, p.245-259, May, 2008
	Jun Jie Foo , Justin Zobel , Ranjan Sinha, Clustering near-duplicate images in large collections, Proceedings of the international workshop on Workshop on multimedia information retrieval, September 24-29, 2007, Augsburg, Bavaria, Germany
	Benno Stein, Principles of hash-based text retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands
	Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Journal of the ACM (JACM), v.54 n.5, p.23-es, October 2007
	Ping Li, Very sparse stable random projections for dimension reduction in lα (0 <α ≤ 2) norm, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Navin Goyal , Yury Lifshits , Hinrich Schütze, Disorder inequality: a combinatorial approach to nearest neighbor search, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA
	Tanguy Urvoy , Emmanuel Chauveau , Pascal Filoche , Thomas Lavergne, Tracking Web spam with HTML style similarities, ACM Transactions on the Web (TWEB), v.2 n.1, p.1-28, February 2008
	Ping Li, Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 20-22, 2008, San Francisco, California
	Yu-En Lu , Pietro Lió , Steven Hand, On low dimensional random projections and similarity search, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Daniel Fogaras , Balazs Racz, Practical Algorithms and Lower Bounds for Similarity Search in Massive Graphs, IEEE Transactions on Knowledge and Data Engineering, v.19 n.5, p.585-598, May 2007
	Yi Yu , J. Stephen Downie , Fabian Moerchen , Lei Chen , Kazuki Joe , Vincent Oria, COSIN: content-based retrieval system for cover songs, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada
	Filippo Geraci , Marco Pellegrini, Dynamic user-defined similarity searching in semi-structured text retrieval, Proceedings of the 3rd international conference on Scalable information systems, June 04-06, 2008, Vico Equense, Italy
	Wei Dong , Zhe Wang , William Josephson , Moses Charikar , Kai Li, Modeling LSH for performance tuning, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	Amol Ghoting , Srinivasan Parthasarathy , Matthew Eric Otey, Fast mining of distance-based outliers in high-dimensional datasets, Data Mining and Knowledge Discovery, v.16 n.3, p.349-364, June 2008
	Damien Francois , Vincent Wertz , Michel Verleysen, The Concentration of Fractional Distances, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.873-886, July 2007
	Sharon Goldberg , David Xiao , Eran Tromer , Boaz Barak , Jennifer Rexford, Path-quality monitoring in the presence of adversaries, ACM SIGMETRICS Performance Evaluation Review, v.36 n.1, June 2008
	Hong Lu , Beng Chin Ooi , Heng Tao Shen , Xiangyang Xue, Hierarchical Indexing Structure for Efficient Similarity Search in Video Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.18 n.11, p.1544-1559, November 2006
	Johan W. Tangelder , Remco C. Veltkamp, A survey of content based 3D shape retrieval methods, Multimedia Tools and Applications, v.39 n.3, p.441-471, September 2008
	Ilya Mironov , Moni Naor , Gil Segev, Sketching in adversarial environments, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Kave Eshghi , Shyamsundar Rajaram, Locality sensitive hash functions based on concomitant rank order statistics, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Eduardo Valle , Matthieu Cord , Sylvie Philipp-Foliguet, High-dimensional descriptor indexing for large multimedia databases, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
	David Gorisse , Frederic Precioso , Sylvie Philipp-Foliguet , Matthieu Cord, Summarization scheme based on near-duplicate analysis, Proceedings of the 2nd ACM TRECVid Video Summarization Workshop, p.50-54, October 31-31, 2008, Vancouver, British Columbia, Canada
	Eduardo Valle , Matthieu Cord , Sylvie Philipp-Foliguet, Fast identification of visual documents using local descriptors, Proceeding of the eighth ACM symposium on Document engineering, September 16-19, 2008, Sao Paulo, Brazil
	Geert Willems , Tinne Tuytelaars , Luc Van Gool, Spatio-temporal features for robust content-based video copy detection, Proceeding of the 1st ACM international conference on Multimedia information retrieval, October 30-31, 2008, Vancouver, British Columbia, Canada
	Wei Dong , Zhe Wang , Moses Charikar , Kai Li, Efficiently matching sets of features with random histograms, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada
	Haiying Shen, A P2P-based intelligent resource discovery mechanism in Internet-based distributed systems, Journal of Parallel and Distributed Computing, v.69 n.2, p.197-209, February, 2009
	Alexandr Andoni , Piotr Indyk , Robert Krauthgamer , Huy L. Nguyen, Approximate line nearest neighbor in high dimensions, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.293-301, January 04-06, 2009, New York, New York
	Shibin Qiu , Terran Lane , Ljubomir Buturovic, A randomized string kernel and its application to RNA interference, Proceedings of the 22nd national conference on Artificial intelligence, p.627-632, July 22-26, 2007, Vancouver, British Columbia, Canada
	Jun Yan , Ning Liu , Gang Wang , Wen Zhang , Yun Jiang , Zheng Chen, How much can behavioral targeting help online advertising?, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Yi Yu , Kazuki Joe , J. Stephen Downie, Efficient Query-by-Content Audio Retrieval by Locality Sensitive Hashing and Partial Sequence Comparison, IEICE - Transactions on Information and Systems, v.E91-D n.6, p.1730-1739, June 2008
	Sandeep Pandey , Andrei Broder , Flavio Chierichetti , Vanja Josifovski , Ravi Kumar , Sergei Vassilvitskii, Nearest-neighbor caching for content-match applications, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Flavio Chierichetti , Ravi Kumar , Sergei Vassilvitskii, Similarity caching, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Shibin Qiu , Terran Lane, A Framework for Multiple Kernel Support Vector Regression and Its Applications to siRNA Efficacy Prediction, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.6 n.2, p.190-199, April 2009
	Yufei Tao , Ke Yi , Cheng Sheng , Panos Kalnis, Quality and efficiency in high dimensional nearest neighbor search, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Andreas Sæbjørnsen , Jeremiah Willcock , Thomas Panas , Daniel Quinlan , Zhendong Su, Detecting code clones in binary executables, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA
	Qing Xu , Carl Tropper, On Determining How Many Computers to Use in Parallel VLSI Simulation, Proceedings of the 2009 ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation, p.122-128, June 22-25, 2009
	Kilian Q. Weinberger , Lawrence K. Saul, Distance Metric Learning for Large Margin Nearest Neighbor Classification, The Journal of Machine Learning Research, 10, p.207-244, June 2009
	Mathias Eitz , Kristian Hildebrand , Tamy Boubekeur , Marc Alexa, A descriptor for large scale image retrieval based on sketched feature lines, Proceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling, August 01-02, 2009, New Orleans, Louisiana