KIT | KIT-Bibliothek | Impressum | Datenschutz

Zipping Segment Trees

Barth, Lukas; Wagner, Dorothea

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.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000128473
Veröffentlicht am 13.01.2021
Originalveröffentlichung
DOI: 10.4230/LIPIcs.SEA.2020.25
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2020
Sprache Englisch
Identifikator ISBN: 978-3-9597714-8-1
ISSN: 1868-8969
KITopen-ID: 1000128473
HGF-Programm 37.06.01 (POF III, LK 01) Networks and Storage Integration
Erschienen in 18th International Symposium on Experimental Algorithms (SEA 2020). Hrsg.: Faro, S.
Veranstaltung 18th International Symposium on Experimental Algorithms (SEA 2020), Online, 16.06.2020 – 18.06.2020
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH (LZI)
Seiten 25:1–25:13
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 160
Bemerkung zur Veröffentlichung Die Veranstaltung fand wegen der Corona-Pandemie als Online-Event statt
Schlagwörter Segment Trees, Dynamic Segment Trees, Zip Trees, Data Structures
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page