Forskning ved Københavns Universitet - Københavns Universitet

Forside

A compact data structure for representing a dynamic multiset

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfællebedømt

  • Jyrki Katajainen
  • S. Srinivasa Rao

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.

OriginalsprogEngelsk
TidsskriftInformation Processing Letters
Vol/bind110
Udgave nummer23
Sider (fra-til)1061-1066
Antal sider6
ISSN0020-0190
DOI
StatusUdgivet - 2010

ID: 172855195