License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.14
URN: urn:nbn:de:0030-drops-154473
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15447/
Go to the corresponding LIPIcs Volume Portal

de Berg, Sarita ; Staals, Frank

Dynamic Data Structures for k-Nearest Neighbor Queries

pdf-format:
LIPIcs-ISAAC-2021-14.pdf (0.8 MB)

Abstract

Our aim is to develop dynamic data structures that support k-nearest neighbors (k-NN) queries for a set of n point sites in O(f(n) + k) time, where f(n) is some polylogarithmic function of n. The key component is a general query algorithm that allows us to find the k-NN spread over t substructures simultaneously, thus reducing a O(tk) term in the query time to O(k). Combining this technique with the logarithmic method allows us to turn any static k-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, O(log²n/log log n +k) query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic geodesic k-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only k-NN data structure. More generally, we obtain a dynamic k-NN data structure for any type of distance functions for which we can build vertical shallow cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant-complexity, algebraic distance functions.

BibTeX - Entry

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2021.14,
  author =	{de Berg, Sarita and Staals, Frank},
  title =	{{Dynamic Data Structures for k-Nearest Neighbor Queries}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15447},
  URN =		{urn:nbn:de:0030-drops-154473},
  doi =		{10.4230/LIPIcs.ISAAC.2021.14},
  annote =	{Keywords: data structure, simple polygon, geodesic distance, nearest neighbor searching}
}

Keywords: data structure, simple polygon, geodesic distance, nearest neighbor searching
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

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