1 Search Results for "�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-dev.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}
}

Refine by Author
1 Iacono, John
1 Özkan, Özgür

Refine by Classification

Refine by Keyword
1 Data structures
1 amortized analysis

Refine by Type
1 document

Refine by Publication Year
1 2010

1 Search Results for "�zkan, �zg�r"

Mergeable Dictionaries

Abstract

Cite as

Thanks for your feedback!

Could not send message