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

Intro     Bibliography     Researchers     Links     Maintainer's corner

Papers by Yury Lifshits related to nearest neighbors:
And teaching materials:
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.