Search Results

Documents authored by Özkan, Özgür


Document
Mergeable Dictionaries

Authors: John Iacono and Özgür Özkan

Published in: Dagstuhl Seminar Proceedings, Volume 10091, Data Structures (2010)


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.

Cite as

John Iacono and Özgür Özkan. Mergeable Dictionaries. In Data Structures. Dagstuhl Seminar Proceedings, Volume 10091, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{iacono_et_al:DagSemProc.10091.2,
  author =	{Iacono, John and \"{O}zkan, \"{O}zg\"{u}r},
  title =	{{Mergeable Dictionaries}},
  booktitle =	{Data Structures},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10091},
  editor =	{Lars Arge and Erik D. Demaine and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10091.2},
  URN =		{urn:nbn:de:0030-drops-26854},
  doi =		{10.4230/DagSemProc.10091.2},
  annote =	{Keywords: Data structures, amortized analysis}
}
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