{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:29:28Z","timestamp":1760243368224,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T00:00:00Z","timestamp":1414972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We design practical implementations of data structures for compressing bit-vectors to support efficient rank-queries (counting the number of ones up to a given point). Unlike previous approaches, which either store the bit vectors plainly, or focus on compressing bit-vectors with low densities of ones or zeros, we aim at low entropies of higher order, for example 101010...10. Our implementations achieve very good compression ratios, while showing only a modest increase in query time.<\/jats:p>","DOI":"10.3390\/a7040608","type":"journal-article","created":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T08:52:52Z","timestamp":1415004772000},"page":"608-620","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["High-Order Entropy Compressed Bit Vectors with Rank\/Select"],"prefix":"10.3390","volume":"7","author":[{"given":"Kai","family":"Beskers","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Theoretische Informatik, Karlsruhe Institute of Technology, Kaiserstra\u00dfe 12, 76131 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Fischer","sequence":"additional","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Informatik, Technical University of Dortmund, Otto-Hahn-Stra\u00dfe 14,44227 Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,11,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Sadakane, K., and Navarro, G. (2010, January 17\u201319). Fully-Functional Succinct Trees. Proceedings of Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.13"},{"key":"ref_2","unstructured":"Clark, D. (1996). Compact Pat Trees. [PhD thesis, University of Waterloo]."},{"key":"ref_3","unstructured":"Munro, J.I. (1996, January 18\u201320). Tables. Proceedings of 16th Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India."},{"key":"ref_4","unstructured":"Raman, R., Raman, V., and Rao, S.S. (2002, January 6\u20138). Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Okanohara, D., and Sadakane, K. (2007, January 6). Practical Entropy-Compressed Rank\/Select Dictionary. Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611972870.6"},{"key":"ref_6","unstructured":"Vigna, S. (2008). Experimental Algorithms, Springer."},{"key":"ref_7","unstructured":"Navarro, G., Puglisi, S.J., and Valenzuela, D. (2011). Experimental Algorithms, Springer."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., and Puglisi, S.J. (2014, January 26\u201328). Hybrid Compression of Bitvectors for the FM-Index. Proceedings of Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2014.87"},{"key":"ref_9","unstructured":"Ferragina, P., and Venturini, R. (2007, January 7\u20139). A Simple Storage Scheme for Strings Achieving Entropy Bounds. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA."},{"key":"ref_10","unstructured":"Navarro, G., and Providel, E. (2012). Experimental Algorithms, Springer."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.jcss.2011.09.002","article-title":"Ultra-succinct representation of ordered trees with applications","volume":"78","author":"Jansson","year":"2012","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1145\/382780.382782","article-title":"An Analysis of the Burrows-Wheeler Transform","volume":"48","author":"Manzini","year":"2001","journal-title":"J. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"50","DOI":"10.3390\/a5010050","article-title":"A Note on Sequence Prediction over Lage Alphabets","volume":"5","author":"Gagie","year":"2012","journal-title":"Algorithms"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.ipm.2012.08.003","article-title":"DACs: Bringing Direct Access to Variable-Length Codes","volume":"49","author":"Brisaboa","year":"2013","journal-title":"Inf. Process. Manag."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Fischer, J., Heun, V., and St\u00fchler, H.M. (2008, January 25\u201327). Practical Entropy Bounded Schemes for O(1)-Range Minimum Queries. Proceedings of Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2008.45"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/s00453-012-9726-3","article-title":"Efficient Fully-Compressed Sequence Representations","volume":"69","author":"Barbay","year":"2014","journal-title":"Algorithmica"},{"key":"ref_17","unstructured":"Source code. Available online: http:\/\/ls11-www.cs.uni-dortmund.de\/_media\/fischer\/research\/diplcode.tar.gz."},{"key":"ref_18","unstructured":"Simon Gog\u2019s sdsl. Available online: https:\/\/github.com\/simongog\/sdsl."},{"key":"ref_19","unstructured":"Daisuke Okanohara\u2019s Rsdic. Available online: https:\/\/code.google.com\/p\/rsdic\/."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/4\/608\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:17:44Z","timestamp":1760217464000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/4\/608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,3]]},"references-count":19,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2014,12]]}},"alternative-id":["a7040608"],"URL":"https:\/\/doi.org\/10.3390\/a7040608","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2014,11,3]]}}}