Abstract
A rank-select index for a sequence \(B=(b_1,\ldots ,b_n)\) of n bits, where \(n\in \mathbb {N}=\{1,2,\ldots \}\), is a data structure that, if provided with a constant-time operation to access (the integer whose binary representation is) the subsequence of B in \(\varTheta (\log n)\) specified consecutive positions (thus B is stored outside of the data structure), can compute \(\textit{rank}_B(j)=\sum _{i=1}^j b_i\) for given \(j\in \{0,\ldots ,n\}\) and \(\textit{select}_B(k)=\min \{j\in \mathbb {N}\mid \textit{rank}_B(j)\ge k\}\) for given \(k\in \{1,\ldots ,\sum _{i=1}^n b_i\}\). We describe a new rank-select index that, like previous rank-select indices, occupies \(O({{n\log \log n}/{\log n}})\) bits and executes \(\textit{rank}\) and \(\textit{select}\) queries in constant time. Its derivation is intended to be largely free of tedious low-level detail, its operations are given by straight-line code, and it can be constructed in \(O({n/{\log n}})\) time if B can be accessed as above.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angluin, D., Valiant, L.G.: Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. Syst. Sci. 18(2), 155–193 (1979). https://doi.org/10.1016/0022-0000(79)90045-X
Clark, D.: Compact pat trees. Ph.D. thesis, University of Waterloo (1996)
Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246–260 (1974). https://doi.org/10.1145/321812.321820
Fano, R.M.: On the number of bits required to implement an associative memory. Computation Structures Group Memo 61, MIT Project MAC, August 1971
Golynski, A.: Optimal lower bounds for rank and select indexes. Theor. Comput. Sci. 387(3), 348–359 (2007). https://doi.org/10.1016/j.tcs.2007.07.041
Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841–850. SIAM (2003)
Hagerup, T.: Sorting and searching on the word RAM. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998). LNCS, vol. 1373, pp. 366–398. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0028575
Hagerup, T., Kammer, F., Laudahn, M.: Space-efficient Euler partition and bipartite edge coloring. Theor. Comput. Sci. 754, 16–34 (2019). https://doi.org/10.1016/j.tcs.2018.01.008
Jacobson, G.: Succinct static data structures. Ph.D. thesis, Carnegie Mellon University (1988)
Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1989), pp. 549–554. IEEE Computer Society (1989). https://doi.org/10.1109/SFCS.1989.63533
Mäkinen, V., Navarro, G.: Rank and select revisited and extended. Theor. Comput. Sci. 387(3), 332–347 (2007). https://doi.org/10.1016/j.tcs.2007.07.013
Pǎtraşcu, M.: Succincter. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 305–313. IEEE Computer Society (2008). https://doi.org/10.1109/FOCS.2008.83
Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007). https://doi.org/10.1145/1290672.1290680
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Baumann, T., Hagerup, T. (2019). Rank-Select Indices Without Tears. In: Friggstad, Z., Sack, JR., Salavatipour, M. (eds) Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science(), vol 11646. Springer, Cham. https://doi.org/10.1007/978-3-030-24766-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-24766-9_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24765-2
Online ISBN: 978-3-030-24766-9
eBook Packages: Computer ScienceComputer Science (R0)