{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:55:12Z","timestamp":1725854112490},"publisher-location":"New York, NY","reference-count":33,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_61","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:32:23Z","timestamp":1553095943000},"page":"261-264","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cache-Oblivious B-Tree"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"61_CR31","doi-asserted-by":"crossref","unstructured":"Afshani P, Zeh N (2011) Improved space bounds for cache-oblivious range reporting. In: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, San Francisco, pp\u00a01745\u20131758","DOI":"10.1137\/1.9781611973082.134"},{"key":"61_CR32","doi-asserted-by":"crossref","unstructured":"Afshani P, Hamilton CH, Zeh N (2010) A general approach for cache-oblivious range reporting and approximate range counting. Comput Geom 43(8):700\u2013712. Conference version appeared at SoCG 2009","DOI":"10.1016\/j.comgeo.2010.04.003"},{"key":"61_CR33","doi-asserted-by":"crossref","unstructured":"Afshani P, Hamilton CH, Zeh N (2011) Cache-oblivious range reporting with optimal queries requires superlinear space. Discret Comput Geom 45(4):824\u2013850. Conference version appeared at SoCG 2009","DOI":"10.1007\/s00454-011-9347-7"},{"issue":"9","key":"61_CR34","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal A, Vitter JS (1988) The input\/output complexity of sorting and related problems. Commun ACM 31(9):1116\u20131127","journal-title":"Commun ACM"},{"issue":"6","key":"61_CR35","doi-asserted-by":"publisher","first-page":"1488","DOI":"10.1137\/S009753970240481X","volume":"32","author":"L Arge","year":"2003","unstructured":"Arge L, Vitter JS (2003) Optimal external memory interval management. SIAM J Comput 32(6):1488\u20131508","journal-title":"SIAM J Comput"},{"key":"61_CR36","doi-asserted-by":"crossref","unstructured":"Arge L, Zeh N (2006) Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching. In: Proceedings of the 22nd ACM symposium on computational geometry, Sedona, pp\u00a0158\u2013166","DOI":"10.1145\/1137856.1137883"},{"key":"61_CR37","doi-asserted-by":"crossref","unstructured":"Arge L, de\u00a0Berg M, Haverkort HJ (2005) Cache-oblivious R-trees. In: Proceedings of the 21st ACM symposium on computational geometry, Pisa, pp\u00a0170\u2013179","DOI":"10.1145\/1064092.1064120"},{"key":"61_CR38","volume-title":"Handbook on data structures and applications","author":"L Arge","year":"2005","unstructured":"Arge L, Brodal GS, Fagerberg R (2005) Cache-oblivious data structures. In: Mehta D, Sahni S (eds) Handbook on data structures and applications. CRC, Boca Raton"},{"key":"61_CR39","doi-asserted-by":"crossref","unstructured":"Arge L, Brodal GS, Fagerberg R, Laustsen M (2005) Cache-oblivious planar orthogonal range searching and counting. In: Proceedings of the 21st ACM symposium on computational geometry, Pisa, pp\u00a0160\u2013169","DOI":"10.1145\/1064092.1064119"},{"key":"61_CR310","doi-asserted-by":"crossref","unstructured":"Bender M, Cole R, Demaine E, Farach-Colton M (2002) Scanning and traversing: maintaining data for traversals in a memory hierarchy. In: Proceedings of the 10th annual European symposium on algorithms, Rome. LNCS, vol\u00a02461, pp\u00a0139\u2013151","DOI":"10.1007\/3-540-45749-6_16"},{"key":"61_CR311","doi-asserted-by":"crossref","unstructured":"Bender M, Cole R, Raman R (2002) Exponential structures for cache-oblivious algorithms. In: Proceedings of the 29th international colloquium on automata, languages, and programming, M\u00e1laga. LNCS, vol\u00a02380, pp\u00a0195\u2013207","DOI":"10.1007\/3-540-45465-9_18"},{"key":"61_CR312","doi-asserted-by":"crossref","unstructured":"Bender MA, Duan Z, Iacono J, Wu J (2004) A locality-preserving cache-oblivious dynamic dictionary. J Algorithms 53(2):115\u2013136. Conference version appeared at SODA 2002","DOI":"10.1016\/j.jalgor.2004.04.014"},{"key":"61_CR313","doi-asserted-by":"crossref","unstructured":"Bender MA, Demaine ED, Farach-Colton M (2005) Cache-oblivious B-trees. SIAM J Comput 35(2):341\u2013358. Conference version appeared at FOCS 2000","DOI":"10.1137\/S0097539701389956"},{"key":"61_CR314","doi-asserted-by":"crossref","unstructured":"Bender MA, Fineman JT, Gilbert S, Kuszmaul BC (2005) Concurrent cache-oblivious B-trees. In: Proceedings of the 17th annual ACM symposium on parallelism in algorithms and architectures, Las Vegas, pp\u00a0228\u2013237","DOI":"10.1145\/1073970.1074009"},{"key":"61_CR315","doi-asserted-by":"crossref","unstructured":"Bender MA, Farach-Colton M, Kuszmaul BC (2006) Cache-oblivious string B-trees. In: Proceedings of the 25th ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, Chicago, pp\u00a0233\u2013242","DOI":"10.1145\/1142351.1142385"},{"key":"61_CR316","doi-asserted-by":"crossref","unstructured":"Bender MA, Farach-Colton M, Fineman JT, Fogel YR, Kuszmaul BC, Nelson J (2007) Cache-oblivious streaming B-trees. In: Proceedings of the 19th annual ACM symposium on parallelism in algorithms and architectures, San Diego, pp\u00a081\u201392","DOI":"10.1145\/1248377.1248393"},{"key":"61_CR317","doi-asserted-by":"crossref","unstructured":"Bender MA, Brodal GS, Fagerberg R, Ge D, He S, Hu H, Iacono J, L\u00f3pez-Ortiz A (2011) The cost of cache-oblivious searching. Algorithmica 61(2):463\u2013505. Conference version appeared at FOCS 2003","DOI":"10.1007\/s00453-010-9394-0"},{"key":"61_CR318","doi-asserted-by":"crossref","unstructured":"Brodal GS, Fagerberg R (2006) Cache-oblivious string dictionaries. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms, Miami, pp\u00a0581\u2013590","DOI":"10.1145\/1109557.1109621"},{"key":"61_CR319","unstructured":"Brodal GS, Kejlberg-Rasmussen C (2012) Cache-oblivious implicit predecessor dictionaries with the working set property. In: Proceedings of the 29th annual symposium on theoretical aspects of computer science, Paris. Leibniz international proceedings in informatics, vol\u00a014, pp 112\u2013123"},{"key":"61_CR320","unstructured":"Brodal GS, Fagerberg R, Jacob R (2002) Cache-oblivious search trees via binary trees of small height. In: Proceedings of the 13th annual ACM-SIAM symposium on discrete algorithms, San Francisco, pp\u00a039\u201348"},{"key":"61_CR321","doi-asserted-by":"crossref","unstructured":"Brodal GS, Demaine ED, Fineman JT, Iacono J, Langerman S, Munro JI (2010) Cache-oblivious dynamic dictionaries with update\/query tradeoffs. In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, Austin, pp 1448\u20131456","DOI":"10.1137\/1.9781611973075.117"},{"key":"61_CR322","doi-asserted-by":"crossref","unstructured":"Ferragina P (2013) On the weak prefix-search problem. Theor Comput Sci 483:75\u201384. Conference version appeared at CPM 2011","DOI":"10.1016\/j.tcs.2012.06.011"},{"key":"61_CR323","doi-asserted-by":"crossref","unstructured":"Ferragina P, Venturini R (2013) Compressed cache-oblivious string B-tree. In: Proceedings of the algorithms \u2013 ESA 2013 \u2013 21st annual European symposium, Sophia Antipolis. LNCS, vol\u00a08125, pp\u00a0469\u2013480","DOI":"10.1007\/978-3-642-40450-4_40"},{"key":"61_CR324","doi-asserted-by":"crossref","unstructured":"Ferragina P, Grossi R, Gupta A, Shah R, Vitter JS (2008) On searching compressed string collections cache-obliviously. In: Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, Vancouver, pp\u00a0181\u2013190","DOI":"10.1145\/1376916.1376943"},{"key":"61_CR325","doi-asserted-by":"crossref","unstructured":"Franceschini G, Grossi R (2003) Optimal worst-case operations for implicit cache-oblivious search trees. In: Proceedings of the 8th international workshop on algorithms and data structures (WADS), Ottawa. LNCS, vol\u00a02748, pp\u00a0114\u2013126","DOI":"10.1007\/978-3-540-45078-8_11"},{"key":"61_CR326","doi-asserted-by":"crossref","unstructured":"Frigo M, Leiserson CE, Prokop H, Ramachandran S (2012) Cache-oblivious algorithms. ACM Trans Algorithms 8(1):4. Conference version appeared at FOCS 1999","DOI":"10.1145\/2071379.2071383"},{"key":"61_CR327","doi-asserted-by":"crossref","unstructured":"Hon W, Lam TW, Shah R, Tam S, Vitter JS (2011) Cache-oblivious index for approximate string matching. Theor Comput Sci 412(29):3579\u20133588. Conference version appeared at CPM 2007","DOI":"10.1016\/j.tcs.2011.03.004"},{"key":"61_CR328","first-page":"417","volume":"115","author":"A Itai","year":"1981","unstructured":"Itai A, Konheim AG, Rodeh M (1981) A sparse table implementation of priority queues. In: 8th International colloquium on Automata, languages and programming, Acre (Akko). LNCS, vol\u00a0115, pp\u00a0417\u2013431","journal-title":"LNCS, vol"},{"key":"61_CR329","doi-asserted-by":"crossref","unstructured":"Ladner RE, Fortna R, Nguyen BH (2002) A comparison of cache aware and cache oblivious static search trees using program instrumentation. In: Experimental algorithmics. LNCS, Springer-Verlag, Berlin\/Heidelberg, vol 2547, pp 78\u201392","DOI":"10.1007\/3-540-36383-1_4"},{"key":"61_CR330","doi-asserted-by":"crossref","unstructured":"Lindstrom P, Rajan D (2014) Optimal hierarchical layouts for cache-oblivious search trees. In: IEEE 30th international conference on data engineering, Chicago, pp 616\u2013627","DOI":"10.1109\/ICDE.2014.6816686"},{"key":"61_CR331","doi-asserted-by":"crossref","unstructured":"Pagh R, Wei Z, Yi K, Zhang Q (2014) Cache-oblivious hashing. Algorithmica 69(4):864\u2013883. Conference version appeared at PODS 2010","DOI":"10.1007\/s00453-013-9763-6"},{"key":"61_CR332","volume-title":"Cache-oblivious algorithms","author":"H Prokop","year":"1999","unstructured":"Prokop H (1999) Cache-oblivious algorithms. Master\u2019s thesis, Massachusetts Institute of Technology"},{"key":"61_CR333","doi-asserted-by":"crossref","unstructured":"Rahman N, Cole R, Raman R (2001) Optimised predecessor data structures for internal memory. In: Proceedings of the algorithm engineering, 5th international workshop (WAE), Aarhus. LNCS, vol\u00a02141, pp\u00a067\u201378","DOI":"10.1007\/3-540-44688-5_6"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_61","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:24:17Z","timestamp":1553099057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_61","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}