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


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:

1. Write a survey on lower bounds for nearest neighbors. Reference: scribe notes Lower Bounds for Data Structures (2006) by Mihai Patrascu and Mikkel Thorup
2. Apply machine learning approach to nearest neighbors problem.
3. 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.
4. 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.
5. 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.
6. New data models. Introduce data representation format related to social netwotks and recomendation systems. Reference: A Guide to Web Research by Yury Lifshits.
7. Comparative experiments. Introduce unique data sets accepted by the whole community for verifying all NN solutions.
8. [Organizational] Announce list of major open problems in the area.