ITU

PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors

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

Standard

PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors. / Christiani, Tobias Lybecker; Pagh, Rasmus; Aumüller, Martin; Vesterli, Michael Erik.

27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2019. p. 1-16 10.

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

Harvard

Christiani, TL, Pagh, R, Aumüller, M & Vesterli, ME 2019, PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors. in 27th Annual European Symposium on Algorithms (ESA 2019)., 10, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, pp. 1-16. https://doi.org/10.4230/LIPIcs.ESA.2019.10

APA

Christiani, T. L., Pagh, R., Aumüller, M., & Vesterli, M. E. (2019). PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors. In 27th Annual European Symposium on Algorithms (ESA 2019) (pp. 1-16). [10] Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. https://doi.org/10.4230/LIPIcs.ESA.2019.10

Vancouver

Christiani TL, Pagh R, Aumüller M, Vesterli ME. PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors. In 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. 2019. p. 1-16. 10 https://doi.org/10.4230/LIPIcs.ESA.2019.10

Author

Christiani, Tobias Lybecker ; Pagh, Rasmus ; Aumüller, Martin ; Vesterli, Michael Erik. / PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors. 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2019. pp. 1-16

Bibtex

@inproceedings{77b537dcc78a4073b0094a994f5ccbe0,
title = "PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors",
abstract = " 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.",
author = "Christiani, {Tobias Lybecker} and Rasmus Pagh and Martin Aum{\"u}ller and Vesterli, {Michael Erik}",
year = "2019",
doi = "10.4230/LIPIcs.ESA.2019.10",
language = "English",
pages = "1--16",
booktitle = "27th Annual European Symposium on Algorithms (ESA 2019)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH",

}

RIS

TY - GEN

T1 - PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors

AU - Christiani, Tobias Lybecker

AU - Pagh, Rasmus

AU - Aumüller, Martin

AU - Vesterli, Michael Erik

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.ESA.2019.10

DO - 10.4230/LIPIcs.ESA.2019.10

M3 - Article in proceedings

SP - 1

EP - 16

BT - 27th Annual European Symposium on Algorithms (ESA 2019)

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH

ER -

ID: 84061764