Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Improved Address-Calculation C...

Improved Address-Calculation Coding of Integer Arrays

Amr Elmasry, Jyrki Katajainen, Jukka Teuhola, Improved Address-Calculation Coding of Integer Arrays. In: Liliana Calderón-Benavides, Cristina González-Caro, Edgar Chávez, Nivio Ziviani (Eds.), String Processing and Information Retrieval, 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings, LNCS 7608, 205–216, Springer, 2012.

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(lg lg (n+s)) time, as well as prefix-sum searches in O(lg n + lg lg s) time, using the word RAM as the model of computation. The second version of the data structure supports accesses in O(lg lg U) time and changes of element values in O(lg^2 U) 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 + lg lg U) time, and insertions and deletions in O(lg^2 U) time.

BibTeX entry:

@INPROCEEDINGS{inpElKaTe12a,
  title = {Improved Address-Calculation Coding of Integer Arrays},
  booktitle = {String Processing and Information Retrieval, 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings},
  author = {Elmasry, Amr and Katajainen, Jyrki and Teuhola, Jukka},
  volume = {7608},
  series = {LNCS},
  editor = {Calderón-Benavides, Liliana and González-Caro, Cristina and Chávez, Edgar and Ziviani, Nivio},
  publisher = {Springer},
  pages = {205–216},
  year = {2012},
}

Belongs to TUCS Research Unit(s): Algorithmics and Computational Intelligence Group (ACI)

Edit publication