Mergeable dictionaries

John Iacono; Özgür ̈ Özkan

doi:10.1007/978-3-642-14165-2_15

Mergeable dictionaries

John Iacono, Özgür ̈ Özkan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A data structure is presented for the Mergeable Dictionary abstract data type, which supports the operations Predecessor-Search, Split, and Merge on a collection of disjoint sets of totally ordered data. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation. A data structure which can handle arbitrary Merge operations in O(log n) amortized time in the absence of Split operations was presented by Brown and Tarjan [2]. A data structure which can handle both Split and Merge operations in amortized time was presented by Farach and Thorup [4]. In contrast, our data structure supports all operations, including Split and Merge, in amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-à-vis disjoint Merge operations.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Pages	164-175
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-14165-2_15
State	Published - 2010
Event	37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France Duration: Jul 6 2010 → Jul 10 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6198 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Country/Territory	France
City	Bordeaux
Period	7/6/10 → 7/10/10

Keywords

amortized analysis
data structures

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-14165-2_15

Cite this

Iacono, J., & Özkan, Ö. . (2010). Mergeable dictionaries. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings (PART 1 ed., pp. 164-175). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-14165-2_15

Mergeable dictionaries. / Iacono, John; Özkan, Özgür ̈.
Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1. ed. 2010. p. 164-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Iacono, J & Özkan, Ö 2010, Mergeable dictionaries. in Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6198 LNCS, pp. 164-175, 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, Bordeaux, France, 7/6/10. https://doi.org/10.1007/978-3-642-14165-2_15

@inproceedings{443e93eb9ea642a293d9aca03173e336,

title = "Mergeable dictionaries",

abstract = "A data structure is presented for the Mergeable Dictionary abstract data type, which supports the operations Predecessor-Search, Split, and Merge on a collection of disjoint sets of totally ordered data. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation. A data structure which can handle arbitrary Merge operations in O(log n) amortized time in the absence of Split operations was presented by Brown and Tarjan [2]. A data structure which can handle both Split and Merge operations in amortized time was presented by Farach and Thorup [4]. In contrast, our data structure supports all operations, including Split and Merge, in amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-{\`a}-vis disjoint Merge operations.",

keywords = "amortized analysis, data structures",

author = "John Iacono and {\"O}zkan, {{\"O}zg{\"u}r{\" }}",

note = "Copyright: Copyright 2010 Elsevier B.V., All rights reserved.; 37th International Colloquium on Automata, Languages and Programming, ICALP 2010 ; Conference date: 06-07-2010 Through 10-07-2010",

year = "2010",

doi = "10.1007/978-3-642-14165-2_15",

language = "English (US)",

isbn = "3642141641",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "164--175",

booktitle = "Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings",

edition = "PART 1",

}

TY - GEN

T1 - Mergeable dictionaries

AU - Iacono, John

AU - Özkan, Özgür ̈

PY - 2010

Y1 - 2010

N2 - A data structure is presented for the Mergeable Dictionary abstract data type, which supports the operations Predecessor-Search, Split, and Merge on a collection of disjoint sets of totally ordered data. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation. A data structure which can handle arbitrary Merge operations in O(log n) amortized time in the absence of Split operations was presented by Brown and Tarjan [2]. A data structure which can handle both Split and Merge operations in amortized time was presented by Farach and Thorup [4]. In contrast, our data structure supports all operations, including Split and Merge, in amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-à-vis disjoint Merge operations.

AB - A data structure is presented for the Mergeable Dictionary abstract data type, which supports the operations Predecessor-Search, Split, and Merge on a collection of disjoint sets of totally ordered data. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation. A data structure which can handle arbitrary Merge operations in O(log n) amortized time in the absence of Split operations was presented by Brown and Tarjan [2]. A data structure which can handle both Split and Merge operations in amortized time was presented by Farach and Thorup [4]. In contrast, our data structure supports all operations, including Split and Merge, in amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-à-vis disjoint Merge operations.

KW - amortized analysis

KW - data structures

UR - http://www.scopus.com/inward/record.url?scp=77955322888&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955322888&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14165-2_15

DO - 10.1007/978-3-642-14165-2_15

M3 - Conference contribution

AN - SCOPUS:77955322888

SN - 3642141641

SN - 9783642141645

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 175

BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings

T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010

Y2 - 6 July 2010 through 10 July 2010

ER -

Mergeable dictionaries

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this