A compact data structure for representing a dynamic multiset

TY - JOUR

T1 - A compact data structure for representing a dynamic multiset

AU - Katajainen, Jyrki

AU - Rao, S. Srinivasa

PY - 2010

Y1 - 2010

N2 - We develop a data structure for maintaining a dynamic multiset that uses O(nlglgn/lgn) bits and O(1) words, in addition to the space required by the n elements stored, supports searches in O(lgn) worst-case time and updates in O(lgn) amortized time. Compared to earlier data structures, we improve the space requirements from O(n) bits to O(nlglgn/lgn) bits, but the running time of updates is amortized, not worst-case.

AB - We develop a data structure for maintaining a dynamic multiset that uses O(nlglgn/lgn) bits and O(1) words, in addition to the space required by the n elements stored, supports searches in O(lgn) worst-case time and updates in O(lgn) amortized time. Compared to earlier data structures, we improve the space requirements from O(n) bits to O(nlglgn/lgn) bits, but the running time of updates is amortized, not worst-case.

KW - Balanced search trees

KW - Data structures

KW - Dictionaries

KW - Memory management

KW - Space efficiency

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

U2 - 10.1016/j.ipl.2010.08.007

DO - 10.1016/j.ipl.2010.08.007

M3 - Journal article

AN - SCOPUS:77956872964

SN - 0020-0190

VL - 110

SP - 1061

EP - 1066

JO - Information Processing Letters

JF - Information Processing Letters

IS - 23

ER -