| 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 (161 kB) |
| DOI: | 10.1016/j.ipl.2010.08.007 |
| Copyright: | © Elsevier B.V. |
| Abstract: | 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. |
| BibLATEX: | @article{KR2010J,
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},
}
|