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.
- 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:
- 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.