2021
Journal article
Open Access
Rank/select queries over mutable bitmaps
Pibiri G. E., Kanda S.
Bitmap FOS: Computer and information sciences Computer Science - Data Structures and Algorithms Information Systems Hardware and Architecture Software SIMD Rank/Select Data Structures and Algorithms (cs.DS)
The problem of answering rank/select queries over a bitmap is of utmost importance for many succinct data structures. When the bitmap does not change, many solutions exist in the theoretical and practical side. In this work we consider the case where one is allowed to modify the bitmap via a flip(i) operation that toggles its i-th bit. By adapting and properly extending some results concerning prefix-sum data structures, we present a practical solution to the problem, tailored for modern CPU instruction sets. Compared to the state-of-the-art, our solution improves runtime with no space degradation. Moreover, it does not incur in a significant runtime penalty when compared to the fastest immutable indexes, while providing even lower space overhead.
Source: Information systems (Oxf.) 99 (2021). doi:10.1016/j.is.2021.101756
Publisher: Pergamon,, Oxford , Regno Unito
[1] Jon Louis Bentley. 1977. Solutions to Klee's rectangle problems. Unpublished manuscript (1977), 282-300.
[2] Jon Louis Bentley and Derick Wood. 1980. An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Comput. 7 (1980), 571-577.
[3] Nieves R Brisaboa, Susana Ladra, and Gonzalo Navarro. 2014. Compact representation of web graphs with extended functionality. Information Systems 39 (2014), 152-174.
[4] Nieves R Brisaboa, Miguel R Luaces, Gonzalo Navarro, and Diego Seco. 2013. Space-eficient representations of rectangle datasets supporting orthogonal range querying. Information Systems 38, 5 (2013), 635-655.
[5] David Clark. 1996. Compact Pat Trees. Ph.D. Dissertation. University of Waterloo.
[6] Intel Corporation. [last accessed July 2020]. The Intel Intrinsics Guide, https://software.intel.com/sites/landingpage/ IntrinsicsGuide.
[7] Peter M. Fenwick. 1994. A new data structure for cumulative frequency tables. Software: Practice and experience 24, 3 (1994), 327-336.
[8] Paolo Ferragina, Rodrigo González, Gonzalo Navarro, and Rossano Venturini. 2009. Compressed text indexes: From theory to practice. Journal of Experimental Algorithmics (JEA) 13 (2009), 1-12.
[9] Michael Fredman and Michael Saks. 1989. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual Symposium on Theory of Computing (STOC). 345-354.
[10] Simon Gog, Timo Beller, Alistair Mofat, and Matthias Petri. 2014. From theory to practice: Plug and play with succinct data structures. In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA). Springer, 326-337.
[11] Simon Gog and Matthias Petri. 2014. Optimized succinct data structures for massive data. Software: Practice and Experience 44, 11 (2014), 1287-1314.
[12] Alexander Golynski. 2007. Optimal lower bounds for rank and select indexes. Theoretical Computer Science 387, 3 (2007), 348-359.
[13] Rodrigo González, Szymon Grabowski, Veli Mäkinen, and Gonzalo Navarro. 2005. Practical implementation of rank and select queries. In Poster Proceedings of the 4th Workshop on Experimental and Eficient Algorithms (WEA) . 27-38.
[14] Szymon Grabowski and Marcin Raniszewski. 2018. Rank and select: Another lesson learned. Information Systems 73 (2018), 25-34.
[15] Roberto Grossi and Giuseppe Ottaviano. 2013. Design of practical succinct data structures for large data collections. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA). Springer, 5-17.
[16] W. Daniel Hillis and Guy L. Steele. 1986. Data parallel algorithms. Commun. ACM 29, 12 (Dec. 1986), 1170âĂŞ1183.
[17] Guy Joseph Jacobson. 1988. Succinct static data structures. Ph.D. Dissertation. Carnegie Mellon University.
[18] Shunsuke Kanda, Kazuhiro Morita, and Masao Fuketa. 2017. Practical string dictionary compression using string dictionary encoding. In Proceedings of the 3rd International Conference on Big Data Innovations and Applications (Innovate-Data). 1-8.
[19] Stefano Marchini and Sebastiano Vigna. 2020. Compact Fenwick trees for dynamic ranking and selection. Software: Practice and Experience 50, 7 (2020), 1184-1202.
[20] Miguel A Martínez-Prieto, Nieves Brisaboa, Rodrigo Cánovas, Francisco Claude, and Gonzalo Navarro. 2016. Practical compressed string dictionaries. Information Systems 56 (2016), 73-108.
[21] Peter Bro Miltersen. 2005. Lower bounds on the size of selection and rank indexes. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vol. 23. Citeseer, 11-12.
[22] Wojciech Muła, Nathan Kurz, and Daniel Lemire. 2017. Faster population counts using AVX2 instructions. Comput. J. 61, 1 (2017), 111-120.
[23] Gonzalo Navarro and Eliana Providel. 2012. Fast, small, simple rank/select on bitmaps. In Proceedings of the 11th International Symposium on Experimental Algorithms (SEA). Springer, 295-306.
[24] Daisuke Okanohara and Kunihiko Sadakane. 2007. Practical entropy-compressed rank/select dictionary. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 60-70.
[25] Prashant Pandey, Michael A Bender, and Rob Johnson. 2017. A fast x86 implementation of select. arXiv preprint arXiv:1706.00990 (2017).
[26] Giulio Ermanno Pibiri and Rossano Venturini. 2020. Practical trade-ofs for the prefix-sum problem. arXiv:2006.14552 (2020).
[27] Nicola Prezza. 2017. A framework of dynamic data structures for string processing. In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA), Vol. 75. 11:1-11:15.
[28] Sebastiano Vigna. 2008. Broadword implementation of rank/select queries. In Proceedings of the 7th International Workshop on Experimental and Eficient Algorithms (WEA) . Springer, 154-168.
[29] Sebastiano Vigna. [last accessed July 2020]. The Sux library, https://github.com/vigna/sux.
[30] Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical range query filtering with fast succinct tries. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD). 323-336.
[31] Dong Zhou, David G Andersen, and Michael Kaminsky. 2013. Space-eficient, high-performance rank and select structures on uncompressed bit sequences. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA). Springer, 151-163.
[2] Jon Louis Bentley and Derick Wood. 1980. An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Comput. 7 (1980), 571-577.
[3] Nieves R Brisaboa, Susana Ladra, and Gonzalo Navarro. 2014. Compact representation of web graphs with extended functionality. Information Systems 39 (2014), 152-174.
[4] Nieves R Brisaboa, Miguel R Luaces, Gonzalo Navarro, and Diego Seco. 2013. Space-eficient representations of rectangle datasets supporting orthogonal range querying. Information Systems 38, 5 (2013), 635-655.
[5] David Clark. 1996. Compact Pat Trees. Ph.D. Dissertation. University of Waterloo.
[6] Intel Corporation. [last accessed July 2020]. The Intel Intrinsics Guide, https://software.intel.com/sites/landingpage/ IntrinsicsGuide.
[7] Peter M. Fenwick. 1994. A new data structure for cumulative frequency tables. Software: Practice and experience 24, 3 (1994), 327-336.
[8] Paolo Ferragina, Rodrigo González, Gonzalo Navarro, and Rossano Venturini. 2009. Compressed text indexes: From theory to practice. Journal of Experimental Algorithmics (JEA) 13 (2009), 1-12.
[9] Michael Fredman and Michael Saks. 1989. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual Symposium on Theory of Computing (STOC). 345-354.
[10] Simon Gog, Timo Beller, Alistair Mofat, and Matthias Petri. 2014. From theory to practice: Plug and play with succinct data structures. In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA). Springer, 326-337.
[11] Simon Gog and Matthias Petri. 2014. Optimized succinct data structures for massive data. Software: Practice and Experience 44, 11 (2014), 1287-1314.
[12] Alexander Golynski. 2007. Optimal lower bounds for rank and select indexes. Theoretical Computer Science 387, 3 (2007), 348-359.
[13] Rodrigo González, Szymon Grabowski, Veli Mäkinen, and Gonzalo Navarro. 2005. Practical implementation of rank and select queries. In Poster Proceedings of the 4th Workshop on Experimental and Eficient Algorithms (WEA) . 27-38.
[14] Szymon Grabowski and Marcin Raniszewski. 2018. Rank and select: Another lesson learned. Information Systems 73 (2018), 25-34.
[15] Roberto Grossi and Giuseppe Ottaviano. 2013. Design of practical succinct data structures for large data collections. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA). Springer, 5-17.
[16] W. Daniel Hillis and Guy L. Steele. 1986. Data parallel algorithms. Commun. ACM 29, 12 (Dec. 1986), 1170âĂŞ1183.
[17] Guy Joseph Jacobson. 1988. Succinct static data structures. Ph.D. Dissertation. Carnegie Mellon University.
[18] Shunsuke Kanda, Kazuhiro Morita, and Masao Fuketa. 2017. Practical string dictionary compression using string dictionary encoding. In Proceedings of the 3rd International Conference on Big Data Innovations and Applications (Innovate-Data). 1-8.
[19] Stefano Marchini and Sebastiano Vigna. 2020. Compact Fenwick trees for dynamic ranking and selection. Software: Practice and Experience 50, 7 (2020), 1184-1202.
[20] Miguel A Martínez-Prieto, Nieves Brisaboa, Rodrigo Cánovas, Francisco Claude, and Gonzalo Navarro. 2016. Practical compressed string dictionaries. Information Systems 56 (2016), 73-108.
[21] Peter Bro Miltersen. 2005. Lower bounds on the size of selection and rank indexes. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vol. 23. Citeseer, 11-12.
[22] Wojciech Muła, Nathan Kurz, and Daniel Lemire. 2017. Faster population counts using AVX2 instructions. Comput. J. 61, 1 (2017), 111-120.
[23] Gonzalo Navarro and Eliana Providel. 2012. Fast, small, simple rank/select on bitmaps. In Proceedings of the 11th International Symposium on Experimental Algorithms (SEA). Springer, 295-306.
[24] Daisuke Okanohara and Kunihiko Sadakane. 2007. Practical entropy-compressed rank/select dictionary. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 60-70.
[25] Prashant Pandey, Michael A Bender, and Rob Johnson. 2017. A fast x86 implementation of select. arXiv preprint arXiv:1706.00990 (2017).
[26] Giulio Ermanno Pibiri and Rossano Venturini. 2020. Practical trade-ofs for the prefix-sum problem. arXiv:2006.14552 (2020).
[27] Nicola Prezza. 2017. A framework of dynamic data structures for string processing. In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA), Vol. 75. 11:1-11:15.
[28] Sebastiano Vigna. 2008. Broadword implementation of rank/select queries. In Proceedings of the 7th International Workshop on Experimental and Eficient Algorithms (WEA) . Springer, 154-168.
[29] Sebastiano Vigna. [last accessed July 2020]. The Sux library, https://github.com/vigna/sux.
[30] Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical range query filtering with fast succinct tries. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD). 323-336.
[31] Dong Zhou, David G Andersen, and Michael Kaminsky. 2013. Space-eficient, high-performance rank and select structures on uncompressed bit sequences. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA). Springer, 151-163.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:446386,
title = {Rank/select queries over mutable bitmaps},
author = {Pibiri G. E. and Kanda S.},
publisher = {Pergamon,, Oxford , Regno Unito},
doi = {10.1016/j.is.2021.101756 and 10.48550/arxiv.2009.12809},
journal = {Information systems (Oxf.)},
volume = {99},
year = {2021}
}CNR authorsLaboratories
0000-0003-0724-7092CNR ExploRA
ISTI Repository
DOI
ISTI Repository
DOI
10.1016/j.is.2021.101756
10.48550/arxiv.2009.12809
arXiv.org e-Print Archive
Information Systems
www.sciencedirect.com
