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

Update: this page is frozen. Please visit the successor page by Arnoldo Muller


Implementations:

• Simmachines.com — startup developing similarity search solutions.
• Nearest neighbors algorithms for Amazon EC2, also check research work it is based on.
• Metric Spaces Library: An open-source C-based library for metric space indexing.
• Nearest neighbor searching in metric spaces - Experimental results and demo by Ken Clarkson.
• Implementation of LSH method by Alex Andoni.
• The homepage of M-tree.
• C++ library by Daniel Lemire.
• Spatial Index Demos from University of Maryland.
• BoostMap method: project description, implementation and dataset.
• ANN: A Library for Approximate Nearest Neighbor Searching by David M. Mount and Sunil Arya
• Arboretum + MAMViewer: an open library of metric access methods + a visual tool to explore and analyze metric access methods and similarity queries. By Fabio J. T. Chino, Marcos R. Vieira, Agma J. M. Traina and Caetano Traina Jr.
• Cover Tree for Nearest Neighbor calculations by Alina Beygelzimer, Sham Kakade, and John Langford.
• Nearest Neighbor Applet
• Metric Similarity Search Implementation Framework
• K Nearest Neighbors Linear Scan Baseline by Georges Quénot.
• Princeton Content-Aware Search Systems project including Corel-Princeton Image Similarity Benchmark.
• Nearest-Neighbor Machine Learning Bakeoff project by Michael J. Radwin.
• SAPIR project
• Music IR project at TU Wien
• Nearest Neighbour Searching in High-Dimensional Metric Space master project by David Marchall. Some written materials available.

Datasets:

• TREC Data Collections
• Web datasets by Laboratory for Web Algorithmics (Milan).
• Web matrices by Sep Kamvar.
• BLOG06 collection from TREC.
• Blogosphere dataset from ICWSM.
• Blogosphere dataset from Webblogging Ecosystems.
• Time series datasets collected by Eamonn Keogh.

Related meetings:

• International Workshop on Similarity Search and Applications
• 2006 Nearest Neighbors Workshop and 2007 Nearest Neighbors Workshop
• Workshop Approximate Nearest Neighbors Methods for Learning and Vision, satellite of NIPS'03.
• International Workshop on Similarity Search (IWOSS'99).

Related materials:

• Wikipedia articles about NN search, NN-based classification, near-duplicate algorithms, content-based image retrieval, locality sensitive hashing, nearest neighbor interpolation, curse of dimensionality, Voronoi diagram. Also Nearest Neighbor Problem article at Mathworld and K Nearest Neighbor article in Scholarpedia.
• MIT book about nearest neighbors.
• The homepage of Similarity Search book.
• The flyer of "Foundations of Multidimensional and Metric Data Structures" book by Hanan Samet. Table of contents and Amazon page for the book.

Other pointers:

• Bibliography on NN-based classification from visionbib.com
• Nearest Neighbors and Voronoi Diagrams link collection.
• KNN links collection
• Links to implementations
• References on Similarity-based Time Series Retrieval.