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

Maintained by Yury Lifshits

**Maintainer's corner**

Papers by Yury Lifshits related to nearest neighbors:

- Disorder Inequality: A Combinatorial Approach to Nearest Neighbor Search,

with Navin Goyal and Hinrich Schütze. Submitted, 2007. - Maximal Intersection Queries in Randomized Graph Models,

with Benjamin Hoffmann and Dirk Nowotka. Accepted to CSR 2007.

Talks:

- Algorithms for Nearest Neighbors: Classic Ideas, New Ideas,

Seminar talk at University of Toronto - Algorithms for Nearest Neighbors: Background and Two Challenges,

Seminar talk at McGill University - Algorithms for Nearest Neighbors: Theoretical Aspects,

Seminar talk at Moscow State University ("Kolmogorov seminar") - Algorithms for Nearest Neighbors: State-of-the-Art,

Tech talk at Yandex LLC.

And teaching materials:

- A Guide to Web Research,

Mini-course at University of Stuttgart.

I am now collecting the most important problems and directions in the field:

Research agenda:

- Write a survey on lower bounds for nearest neighbors. Reference: scribe notes Lower Bounds for Data Structures (2006) by Mihai Patrascu and Mikkel Thorup
- Apply machine learning approach to nearest neighbors problem.
- Study dinamic version of NN: objects are inserted, deleted, their representation format is changing and sometimes even similarity function is modified with time. Reference: Learning dissimilarity approach.
- Design I/O efficient NN algorithms. I.e. take into account communication between internal and external memory. Reference: External Memory Geometric Data Structures by Lars Arge.
- New analysis techniques. In order to beat brute force algorithm we need to introduce some assumptions about input data. References: randomized input assimption, bounded dimension assumption.
- New data models. Introduce data representation format related to social netwotks and recomendation systems. Reference: A Guide to Web Research by Yury Lifshits.
- Comparative experiments. Introduce unique data sets accepted by the whole community for verifying all NN solutions.
- [Organizational] Announce list of major open problems in the area.