A compact data structure for representing a dynamic multiset
Authors:Jyrki Katajainen and S. Srinivasa Rao
Published in:Information Processing Letters 110,23 (2010), 1061-1066
Full text:<pdf.gif>PDF (161 kB)  
Copyright:© Elsevier B.V.

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

  author = {Jyrki Katajainen and S. Srinivasa Rao},
  title = {A compact data structure for representing a dynamic multiset},
  journaltitle = {Information Processing Letters},
  volume = {110},
  number = {23},
  year = {2010},
  pages = {1061--1066},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.