Maintained by Yury Lifshits
Tutorial by Yury Lifshits. RuSSIR'07, Ekaterinburg, September 2007
Comment: video in files has much better quality than on Google-Video
Branch and Bound
Tree-based data structures for geneal metric spaces
|Slides for print||TeX||File (214 Mb),
Other Use of Triangle Inequality
Walks, matrix methods, tricks for Euclidean space
|Slides for print||TeX||File (251 Mb),
Locality-sensitive hashing, random projections
|Slides for print||TeX||File (351 Mb),
Restrictions on Input
Intrinsic dimension, probabilistic analysis and open problems
|Slides for print||TeX||File (237 Mb).
© 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 readingFor 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.