Dynamic Data Structures for \(k\)-Nearest Neighbor Queries

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^2n/\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.

Corresponding Publications

Dynamic Data Structures for \(k\)-Nearest Neighbor Queries

Sarita de Berg, Frank Staals

Proc. 32th International Symposium on Algorithms and Computation, 2021

To appear.
@incollection{dynamic_knn2021,
  author = {de Berg, Sarita and Staals, Frank},
  title = {Dynamic Data Structures for $k$-Nearest Neighbor Queries},
  booktitle = {Proc. 32th International Symposium on Algorithms and Computation},
  year = {2021},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Fukuoka, Japan},
  category = {datastructures},
  note = {To appear.},
}

A Dynamic Data Structure for \(k\)-Nearest Neighbors Queries

Sarita de Berg, Frank Staals

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

@article{dynamic_knn_eurocg,
  author = {de Berg, Sarita and Staals, Frank},
  title = {A Dynamic Data Structure for $k$-Nearest Neighbors Queries},
  journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
  year = {2021},
  location = {St. Petersburg, Russia (online)},
  numpages = {7},
  category = {other},
  url = {http://eurocg21.spbu.ru/wp-content/uploads/2021/04/EuroCG_2021_paper_14.pdf},
  project = {dynamic_knn2021},
}