Document Open Access Logo

Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors

Authors Boris Aronov , Matthew J. Katz

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.11.pdf
  • Filesize: 0.76 MB
  • 14 pages

Document Identifiers

Author Details

Boris Aronov
  • Department of Computer Science and Engineering, Tandon School of Engineering, New York University, Brooklyn, NY, USA
Matthew J. Katz
  • Department of Computer Science, Ben Gurion University of the Negev, Beer Sheva, Israel

Funding

Supported by Grants 2019715/CCF-20-08551 from the US-Israel Binational Science Foundation/US National Science Foundation.
  • Aronov, Boris: Supported in part by NSF grant CCF 15-40656.
  • Katz, Matthew J.: Supported in part by Grant 1884/16 from the Israel Science Foundation.

Acknowledgements

We wish to thank Pankaj K. Agarwal for his help and encouragement, and David Mount for a clarification regarding the approximating polytope in [Rahul Arya et al., 2020].

Cite AsGet BibTex

Boris Aronov and Matthew J. Katz. Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.11

Abstract

We describe a dynamic data structure for approximate nearest neighbor (ANN) queries with respect to multiplicatively weighted distances with additive offsets. Queries take polylogarithmic time, while the cost of updates is amortized polylogarithmic. The data structure requires near-linear space and construction time. The approach works not only for the Euclidean norm, but for other norms in ℝ^d, for any fixed d. We employ our ANN data structure to construct a faster dynamic structure for approximate SINR queries, ensuring polylogarithmic query and polylogarithmic amortized update for the case of non-uniform power transmitters, thus closing a gap in previous state of the art. To obtain the latter result, we needed a data structure for dynamic approximate halfplane range counting in the plane. Since we could not find such a data structure in the literature, we also show how to dynamize one of the known static data structures.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Nearest neighbors
  • Approximate nearest neighbors
  • Weighted nearest neighbors
  • Nearest neighbor queries
  • SINR queries
  • Dynamic data structures

Metrics

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

References

  1. Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Approximate nearest neighbor searching with non-Euclidean and weighted distances. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 355-372. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.23.
  2. Peyman Afshani and Timothy M. Chan. On approximate range counting and depth. Discret. Comput. Geom., 42(1):3-21, 2009. URL: https://doi.org/10.1007/s00454-009-9177-z.
  3. Alexandr Andoni and Piotr Indyk. Nearest neighbors in high-dimensional spaces. In Handbook of Discrete and Computational Geometry, pages 1135-1155. Chapman and Hall/CRC, 2017. Google Scholar
  4. Boris Aronov, Gali Bar-On, and Matthew J. Katz. Resolving SINR queries in a dynamic setting. SIAM J. Comput., 49(6):1271-1290, 2020. Google Scholar
  5. Boris Aronov and Sariel Har-Peled. On approximating the depth and related problems. SIAM J. Comput., 38(3):899-921, 2008. Google Scholar
  6. Boris Aronov and Matthew J. Katz. Batched point location in SINR diagrams via algebraic tools. ACM Transactions on Algorithms, 14(4):41:1-41:29, 2018. Google Scholar
  7. Boris Aronov and Micha Sharir. Approximate halfspace range counting. SIAM J. Comput., 39:2704-2725, 2010. Google Scholar
  8. Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal bound on the combinatorial complexity of approximating polytopes. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 786-805. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.48.
  9. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal approximate polytope membership. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 270-288. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.18.
  10. Sunil Arya, Theocharis Malamatos, and David M. Mount. Space-time tradeoffs for approximate nearest neighbor searching. J. ACM, 57(1):1:1-1:54, 2009. URL: https://doi.org/10.1145/1613676.1613677.
  11. Franz Aurenhammer and Herbert Edelsbrunner. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recogn., 17:251-257, 1984. URL: https://dx.doi.org/10.1016/0031-3203(84)90064-5.
  12. Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, and Liam Roditty. SINR diagrams: Convexity and its applications in wireless networks. J. ACM, 59(4):18:1-18:34, 2012. URL: https://doi.org/10.1145/2339123.2339125.
  13. Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 617-626. IEEE, 2002. See also [Riko Jacob and Gerth Stølting Brodal, 2019]. Google Scholar
  14. Efim M. Bronshteyn and L.D. Ivanov. The approximation of convex sets by polyhedra. Siberian Mathematical Journal, 16(5):852-853, 1975. Google Scholar
  15. Timothy M. Chan. Approximate nearest neighbor queries revisited. Discret. Comput. Geom., 20(3):359-373, 1998. URL: https://doi.org/10.1007/PL00009390.
  16. Timothy M Chan. Dynamic planar convex hull operations in near-logarithmic amortized time. Journal of the ACM (JACM), 48(1):1-12, 2001. Google Scholar
  17. Timothy M. Chan. Applications of Chebyshev polynomials to low-dimensional computational geometry. J. Comput. Geom., 9(2):3-20, 2018. URL: https://doi.org/10.20382/jocg.v9i2a2.
  18. Kenneth L. Clarkson. A randomized algorithm for closest-point queries. SIAM J. Comput., 17(4):830-847, 1988. URL: https://doi.org/10.1137/0217052.
  19. Richard M Dudley. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory, 10(3):227-236, 1974. Google Scholar
  20. Sariel Har-Peled. A replacement for Voronoi diagrams of near linear size. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 94-103. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/SFCS.2001.959884.
  21. Sariel Har-Peled and Mitchell Jones. Proof of Dudley’s convex approximation, 2019. URL: http://arxiv.org/abs/1912.01977.
  22. Sariel Har-Peled and Nirman Kumar. Approximating minimization diagrams and generalized proximity search. SIAM J. Comput., 44(4):944-974, 2015. Google Scholar
  23. Riko Jacob and Gerth Stølting Brodal. Dynamic planar convex hull, 2019. URL: http://arxiv.org/abs/1902.11169.
  24. Fritz John. Extremum problems with inequalities as subsidiary conditions. R. Courant Anniversary Volume, pages 187-204, 1948. Google Scholar
  25. Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. The topology of wireless communication. In Proceedings 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 383-392, 2011. URL: https://doi.acm.org/10.1145/1993636.1993688, URL: https://doi.org/10.1145/1993636.1993688.
  26. Sanjiv Kapoor and Michiel H. M. Smid. New techniques for exact and approximate dynamic closest-point problems. SIAM J. Comput., 25(4):775-796, 1996. URL: https://doi.org/10.1137/S0097539793259458.
  27. Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1 of EATCS Monographs on Theoretical Computer Science. Springer, 1984. URL: https://doi.org/10.1007/978-3-642-69672-5.
  28. David M. Mount. New directions in approximate nearest-neighbor searching. In Sudebkumar Prasant Pal and Ambat Vijayakumar, editors, Algorithms and Discrete Applied Mathematics - 5th International Conference, CALDAM 2019, Kharagpur, India, February 14-16, 2019, Proceedings, volume 11394 of Lecture Notes in Computer Science, pages 1-15. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11509-8_1.
  29. Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23(2):166-204, 1981. URL: https://doi.org/10.1016/0022-0000(81)90012-X.
  30. A. N. Papadopoulos and Y. Manolopoulos. Nearest Neighbor Search: A Database Perspective. Springer US, 2005. Google Scholar
  31. Theodore S. Rappaport. Wireless Communications - Principles and Practice. Prentice Hall, 1996. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact