Dynamic Data Structures for k-Nearest Neighbor Queries

Authors Sarita de Berg, Frank Staals



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.14.pdf
  • Filesize: 0.8 MB
  • 14 pages

Document Identifiers

Author Details

Sarita de Berg
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Frank Staals
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands

Cite AsGet BibTex

Sarita de Berg and Frank Staals. Dynamic Data Structures for k-Nearest Neighbor Queries. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.14

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • data structure
  • simple polygon
  • geodesic distance
  • nearest neighbor searching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Peyman Afshani and Timothy M. Chan. Optimal halfspace range reporting in three dimensions. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 180-186. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496791.
  2. Pankaj K. Agarwal, Lars Arge, and Frank Staals. Improved dynamic geodesic nearest neighbor searching in a simple polygon. In 34th International Symposium on Computational Geometry, SoCG, volume 99 of LIPIcs, pages 4:1-4:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.4.
  3. Pankaj K. Agarwal and Jirí Matousek. Dynamic half-space range reporting and its applications. Algorithmica, 13(4):325-345, 1995. URL: https://doi.org/10.1007/BF01293483.
  4. Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1):117-122, 2008. URL: https://doi.org/10.1145/1327452.1327494.
  5. Timothy M. Chan. Random sampling, halfspace range reporting, and construction of ≤ k-levels in three dimensions. SIAM J. Comput., 30(2):561-575, 2000. URL: https://doi.org/10.1137/S0097539798349188.
  6. Timothy M. Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. ACM, 57(3):16:1-16:15, 2010. URL: https://doi.org/10.1145/1706591.1706596.
  7. Timothy M. Chan. Three problems about dynamic convex hulls. Int. J. Comput. Geom. Appl., 22(4):341-364, 2012. URL: https://doi.org/10.1142/S0218195912600096.
  8. Timothy M. Chan. Dynamic geometric data structures via shallow cuttings. In 35th International Symposium on Computational Geometry, SoCG, volume 129 of LIPIcs, pages 24:1-24:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.24.
  9. Timothy M. Chan. personal communication, 2021. Google Scholar
  10. Timothy M. Chan and Konstantinos Tsakalidis. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discret. Comput. Geom., 56(4):866-881, 2016. URL: https://doi.org/10.1007/s00454-016-9784-4.
  11. Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1):21-27, 1967. Google Scholar
  12. Sarita de Berg and Frank Staals. Dynamic data structures for k-nearest neighbor queries, 2021. URL: http://arxiv.org/abs/2109.11854.
  13. Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Inf. Comput., 104(2):197-214, 1993. URL: https://doi.org/10.1006/inco.1993.1030.
  14. Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1):209-233, 1987. Google Scholar
  15. Leonidas J. Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126-152, 1989. URL: https://doi.org/10.1016/0022-0000(89)90041-X.
  16. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar voronoi diagrams for general distance functions and their algorithmic applications. Discret. Comput. Geom., 64(3):838-904, 2020. URL: https://doi.org/10.1007/s00454-020-00243-7.
  17. Rolf Klein and Andrzej Lingas. Hamiltonian abstract voronoi diagrams in linear time. In Algorithms and Computation, 5th International Symposium, ISAAC, Proceedings, volume 834 of Lecture Notes in Computer Science, pages 11-19. Springer, 1994. URL: https://doi.org/10.1007/3-540-58325-4_161.
  18. Der-Tsai Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE Transactions on Computers, C-31(6):478-487, 1982. Google Scholar
  19. Chih-Hung Liu. Nearly optimal planar k nearest neighbors queries under general distance functions. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2842-2859. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.173.
  20. Chih-Hung Liu and D. T. Lee. Higher-order geodesic voronoi diagrams in a polygonal domain with holes. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1633-1645. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.117.
  21. Jiří Matoušek. Reporting points in halfspaces. Computational Geometry Theory and Applications, 2(3):169-186, 1992. Google Scholar
  22. Eunjin Oh and Hee-Kap Ahn. Voronoi diagrams for a moderate-sized point-set in a simple polygon. Discret. Comput. Geom., 63(2):418-454, 2020. URL: https://doi.org/10.1007/s00454-019-00063-4.
  23. Mark H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer, 1983. URL: https://doi.org/10.1007/BFb0014927.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail