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

Abstrakt

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.
OriginalsprogEngelsk
Titel27th Annual European Symposium on Algorithms (ESA 2019)
Antal sider16
ForlagSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publikationsdato2019
Sider1-16
Artikelnummer10
ISBN (Elektronisk)978-3-95977-124-5
DOI
StatusUdgivet - 2019

Fingeraftryk

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

Citationsformater