Improved address-calculation coding of integer arrays

Amr Ahmed Abd Elmoneim Elmasry; Jyrki Katajainen; Jukka Teuhola

doi:10.1007/978-3-642-34109-0_22

Improved address-calculation coding of integer arrays

Amr Ahmed Abd Elmoneim Elmasry, Jyrki Katajainen, Jukka Teuhola

Department of Computer Science

3 Citations (Scopus)

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 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.

Original language	English
Title of host publication	String Processing and Information Retrieval : 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings
Editors	Liliana Calderón-Benavides, Cristina González-Caro , Edgar Chávez , Nivio Ziviani
Number of pages	12
Publisher	Springer
Publication date	2012
Pages	205-216
ISBN (Print)	978-3-642-34108-3
ISBN (Electronic)	978-3-642-34109-0
DOIs	https://doi.org/10.1007/978-3-642-34109-0_22
Publication status	Published - 2012
Event	19th International Symposium on String Processing and Information Retrieval - Cartagena de Indias, Colombia Duration: 21 Oct 2012 → 25 Oct 2012 Conference number: 19th

Conference

Conference	19th International Symposium on String Processing and Information Retrieval
Number	19th
Country/Territory	Colombia
City	Cartagena de Indias
Period	21/10/2012 → 25/10/2012

Series	Lecture notes in computer science
Volume	7608
ISSN	0302-9743

Access to Document

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

Cite this

Elmasry, A. A. A. E., Katajainen, J., & Teuhola, J. (2012). Improved address-calculation coding of integer arrays. In L. Calderón-Benavides, C. González-Caro , E. Chávez , & N. Ziviani (Eds.), String Processing and Information Retrieval: 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings (pp. 205-216). Springer. Lecture notes in computer science Vol. 7608 https://doi.org/10.1007/978-3-642-34109-0_22

Improved address-calculation coding of integer arrays. / Elmasry, Amr Ahmed Abd Elmoneim; Katajainen, Jyrki; Teuhola, Jukka.

String Processing and Information Retrieval: 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings. ed. / Liliana Calderón-Benavides; Cristina González-Caro ; Edgar Chávez ; Nivio Ziviani. Springer, 2012. p. 205-216 (Lecture notes in computer science, Vol. 7608).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Elmasry, AAAE, Katajainen, J & Teuhola, J 2012, Improved address-calculation coding of integer arrays. in L Calderón-Benavides, C González-Caro , E Chávez & N Ziviani (eds), String Processing and Information Retrieval: 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings. Springer, Lecture notes in computer science, vol. 7608, pp. 205-216, 19th International Symposium on String Processing and Information Retrieval, Cartagena de Indias, Colombia, 21/10/2012. https://doi.org/10.1007/978-3-642-34109-0_22

Elmasry AAAE, Katajainen J, Teuhola J. Improved address-calculation coding of integer arrays. In Calderón-Benavides L, González-Caro C, Chávez E, Ziviani N, editors, String Processing and Information Retrieval: 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings. Springer. 2012. p. 205-216. (Lecture notes in computer science, Vol. 7608). doi: 10.1007/978-3-642-34109-0_22

Elmasry, Amr Ahmed Abd Elmoneim ; Katajainen, Jyrki ; Teuhola, Jukka. / Improved address-calculation coding of integer arrays. String Processing and Information Retrieval: 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings. editor / Liliana Calderón-Benavides ; Cristina González-Caro ; Edgar Chávez ; Nivio Ziviani. Springer, 2012. pp. 205-216 (Lecture notes in computer science, Vol. 7608).

@inproceedings{642431e1b0e94c83ba6a8052e4122001,

title = "Improved address-calculation coding of integer arrays",

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 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.",

author = "Elmasry, {Amr Ahmed Abd Elmoneim} and Jyrki Katajainen and Jukka Teuhola",

year = "2012",

doi = "10.1007/978-3-642-34109-0_22",

language = "English",

isbn = "978-3-642-34108-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "205--216",

editor = "Liliana Calder{\'o}n-Benavides and {Gonz{\'a}lez-Caro }, Cristina and {Ch{\'a}vez }, Edgar and Nivio Ziviani",

booktitle = "String Processing and Information Retrieval",

note = "19th International Symposium on String Processing and Information Retrieval ; Conference date: 21-10-2012 Through 25-10-2012",

}

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 -

Improved address-calculation coding of integer arrays

Abstract

Conference

Access to Document

Fingerprint

Cite this