PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors

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

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer 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.
Titel27th Annual European Symposium on Algorithms (ESA 2019)
Antal sider16
ForlagSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
ISBN (Elektronisk)978-3-95977-124-5
StatusUdgivet - 2019


Dyk ned i forskningsemnerne om 'PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors'. Sammen danner de et unikt fingeraftryk.