Document Open Access Logo

A Simple Mergeable Dictionary

Author Adam Karczmarz

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.7.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Adam Karczmarz

Cite As Get BibTex

Adam Karczmarz. A Simple Mergeable Dictionary. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.7

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].

Subject Classification

Keywords
  • dictionary
  • mergeable
  • data structure
  • merge
  • split

Metrics

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

References

  1. Lars Arge and Jeffrey Scott Vitter. Optimal external memory interval management. SIAM J. Comput., 32(6):1488-1508, 2003. URL: http://dx.doi.org/10.1137/S009753970240481X.
  2. Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich. Biased skip lists. Algorithmica, 42(1):31-48, 2005. URL: http://dx.doi.org/10.1007/s00453-004-1138-6.
  3. Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito. Two simplified algorithms for maintaining order in a list. In Algorithms - ESA 2002, 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings, pages 152-164, 2002. URL: http://dx.doi.org/10.1007/3-540-45749-6_17.
  4. Mark R. Brown and Robert Endre Tarjan. A fast merging algorithm. J. ACM, 26(2):211-226, 1979. URL: http://dx.doi.org/10.1145/322123.322127.
  5. Paul F. Dietz and Daniel Dominic Sleator. Two algorithms for maintaining order in a list. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 365-372, 1987. URL: http://dx.doi.org/10.1145/28395.28434.
  6. Martin Farach and Mikkel Thorup. String matching in lempel-ziv compressed strings. Algorithmica, 20(4):388-404, 1998. URL: http://dx.doi.org/10.1007/PL00009202.
  7. Paweł Gawrychowski. Pattern matching in lempel-ziv compressed strings: Fast, simple, and deterministic. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, pages 421-432, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_36.
  8. Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Robert Endre Tarjan, and Renato Fonseca F. Werneck. Data structures for mergeable trees. ACM Transactions on Algorithms, 7(2):14, 2011. URL: http://dx.doi.org/10.1145/1921659.1921660.
  9. Leonidas J. Guibas and Robert Sedgewick. A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978, pages 8-21, 1978. URL: http://dx.doi.org/10.1109/SFCS.1978.3.
  10. Scott Huddleston and Kurt Mehlhorn. A new data structure for representing sorted lists. Acta Inf., 17:157-184, 1982. URL: http://dx.doi.org/10.1007/BF00288968.
  11. John Iacono and Özgür Özkan. Mergeable dictionaries. In Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming, ICALP'10, pages 164-175, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_15.
  12. Tsvi Kopelowitz. On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 283-292, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.79.
  13. Katherine Jane Lai. Complexity of union-split-find problems. Master’s thesis, Massachusetts Institute of Technology, 2008. URL: http://erikdemaine.org/theses/klai.pdf.
  14. William Pugh. Skip lists: A probabilistic alternative to balanced trees. Commun. ACM, 33(6):668-676, 1990. URL: http://dx.doi.org/10.1145/78973.78977.
  15. Mihai Pătraşcu and Erik D. Demaine. Lower bounds for dynamic connectivity. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 546-553, 2004. URL: http://dx.doi.org/10.1145/1007352.1007435.
  16. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, June 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
  17. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary trees. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 235-245, 1983. URL: http://dx.doi.org/10.1145/800061.808752.
  18. Dan E. Willard. Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett., 17(2):81-84, 1983. URL: http://dx.doi.org/10.1016/0020-0190(83)90075-3.
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 About DROPS Imprint Privacy Contact