The Homepage of Nearest Neighbors and Similarity Search
Maintained by Yury Lifshits


Algorithms for Nearest Neighbor Search
Tutorial by Yury Lifshits. RuSSIR'07, Ekaterinburg, September 2007

Comment: video in files has much better quality than on Google-Video

Slides	Handouts	TeX Sources	Video
Branch and Bound Tree-based data structures for geneal metric spaces	Slides for print	TeX	File (214 Mb), Google-Video
Other Use of Triangle Inequality Walks, matrix methods, tricks for Euclidean space	Slides for print	TeX	File (251 Mb), Google-Video
Mapping-based Techniques Locality-sensitive hashing, random projections	Slides for print	TeX	File (351 Mb), Google-Video
Restrictions on Input Intrinsic dimension, probabilistic analysis and open problems	Slides for print	TeX	File (237 Mb). Google-Video

© COPYRIGHT FREE! Slides and TeX sources including pictures are provided for reuse without any restriction. If you like, you can mention that it was taken from tutorial by Yury Lifshits from http://simsearch.yury.name/tutorial.html. But you are not obliged to do this!

Relevant reading

For lectures 1-2:

• P. Zezula, G. Amato, V. Dohnal, M. Batko, Similarity Search - The Metric Space Approach, Springer, 2006.
• E. Chavez, G. Navarro, R.A. Baeza-Yates, J.L. Marroquin, Searching in metric spaces, 2001
• G.R. Hjaltason, H. Samet, Index-driven similarity search in metric spaces, ACM Transactions on Database Systems, 2003.
• M.T. Orchard, A fast nearest-neighbor search algorithm, ICASSP'91.
• L. Mico, J. Oncina, R.C. Carrasco, An algorithm for finding nearest neighbours in constant average time with a linear space complexity, Pattern Recognition Letters, 1996.
• P. Ciaccia, M. Patella, P. Zezula, M-tree An Efficient Access Method for Similarity Search in Metric Spaces, VLDB'97.
• T. Bozkaya, M. Ozsoyoglu, Indexing large metric spaces for similarity search queries, ACM Transactions on Database Systems, 1999.
• P.N. Yianilos, Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces, SODA'93.
• S. Brin, Near neighbor search in large metric spaces, VLDB'95.
• A. Guttman, R-trees: a dynamic index structure for spatial searching, SIGMOD'84.

For lecture 3:

• P. Indyk, Nearest neighbors in high-dimensional spaces, chapter of Handbook of Discrete and Computational Geometry, 2004.
• J. Kleinberg,  Two algorithms for nearest-neighbor search in high dimensions , STOC'97.
• E. Kushilevitz, R. Ostrovsky, Y. Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, STOC'98.
• A. Gionis, P. Indyk, R. Motwani, Similarity Search in High Dimensions via Hashing, VLDB'99.
• S. Ilyinsky, M. Kuzmin, A. Melkov, I. Segalovich, An efficient method to detect duplicates of web documents with the use of inverted index, WWW'02.
• R. Fagin, R. Kumar, D. Sivakumar, Efficient Similarity Search and Classification via Rank Aggregation, SIGMOD'03.
• N. Ailon, B. Chazelle, Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform, STOC'06.
• A. Andoni, P. Indyk, Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions, FOCS'06.

For lecture 4:

• D.R. Karger, M. Ruhl, Finding nearest neighbors in growth-restricted metrics, STOC'02.
• R. Krauthgamer and J.R. Lee, Navigating nets: simple algorithms for proximity search, SODA'04.
• R. Krauthgamer and J.R. Lee, The black-box complexity of nearest-neighbor search, Theoretical Computer Science, 2005.
• K.L. Clarkson, Nearest-neighbor searching and metric space dimensions, 2006.
• N. Goyal, Y. Lifshits, H. Schütze, Disorder Inequality: A Combinatorial Approach to Nearest Neighbor Search, submitted, 2007.
• B. Hoffmann, Y. Lifshits, D. Nowotka, Maximal Intersection Queries in Randomized Graph Models, CSR'07.