Dynamic data structures for k-nearest neighbor queries

DOI10.1016/J.COMGEO.2022.101976MaRDI QIDQ6101840zbMATH OpenOpenAlexFDO

Authors Sarita de Berg, Frank Staals

Publication date 20 June 2023

Published in Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2109.11854

zbMATH Keywords

data structuregeodesic distancenearest neighbor searchingsimple polygon

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Computing methodologies and applications (68Uxx)

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 the plane 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 an $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(lo{g}^{2}n/loglogn+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 emph{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 planar $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.

Cites work

• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• An optimal algorithm for selection in a min-heap
• Dynamic half-space range reporting and its applications
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Higher-order geodesic Voronoi diagrams in a polygonal domain with holes
• scientific article; zbMATH DE number 7559224 (Why is no real title available?)
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Nearest neighbor pattern classification
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• On range searching with semialgebraic sets. II.
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Optimal halfspace range reporting in three dimensions
• Optimal shortest path queries in a simple polygon
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase(\le k)-Levels in Three Dimensions
• Reporting points in halfspaces
• The design of dynamic data structures
• Voronoi diagrams for a moderate-sized point-set in a simple polygon

Cited in

(11)

• Deferred data structure for the nearest neighbor problem
• Fixed queries array: A fast and economical data structure for proximity searching
• Sequential and MapReduce-based algorithms for constructing an in-place multidimensional quad-tree index for answering fixed-radius nearest neighbor queries
• scientific article; zbMATH DE number 1865433 (Why is no real title available?)
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Dynamic unit-disk range reporting
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Nearest neighbor searching in a dynamic simple polygon

This page was built for publication: Dynamic data structures for \(k\)-nearest neighbor queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6101840)