Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427432 | Information Processing Letters | 2010 | 6 Pages |
Abstract
We develop a data structure for maintaining a dynamic multiset that uses O(nlglgn/lgn) bits and O(1)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)O(n) bits to O(nlglgn/lgn) bits, but the running time of updates is amortized, not worst-case.
Research highlights► Gives a space-efficient dynamic multiset representation. ► Improves the space redundancy of earlier structure from constant bits per element to o(1)o(1) bits per element. ► Gives several improved memory management techniques.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jyrki Katajainen, S. Srinivasa Rao,