{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:30:47Z","timestamp":1759365047227,"version":"build-2065373602"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T00:00:00Z","timestamp":1757376000000},"content-version":"vor","delay-in-days":8,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["22K11907","23H04378","23K11233"],"award-info":[{"award-number":["22K11907","23H04378","23K11233"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJCR24U4","JPMJCR24U4"],"award-info":[{"award-number":["JPMJCR24U4","JPMJCR24U4"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100021092","name":"University of Yamanashi","doi-asserted-by":"publisher","award":["Wakate Grant Number 2291"],"award-info":[{"award-number":["Wakate Grant Number 2291"]}],"id":[{"id":"10.13039\/100021092","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study succinct variants of B trees in the word RAM model that require <jats:inline-formula>\n              <jats:tex-math>$$s + o(s)$$<\/jats:tex-math>\n            <\/jats:inline-formula> bits of space, where <jats:italic>s<\/jats:italic> is the number of bits essentially needed for storing keys and possibly other satellite values. Assuming that elements are sorted by keys (not necessarily in the order of their integer representations), our B trees support standard operations such as searching, insertion and deletion of elements. In some applications it is useful to associate a satellite value to each element, and to support aggregate operations such as computing the sum of values, the minimum\/maximum value in a given range, or search operations based on those values. We propose a B tree representation storing <jats:italic>n<\/jats:italic> elements in <jats:inline-formula>\n              <jats:tex-math>$$s + \\mathcal {O}(s \/ \\lg n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> bits of space and supporting all mentioned operations in <jats:inline-formula>\n              <jats:tex-math>$$\\mathcal {O}(\\lg n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> time. Operations on integer-ordered keys and satellite values can be accelerated to <jats:inline-formula>\n              <jats:tex-math>$$\\mathcal {O}(\\lg n \/ \\lg \\lg n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> time if we use <jats:inline-formula>\n              <jats:tex-math>$$s + \\mathcal {O}(s \\lg \\lg n \/ \\lg n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> bits of space. The time is retained for special kind of aggregate functions that can be computed bit-parallel in constant time. For integer-ordered keys, we can also compress the space <jats:italic>s<\/jats:italic> to match compression measures using difference encoding of the keys while retaining the operational time complexities. For the last enhancement, we allow us to pre-compute tables of <jats:inline-formula>\n              <jats:tex-math>$$o(n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> bits.<\/jats:p>","DOI":"10.1007\/s00224-025-10238-7","type":"journal-article","created":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T11:11:51Z","timestamp":1757416311000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient B Trees via Load-Balancing"],"prefix":"10.1007","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9106-6192","authenticated-orcid":false,"given":"Tomohiro","family":"I","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3470-9187","authenticated-orcid":false,"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[]},{"given":"Sohei","family":"Yamaguchi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,9]]},"reference":[{"issue":"9","key":"10238_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"10238_CR2","doi-asserted-by":"crossref","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indexes. In Proc. SIGFIDET, pp. 107\u2013141 (1970)","DOI":"10.1145\/1734663.1734671"},{"issue":"11","key":"10238_CR3","doi-asserted-by":"publisher","first-page":"3207","DOI":"10.1007\/s00453-017-0380-7","volume":"80","author":"P Bille","year":"2018","unstructured":"Bille, P., Christiansen, A.R., Cording, P.H., G\u00f8rtz, I.L., Skjoldjensen, F.R., Vildh\u00f8j, H.W., Vind, S.: Dynamic relative compression, dynamic partial sums, and substring concatenation. Algorithmica 80(11), 3207\u20133224 (2018)","journal-title":"Algorithmica"},{"key":"10238_CR4","unstructured":"Blandford, D.K., Blelloch, G.E.: Compact representations of ordered sets. In Proc. SODA, pp. 11\u201319 (2004)"},{"issue":"2","key":"10238_CR5","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D Comer","year":"1979","unstructured":"Comer, D.: The ubiquitous B-tree. ACM Comput. Surv. 11(2), 121\u2013137 (1979)","journal-title":"ACM Comput. Surv."},{"key":"10238_CR6","doi-asserted-by":"crossref","unstructured":"Delpratt, O., Rahman, N., Raman, R.: Compressed prefix sums. In Proc. SOFSEM, volume 4362 of LNCS, pp. 235\u2013247 (2007)","DOI":"10.1007\/978-3-540-69507-3_19"},{"key":"10238_CR7","doi-asserted-by":"crossref","unstructured":"Dietz, P.F.: Optimal algorithms for list indexing and subset rank. In Proc. WADS, volume 382 of LNCS, pp. 39\u201346 (1989)","DOI":"10.1007\/3-540-51542-9_5"},{"issue":"2","key":"10238_CR8","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)","journal-title":"J. ACM"},{"issue":"2","key":"10238_CR9","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"24","key":"10238_CR10","doi-asserted-by":"publisher","first-page":"2668","DOI":"10.1016\/j.tcs.2010.10.030","volume":"412","author":"A Farzan","year":"2011","unstructured":"Farzan, A., Munro, J.I.: Succinct representation of dynamic trees. Theor. Comput. Sci. 412(24), 2668\u20132678 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10238_CR11","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: A new data structure for string search in external memory and its applications. J. ACM 46(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"issue":"2","key":"10238_CR12","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00224-005-1167-9","volume":"39","author":"G Franceschini","year":"2006","unstructured":"Franceschini, G., Grossi, R.: Optimal implicit dictionaries over unbounded universes. Theory Comput. Syst. 39(2), 321\u2013345 (2006)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"10238_CR13","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"ML Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"43","key":"10238_CR14","doi-asserted-by":"publisher","first-page":"4414","DOI":"10.1016\/j.tcs.2009.07.022","volume":"410","author":"R Gonz\u00e1lez","year":"2009","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Rank\/select on dynamic compressed sequences and applications. Theor. Comput. Sci. 410(43), 4414\u20134422 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10238_CR15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1561\/1900000028","volume":"3","author":"G Graefe","year":"2011","unstructured":"Graefe, G.: Modern B-tree techniques. Found. Trends Databases 3(4), 203\u2013402 (2011)","journal-title":"Modern B-tree techniques. Found. Trends Databases"},{"key":"10238_CR16","doi-asserted-by":"crossref","unstructured":"He, M., Munro, J.I.: Succinct representations of dynamic strings. In Proc. SPIRE, volume 6393 of LNCS, pp. 334\u2013346 (2010)","DOI":"10.1007\/978-3-642-16321-0_35"},{"key":"10238_CR17","doi-asserted-by":"crossref","unstructured":"I, T., K\u00f6ppl, D.: Space-efficient B trees via load-balancing. In Proc. IWOCA, volume 13270 of LNCS, pp. 327\u2013340 (2022)","DOI":"10.1007\/978-3-031-06678-8_24"},{"issue":"1","key":"10238_CR18","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1109\/COMST.2014.2354398","volume":"17","author":"P Jesus","year":"2015","unstructured":"Jesus, P., Baquero, C., Almeida, P.S.: A survey of distributed data aggregation algorithms. IEEE Commun. Surv. Tutorials 17(1), 381\u2013404 (2015)","journal-title":"IEEE Commun. Surv. Tutorials"},{"issue":"23","key":"10238_CR19","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1016\/j.ipl.2010.08.007","volume":"110","author":"J Katajainen","year":"2010","unstructured":"Katajainen, J., Rao, S.S.: A compact data structure for representing a dynamic multiset. Inf. Process. Lett. 110(23), 1061\u20131066 (2010)","journal-title":"Inf. Process. Lett."},{"key":"10238_CR20","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting and Searching. Addison Wesley, Redwood City, CA, USA (1998)"},{"key":"10238_CR21","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Nekrich, Y.: Compressed data structures for dynamic sequences. In Proc. ESA, volume 9294 of LNCS, pp. 891\u2013902 (2015)","DOI":"10.1007\/978-3-662-48350-3_74"},{"issue":"5","key":"10238_CR22","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1137\/130908245","volume":"43","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. SIAM J. Comput. 43(5), 1781\u20131806 (2014)","journal-title":"SIAM J. Comput."},{"key":"10238_CR23","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Dynamic integer sets with optimal rank, select, and predecessor search. In Proc. FOCS pp. 166\u2013175 (2014)","DOI":"10.1109\/FOCS.2014.26"},{"key":"10238_CR24","unstructured":"Prezza, N.: A framework of dynamic data structures for string processing. In Proc. SEA, volume\u00a075 of LIPIcs, pp. 11:1\u201311:15 (2017)"},{"key":"10238_CR25","doi-asserted-by":"crossref","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In Proc. ICALP, volume 2719 of LNCS, pp. 357\u2013368 (2003)","DOI":"10.1007\/3-540-45061-0_30"},{"key":"10238_CR26","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct dynamic data structures. In Proc. WADS, volume 2125 of LNCS, pp. 426\u2013437 (2001)","DOI":"10.1007\/3-540-44634-6_39"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10238-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10238-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10238-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T05:21:09Z","timestamp":1759296069000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10238-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10238"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10238-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,9]]},"assertion":[{"value":"28 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"32"}}