ITU

PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors

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

View graph of relations

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
Pages1-16
Article number10
ISBN (Electronic)978-3-95977-124-5
DOIs
Publication statusPublished - 2019

Downloads

No data available

ID: 84061764