**The Homepage of Nearest Neighbors and Similarity Search**

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

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.