License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.10
URN: urn:nbn:de:0030-drops-111317
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11131/
Go to the corresponding LIPIcs Volume Portal

Aumüller, Martin ; Christiani, Tobias ; Pagh, Rasmus ; Vesterli, Michael

PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors

pdf-format:
LIPIcs-ESA-2019-10.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{aumller_et_al:LIPIcs:2019:11131,
  author =	{Martin Aum{\"u}ller and Tobias Christiani and Rasmus Pagh and Michael Vesterli},
  title =	{{PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11131},
  URN =		{urn:nbn:de:0030-drops-111317},
  doi =		{10.4230/LIPIcs.ESA.2019.10},
  annote =	{Keywords: Nearest Neighbor Search, Locality-Sensitive Hashing, Adaptive Similarity Search}
}

Keywords: Nearest Neighbor Search, Locality-Sensitive Hashing, Adaptive Similarity Search
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019
Supplementary Material: https://github.com/puffinn/esa-paper

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI