Compressed persistent index for efficient rank/select queries

Wing Kai Hon; Lap Kei Lee; Kunihiko Sadakane; Konstantinos Tsakalidis

doi:10.1007/978-3-642-40104-6_35

Compressed persistent index for efficient rank/select queries

Wing Kai Hon, Lap Kei Lee, Kunihiko Sadakane, Konstantinos Tsakalidis

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

1 Citation (Scopus)

Abstract

We design compressed persistent indices that store a bit vector of size n and support a sequence of k bit-flip update operations, such that rank and select queries at any version can be supported efficiently. In particular, we present partially and fully persistent compressed indices for offline and online updates that support all operations in time polylogarithmic in n and k. This improves upon the space or time complexities of straightforward approaches, when k = O(n/log n), which is common in biological applications. We also prove that any partially persistent index that occupies O((n + k)log(nk)) bits requires ω(1) time to support the rank query at a given version.

Original language	English
Title of host publication	Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Pages	402-414
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-40104-6_35
Publication status	Published - 2013
Externally published	Yes
Event	13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada Duration: 12 Aug 2013 → 14 Aug 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8037 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Symposium on Algorithms and Data Structures, WADS 2013
Country/Territory	Canada
City	London, ON
Period	12/08/13 → 14/08/13

Access to Document

10.1007/978-3-642-40104-6_35

Cite this

Hon, W. K., Lee, L. K., Sadakane, K., & Tsakalidis, K. (2013). Compressed persistent index for efficient rank/select queries. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings (pp. 402-414). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS). https://doi.org/10.1007/978-3-642-40104-6_35

@inproceedings{5f8d5aa2d7334f0884a54f1c33496199,

title = "Compressed persistent index for efficient rank/select queries",

abstract = "We design compressed persistent indices that store a bit vector of size n and support a sequence of k bit-flip update operations, such that rank and select queries at any version can be supported efficiently. In particular, we present partially and fully persistent compressed indices for offline and online updates that support all operations in time polylogarithmic in n and k. This improves upon the space or time complexities of straightforward approaches, when k = O(n/log n), which is common in biological applications. We also prove that any partially persistent index that occupies O((n + k)log(nk)) bits requires ω(1) time to support the rank query at a given version.",

author = "Hon, {Wing Kai} and Lee, {Lap Kei} and Kunihiko Sadakane and Konstantinos Tsakalidis",

year = "2013",

doi = "10.1007/978-3-642-40104-6_35",

language = "English",

isbn = "9783642401039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "402--414",

booktitle = "Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings",

note = "13th International Symposium on Algorithms and Data Structures, WADS 2013 ; Conference date: 12-08-2013 Through 14-08-2013",

}

Hon, WK, Lee, LK, Sadakane, K & Tsakalidis, K 2013, Compressed persistent index for efficient rank/select queries. in Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8037 LNCS, pp. 402-414, 13th International Symposium on Algorithms and Data Structures, WADS 2013, London, ON, Canada, 12/08/13. https://doi.org/10.1007/978-3-642-40104-6_35

Compressed persistent index for efficient rank/select queries. / Hon, Wing Kai; Lee, Lap Kei; Sadakane, Kunihiko et al.
Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. 2013. p. 402-414 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS).

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

TY - GEN

T1 - Compressed persistent index for efficient rank/select queries

AU - Hon, Wing Kai

AU - Lee, Lap Kei

AU - Sadakane, Kunihiko

AU - Tsakalidis, Konstantinos

PY - 2013

Y1 - 2013

N2 - We design compressed persistent indices that store a bit vector of size n and support a sequence of k bit-flip update operations, such that rank and select queries at any version can be supported efficiently. In particular, we present partially and fully persistent compressed indices for offline and online updates that support all operations in time polylogarithmic in n and k. This improves upon the space or time complexities of straightforward approaches, when k = O(n/log n), which is common in biological applications. We also prove that any partially persistent index that occupies O((n + k)log(nk)) bits requires ω(1) time to support the rank query at a given version.

AB - We design compressed persistent indices that store a bit vector of size n and support a sequence of k bit-flip update operations, such that rank and select queries at any version can be supported efficiently. In particular, we present partially and fully persistent compressed indices for offline and online updates that support all operations in time polylogarithmic in n and k. This improves upon the space or time complexities of straightforward approaches, when k = O(n/log n), which is common in biological applications. We also prove that any partially persistent index that occupies O((n + k)log(nk)) bits requires ω(1) time to support the rank query at a given version.

UR - http://www.scopus.com/inward/record.url?scp=84881124837&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40104-6_35

DO - 10.1007/978-3-642-40104-6_35

M3 - Conference contribution

AN - SCOPUS:84881124837

SN - 9783642401039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 402

EP - 414

BT - Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings

T2 - 13th International Symposium on Algorithms and Data Structures, WADS 2013

Y2 - 12 August 2013 through 14 August 2013

ER -

Hon WK, Lee LK, Sadakane K, Tsakalidis K. Compressed persistent index for efficient rank/select queries. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. 2013. p. 402-414. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40104-6_35

Compressed persistent index for efficient rank/select queries

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this