Improved address-calculation coding of integer arrays

TY - GEN

T1 - Improved address-calculation coding of integer arrays

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

AU - Teuhola, Jukka

N1 - Conference code: 19th

PY - 2012

Y1 - 2012

N2 - 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 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 bits. First a read-only version is introduced that supports rank-based accesses to elements and retrievals of prefix sums in) time, as well as prefix-sum searches in time, using the word RAM as the model of computation. The second version of the data structure supports accesses in time and changes of element values in 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 time, and insertions and deletions in time.

AB - 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 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 bits. First a read-only version is introduced that supports rank-based accesses to elements and retrievals of prefix sums in) time, as well as prefix-sum searches in time, using the word RAM as the model of computation. The second version of the data structure supports accesses in time and changes of element values in 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 time, and insertions and deletions in time.

U2 - 10.1007/978-3-642-34109-0_22

DO - 10.1007/978-3-642-34109-0_22

M3 - Article in proceedings

SN - 978-3-642-34108-3

T3 - Lecture notes in computer science

SP - 205

EP - 216

BT - String Processing and Information Retrieval

A2 - Calderón-Benavides, Liliana

A2 - González-Caro , Cristina

A2 - Chávez , Edgar

A2 - Ziviani, Nivio

PB - Springer

T2 - 19th International Symposium on String Processing and Information Retrieval

Y2 - 21 October 2012 through 25 October 2012

ER -