LIPIcs.SEA.2020.25.pdf
- Filesize: 0.58 MB
- 13 pages
Document
Zipping Segment Trees
Authors
Lukas Barth 
,
Dorothea Wagner
-
Part of:
Volume:
18th International Symposium on Experimental Algorithms (SEA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-12
File
Document Identifiers
Author Details
Cite As Get BibTex
Lukas Barth and Dorothea Wagner. Zipping Segment Trees. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SEA.2020.25
Abstract
Stabbing queries in sets of intervals are usually answered using segment trees. A dynamic variant of segment trees has been presented by van Kreveld and Overmars, which uses red-black trees to do rebalancing operations. This paper presents zipping segment trees - dynamic segment trees based on zip trees, which were recently introduced by Tarjan et al. To facilitate zipping segment trees, we show how to uphold certain segment tree properties during the operations of a zip tree. We present an in-depth experimental evaluation and comparison of dynamic segment trees based on red-black trees, weight-balanced trees and several variants of the novel zipping segment trees. Our results indicate that zipping segment trees perform better than rotation-based alternatives.
Subject Classification
ACM Subject Classification
- Theory of computation → Sorting and searching
- Information systems → Point lookups
Keywords
- Segment Trees
- Dynamic Segment Trees
- Zip Trees
- Data Structures
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Lukas Barth and Dorothea Wagner. Shaving peaks by augmenting the dependency graph. In Proceedings of the Tenth ACM International Conference on Future Energy Systems, pages 181-191. ACM, 2019. URL: https://doi.org/10.1145/3307772.3328298.
- Lukas Barth and Dorothea Wagner. Engineering top-down weight-balanced trees. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX), pages 161-174. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976007.13.
-
Jon Louis Bentley. Algorithms for Klee’s rectangle problems. Technical report, Department of Computer Science, Carnegie-Mellon University, 1977. Unpublished notes.
- Yeim-Kuan Chang and Yung-Chieh Lin. Dynamic segment trees for ranges and prefixes. IEEE Transactions on Computers, 56(6):769-784, 2007. URL: https://doi.org/10.1109/TC.2007.1037.
- Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-77974-2.
- Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19-51, 1997. URL: https://doi.org/10.1006/jagm.1997.0873.
- Stefan Edelkamp, Shahid Jabbar, and Thomas Willhalm. Geometric travel planning. IEEE Transactions on Intelligent Transportation Systems, 6(1):5-16, 2005. URL: https://doi.org/10.1109/TITS.2004.838182.
- Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter. Evaluation of labeling strategies for rotating maps. Journal of Experimental Algorithmics (JEA), 21:1-21, 2016. URL: https://doi.org/10.1145/2851493.
-
Johannes Antonius La Poutré. New techniques for the union-find problem. In Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 54-63, 1990.
- Raimund Seidel and Cecilia R Aragon. Randomized search trees. Algorithmica, 16(4-5):464-497, 1996. URL: https://doi.org/10.1007/BF01940876.
- Raimund Seidel and Micha Sharir. Top-down analysis of path compression. SIAM Journal on Computing, 34(3):515-525, 2005. URL: https://doi.org/10.1137/S0097539703439088.
- Robert E Tarjan, Caleb C Levy, and Stephen Timmel. Zip trees. CoRR, abs/1806.06726, 2018. URL: http://arxiv.org/abs/1806.06726.
- Robert E Tarjan, Caleb C Levy, and Stephen Timmel. Zip trees. In Workshop on Algorithms and Data Structures (WADS), pages 566-577. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_41.
- Marc J van Kreveld and Mark H Overmars. Union-copy structures and dynamic segment trees. Journal of the ACM (JACM), 40(3):635-652, 1993. URL: https://doi.org/10.1145/174130.174140.