License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-26854
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2685/

Iacono, John ; Özkan, Özgür

Mergeable Dictionaries

pdf-format:
Dokument 1.pdf (646 KB)


Abstract

A data structure is presented for the Mergeable Dictionary abstract data type, which supports the following operations on a collection of disjoint sets of totally ordered data: Predecessor-Search, Split and Union. While Predecessor-Search and Split work in the normal way, the novel operation is Union. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Union operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation, and permits the merging of arbitrarily interleaved sets. Our data structure supports all operations, including Union, in O(log n) amortized time, thus showing that interleaved Union operations can be supported at no additional cost vis-a-vis disjoint Union operations.

BibTeX - Entry

@InProceedings{iacono_et_al:DSP:2010:2685,
  author =	{John Iacono and {\"O}zg{\"u}r {\"O}zkan},
  title =	{Mergeable Dictionaries},
  booktitle =	{Data Structures},
  year =	{2010},
  editor =	{Lars Arge and Erik D. Demaine and Raimund Seidel},
  number =	{10091},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2685},
  annote =	{Keywords: Data structures, amortized analysis}
}

Keywords: Data structures, amortized analysis
Seminar: 10091 - Data Structures
Issue date: 2010
Date of publication: 26.07.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI