| Improved address-calculation coding of integer arrays | |
| Authors: | Amr Elmasry, Jyrki Katajainen, and Jukka Teuhola |
| Published in: | Proceedings of the 19th International Symposium on String Processing and Information Retrieval, Lecture Notes in Computer Science 7608, Springer-Verlag (2012), 205-216 |
| Full text: |  PDF (152 kB) |
| DOI: | 10.1007/978-3-642-34109-0_22 |
| Copyright: | © Springer-Verlag |
| Abstract: | In this paper we deal with compressed integer arrays that are equipped with fast random access. Our treatment improves over an earlier approach that used address-calculation coding to locate the elements and supported access and search operations in O(lg(n + s)) time for a sequence of n non-negative integers summing up to s. The idea is to complement the address-calculation method with index structures that considerably decrease access times and also enable updates. For all our structures the memory usage is n lg(1 + s/n) + O(n) bits. First a read-only version is introduced that supports rank-based accesses to elements and retrievals of prefix sums in O(lglg(n + s)) time, as well as prefix-sum searches in O(lg n + lglg s) time, using the word RAM as the model of computation. The second version of the data structure supports accesses in O(lglg U) time and changes of element values in O(lg2U) time, where U is the universe size. Both versions performed quite well in practical experiments. A third extension to dynamic arrays is also described, supporting accesses and prefix-sum searches in O(lg n + lglg U) time, and insertions and deletions in O(lg2U) time. |
| Related: |  HTML (Slides) |
| BibLATEX: | @inproceedings{EKT2012C,
author = {Amr Elmasry and Jyrki Katajainen and Jukka Teuhola},
title = {Improved address-calculation coding of integer arrays},
booktitle = {Proceedings of the 19th International Symposium on String
Processing and Information Retrieval},
series = {Lecture Notes in Computer Science},
volume = {7608},
publisher = {Springer-Verlag},
year = {2012},
pages = {205--216},
}
|