article

Building an Optimal Point-Location Structure in $$O( sort (n))$$O(sort(n)) I/Os

Authors:

Yufei TaoAuthors Info & Claims

Algorithmica, Volume 81, Issue 5

Pages 1921 - 1937

https://doi.org/10.1007/s00453-018-0518-2

Published: 01 May 2019 Publication History

Abstract

We revisit the problem of constructing an external memory data structure on a planar subdivision formed by n segments to answer point location queries optimally in $$O(\log _B n)$$O(logBn) I/Os. The objective is to achieve the I/O cost of $$ sort (n) = O(\frac{n}{B} \log _{M/B} \frac{n}{B})$$sort(n)=O(nBlogM/BnB), where B is the number of words in a disk block, and M being the number of words in memory. The previous algorithms are able to achieve this either in expectation or under the tall cache assumption of $$M \ge B^2$$M?B2. We present the first algorithm that solves the problem deterministically for all values of M and B satisfying $$M \ge 2B$$M?2B.

References

[1]

Achakeev, D., Seeger, B.: Efficient bulk updates on multiversion B-trees. PVLDB 6(14), 1834---1845 (2013)

Digital Library

[2]

Afshani, P., Chan, T.M.: On approximate range counting and depth. Discrete Comput. Geom. 42(1), 3---21 (2009)

Digital Library

[3]

Agarwal, P.K., Arge, L., Brodal, G.S., Vitter, J.S.: I/O-efficient dynamic point location in monotone planar subdivisions. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11---20 (1999)

Digital Library

[4]

Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. CACM 31(9), 1116---1127 (1988)

Digital Library

[5]

Arge, L., Brodal, G.S., Georgiadis, L.: Improved dynamic planar point location. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 305---314 (2006)

Digital Library

[6]

Arge, L., Brodal, G.S., Rao, S.S.: External memory planar point location with logarithmic updates. Algorithmica 63(1---2), 457---475 (2012)

[7]

Arge, L., Danner, A., Teh, S.-M.: I/O-efficient point location using persistent B-trees. ACM J. Exp. Algorithmics 8, 1---2 (2003)

Digital Library

[8]

Arge, L., Vahrenhold, J.: I/O-efficient dynamic planar point location. Comput. Geom. 29(2), 147---162 (2004)

Digital Library

[9]

Arge, L., Vengroff, D.E., Vitter, J.S.: External-memory algorithms for processing line segments in geographic information systems. Algorithmica 47(1), 1---25 (2007)

Digital Library

[10]

Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput. 38(3), 899---921 (2008)

Digital Library

[11]

Baumgarten, H., Jung, H., Mehlhorn, K.: Dynamic point location in general subdivisions. J. Algorithms 17(3), 342---380 (1994)

Digital Library

[12]

Bender, M.A., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: International Colloquium on Automata, Languages and Programming (ICALP), pp. 195---207 (2002)

Digital Library

[13]

Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1(4), 301---358 (1980)

[14]

Bertino, E., Catania, B., Shidlovsky, B.: Towards optimal indexing for segment databases. In: Proceedings of Extending Database Technology (EDBT), pp. 39---53 (1998)

Digital Library

[15]

Cheng, S.-W., Janardan, R.: New results on dynamic planar point location. SIAM J. Comput. 21(5), 972---999 (1992)

Digital Library

[16]

de Berg, M., Haverkort, H.J., Thite, S., Toma, L.: I/O-efficient map overlay and point location in low-density subdivisions. In: International Symposium on Algorithms and Computation (ISAAC), pp. 500---511 (2007)

Digital Library

[17]

den Bercken, J.V., Seeger, B., Widmayer, P.: A generic approach to bulk loading multidimensional index structures. In: Proceedings of Very Large Data Bases (VLDB), pp. 406---415 (1997)

Digital Library

[18]

Goodrich, M.T., Tsay, J.-J., Vengroff, D.E., Vitter, J.S.: External-memory computational geometry. In: Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 714---723 (1993)

Digital Library

[19]

Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127---151 (1987)

Digital Library

[20]

Maheshwari, A., Zeh, N.: I/O-efficient planar separators. SIAM J. Comput. 38(3), 767---801 (2008)

Digital Library

[21]

Overmars, M.H.: Range searching in a set of line segments. In: Proceedings of Symposium on Computational Geometry (SoCG), pp. 177---185 (1985)

Digital Library

[22]

Patrascu, M., Thorup, M.: Time---space trade-offs for predecessor search. In: Proceedings of ACM Symposium on Theory of Computing (STOC), pp. 232---240 (2006)

Digital Library

[23]

Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. CACM 29(7), 669---679 (1986)

Digital Library

[24]

van Walderveen, F., Zeh, N., Arge, L.: Multiway simple cycle separators and i/o-efficient algorithms for planar graphs. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 901---918 (2013)

Digital Library

Cited By

Shangqi LMartens WNiewerth MTao Y(2023)Partial Order Multiway SearchACM Transactions on Database Systems10.1145/362695648:4(1-31)Online publication date: 9-Oct-2023
https://dl.acm.org/doi/10.1145/3626956
Rahul STao Y(2022)Generic Techniques for Building Top-k StructuresACM Transactions on Algorithms10.1145/354607418:4(1-23)Online publication date: 29-Jun-2022
https://dl.acm.org/doi/10.1145/3546074
Lu SMartens WNiewerth MTao YLibkin LBarceló P(2022)Optimal Algorithms for Multiway Search on Partial OrdersProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3524150(175-187)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3524150

Recommendations

PinMesh-Fast and exact 3D point location queries using a uniform grid

This paper presents PinMesh, a very fast algorithm with implementation to preprocess a polyhedral mesh, also known as a multi-material mesh, in order to perform 3D point location queries. PinMesh combines several innovative components to efficiently ...
Quality Triangulations with Locally Optimal Steiner Points

We propose two novel ideas to improve the performance of Delaunay refinement algorithms which are used for computing quality triangulations. The first idea is an effective use of the Voronoi diagram and unifies previously suggested Steiner point ...
Nearly optimal expected-case planar point location
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science

We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that a query point lies within this polygon. The goal is to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 81, Issue 5

May 2019

365 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 May 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shangqi LMartens WNiewerth MTao Y(2023)Partial Order Multiway SearchACM Transactions on Database Systems10.1145/362695648:4(1-31)Online publication date: 9-Oct-2023
https://dl.acm.org/doi/10.1145/3626956
Rahul STao Y(2022)Generic Techniques for Building Top-k StructuresACM Transactions on Algorithms10.1145/354607418:4(1-23)Online publication date: 29-Jun-2022
https://dl.acm.org/doi/10.1145/3546074
Lu SMartens WNiewerth MTao YLibkin LBarceló P(2022)Optimal Algorithms for Multiway Search on Partial OrdersProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3524150(175-187)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3524150

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents