{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T02:33:57Z","timestamp":1781577237091,"version":"3.54.5"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031206429","type":"print"},{"value":"9783031206436","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,1]],"date-time":"2022-11-01T00:00:00Z","timestamp":1667260800000},"content-version":"vor","delay-in-days":304,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Bit vectors are fundamental building blocks of succinct data structures used in compressed text indices, e.g., in the form of the wavelet trees. Here, two types of queries are of interest: rank and select queries. In practice, the smallest (uncompressed) rank and select data structure cs-poppy has a space overhead of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\approx $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2248<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 3.51\u00a0% [Zhou et al. SEA 2013]\u00a0[26]. Using the same overhead, we present a data structure that can answer queries up to 8\u00a0% (rank) and 16.5\u00a0% (select) faster compared with cs-poppy.<\/jats:p>","DOI":"10.1007\/978-3-031-20643-6_19","type":"book-chapter","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:18:09Z","timestamp":1667222289000},"page":"257-272","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Engineering Compact Data Structures for\u00a0Rank and\u00a0Select Queries on\u00a0Bit Vectors"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2379-9455","authenticated-orcid":false,"given":"Florian","family":"Kurpicz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,11,1]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","unstructured":"Arroyuelo, D., Weitzman, M.: A hybrid compressed data structure supporting rank and select on bit sequences. In: SCCC, pp. 1\u20138. IEEE (2020). https:\/\/doi.org\/10.1109\/SCCC51225.2020.9281244","DOI":"10.1109\/SCCC51225.2020.9281244"},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","first-page":"608","DOI":"10.3390\/a7040608","volume":"7","author":"K Beskers","year":"2014","unstructured":"Beskers, K., Fischer, J.: High-order entropy compressed bit vectors with rank\/select. Algorithms 7(4), 608\u2013620 (2014). https:\/\/doi.org\/10.3390\/a7040608","journal-title":"Algorithms"},{"issue":"3","key":"19_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3524060","volume":"18","author":"A Boffa","year":"2022","unstructured":"Boffa, A., Ferragina, P., Vinciguerra, G.: A learned approach to design compressed rank\/select data structures. ACM Trans. Algorithms 18(3), 1\u201328 (2022). https:\/\/doi.org\/10.1145\/3524060","journal-title":"ACM Trans. Algorithms"},{"key":"19_CR4","unstructured":"Clark, D.R.: Compact pat trees. Ph.D. thesis, University of Waterloo (1997)"},{"key":"19_CR5","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage (extended abstract). In: SODA, pp. 383\u2013391. ACM\/SIAM (1996)"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3457197","volume":"26","author":"P Dinklage","year":"2021","unstructured":"Dinklage, P., Ellert, J., Fischer, J., Kurpicz, F., L\u00f6bel, M.: Practical wavelet tree construction. ACM J. Exp. Algorithmics 26, 1\u201367 (2021). https:\/\/doi.org\/10.1145\/3457197","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"2","key":"19_CR7","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246\u2013260 (1974). https:\/\/doi.org\/10.1145\/321812.321820","journal-title":"J. ACM"},{"key":"19_CR8","unstructured":"Fano, R.M.: On the number of bits required to implement an associative memory (1971)"},{"issue":"8","key":"19_CR9","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/j.ic.2008.12.010","volume":"207","author":"P Ferragina","year":"2009","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The myriad virtues of wavelet trees. Inf. Comput. 207(8), 849\u2013866 (2009). https:\/\/doi.org\/10.1016\/j.ic.2008.12.010","journal-title":"Inf. Comput."},{"key":"19_CR10","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, pp. 390\u2013398. IEEE Computer Society (2000). https:\/\/doi.org\/10.1109\/SFCS.2000.892127","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3375890","volume":"67","author":"T Gagie","year":"2020","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM 67(1), 1\u201354 (2020). https:\/\/doi.org\/10.1145\/3375890","journal-title":"J. ACM"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_28"},{"key":"19_CR13","unstructured":"Gonz\u00e1lez, R., Grabowski, S., M\u00e4kinen, V., Navarro, G.: Practical implementation of rank and select queries. In: WEA, pp. 27\u201338 (2005)"},{"key":"19_CR14","doi-asserted-by":"publisher","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549\u2013554. IEEE Computer Society (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63533","DOI":"10.1109\/SFCS.1989.63533"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/11427186_28","volume-title":"Experimental and Efficient Algorithms","author":"DK Kim","year":"2005","unstructured":"Kim, D.K., Na, J.C., Kim, J.E., Park, K.: Efficient implementation of rank and select functions for succinct representation. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 315\u2013327. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11427186_28"},{"key":"19_CR16","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. III, 2nd Edn. Addison-Wesley (1998)"},{"issue":"2","key":"19_CR17","doi-asserted-by":"publisher","first-page":"585","DOI":"10.2298\/CSIS110606004M","volume":"9","author":"C Makris","year":"2012","unstructured":"Makris, C.: Wavelet trees: a survey. Comput. Sci. Inf. Syst. 9(2), 585\u2013625 (2012). https:\/\/doi.org\/10.2298\/CSIS110606004M","journal-title":"Comput. Sci. Inf. Syst."},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Wavelet trees for all. J. Discrete Algorithms 25, 2\u201320 (2014). https:\/\/doi.org\/10.1016\/j.jda.2013.07.004","journal-title":"J. Discrete Algorithms"},{"key":"19_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-30850-5_26","volume-title":"Experimental Algorithms","author":"G Navarro","year":"2012","unstructured":"Navarro, G., Providel, E.: Fast, small, simple rank\/select on bitmaps. In: Klasing, R. (ed.) SEA 2012. LNCS, vol. 7276, pp. 295\u2013306. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30850-5_26"},{"key":"19_CR20","unstructured":"Pandey, P., Bender, M.A., Johnson, R.: A fast x86 implementation of select. arXiv preprint arXiv:1706.00990 (2017)"},{"key":"19_CR21","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101756","volume":"99","author":"GE Pibiri","year":"2021","unstructured":"Pibiri, G.E., Kanda, S.: Rank\/select queries over mutable bitmaps. Inf. Syst. 99, 101756 (2021). https:\/\/doi.org\/10.1016\/j.is.2021.101756","journal-title":"Inf. Syst."},{"key":"19_CR22","doi-asserted-by":"publisher","unstructured":"Prezza, N.: A framework of dynamic data structures for string processing. In: SEA. LIPIcs, vol. 75, pp. 11:1\u201311:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2017.11","DOI":"10.4230\/LIPIcs.SEA.2017.11"},{"key":"19_CR23","doi-asserted-by":"publisher","unstructured":"Patrascu, M.: Succincter. In: FOCS, pp. 305\u2013313. IEEE Computer Society (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.83","DOI":"10.1109\/FOCS.2008.83"},{"issue":"4","key":"19_CR24","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"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","journal-title":"ACM Trans. Algorithms"},{"key":"19_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-68552-4_12","volume-title":"Experimental Algorithms","author":"S Vigna","year":"2008","unstructured":"Vigna, S.: Broadword implementation of rank\/select queries. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 154\u2013168. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-68552-4_12"},{"key":"19_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-38527-8_15","volume-title":"Experimental Algorithms","author":"D Zhou","year":"2013","unstructured":"Zhou, D., Andersen, D.G., Kaminsky, M.: Space-efficient, high-performance rank and select structures on uncompressed bit sequences. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 151\u2013163. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38527-8_15"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20643-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:20:53Z","timestamp":1667222453000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20643-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206429","9783031206436"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20643-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 November 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Concepci\u00f3n","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2022.inf.udec.cl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"53% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.62","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}