PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors

Tobias Lybecker Christiani, Rasmus Pagh, Martin Aumüller, Michael Erik Vesterli

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


We present PUFFINN, a parameterless LSH-based index for solving the $k$-nearest neighbor problem with probabilistic guarantees. By parameterless we mean that the user is only required to specify the amount of memory the index is supposed to use and the result quality that should be achieved. The index combines several heuristic ideas known in the literature. By small adaptions to the query algorithm, we make heuristics rigorous. We perform experiments on real-world and synthetic inputs to evaluate implementation choices and show that the implementation satisfies the quality guarantees while being competitive with other state-of-the-art approaches to nearest neighbor search.
We describe a novel synthetic data set that is difficult to solve for almost all existing nearest neighbor search approaches, and for which PUFFINN significantly outperform previous methods.
Original languageEnglish
Title of host publication27th Annual European Symposium on Algorithms (ESA 2019)
Number of pages16
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publication date2019
Article number10
ISBN (Electronic)978-3-95977-124-5
Publication statusPublished - 2019


  • k-nearest neighbor search
  • Locality-sensitive hashing
  • Parameterless indexing
  • Probabilistic guarantees
  • Heuristic algorithms


Dive into the research topics of 'PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors'. Together they form a unique fingerprint.

Cite this