Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.7
URN: urn:nbn:de:0030-drops-60285
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6028/
Karczmarz, Adam
A Simple Mergeable Dictionary
| pdf-format: |
|
Abstract
A mergeable dictionary is a data structure storing a dynamic subset S of a totally ordered set U and supporting predecessor searches in S. Apart from insertions and deletions to S, we can both merge two arbitrarily interleaved dictionaries and split a given dictionary around some pivot x. We present an implementation of a mergeable dictionary matching the optimal amortized logarithmic bounds of Iacono and Ökzan [Iacono/Ökzan,ICALP'10]. However, our solution is significantly simpler. The proposed data structure can also be generalized to the case when the universe U is dynamic or infinite, thus addressing one issue of [Iacono/Ökzan,ICALP'10].
BibTeX - Entry
@InProceedings{karczmarz:LIPIcs:2016:6028,
author = {Adam Karczmarz},
title = {{A Simple Mergeable Dictionary}},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {7:1--7:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-011-8},
ISSN = {1868-8969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6028},
URN = {urn:nbn:de:0030-drops-60285},
doi = {10.4230/LIPIcs.SWAT.2016.7},
annote = {Keywords: dictionary, mergeable, data structure, merge, split}
}
| Keywords: | dictionary, mergeable, data structure, merge, split | |
| Seminar: | 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 22.06.2016 |
