{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T22:51:19Z","timestamp":1768344679684,"version":"3.49.0"},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Computer Journal"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1093\/comjnl\/bxv090","type":"journal-article","created":{"date-parts":[[2015,11,6]],"date-time":"2015-11-06T01:08:17Z","timestamp":1446772097000},"page":"630-649","source":"Crossref","is-referenced-by-count":5,"title":["Cache-Sensitive Memory Layout for Dynamic Binary Trees"],"prefix":"10.1093","volume":"59","author":[{"given":"Riku","family":"Saikkonen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eljas","family":"Soisalon-Soininen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,11,4]]},"reference":[{"key":"2016060203540689000_59.5.630.1","doi-asserted-by":"crossref","unstructured":"Rao J. and Ross K.A. (2000) Making B $^+$ -Trees Cache Conscious in Main Memory. 2000 ACM SIGMOD Int. Conf. Management of Data, Dallas, TX, USA, May 16\u201318, pp. 475\u2013486. ACM Press, New York.","DOI":"10.1145\/342009.335449"},{"key":"2016060203540689000_59.5.630.2","doi-asserted-by":"crossref","unstructured":"Hankins R.A. and Patel J.M. (2003) Effect of Node Size on the Performance of Cache-Conscious B $^+$ -Trees. 2003 ACM SIGMETRICS Int. Conf. Measurement and Modeling of Computer Systems, San Diego, CA, USA, June 10\u201314, pp. 283\u2013294. ACM Press, New York.","DOI":"10.1145\/781027.781063"},{"key":"2016060203540689000_59.5.630.3","unstructured":"Rao J. and Ross K.A. (1999) Cache Conscious Indexing for Decision-Support in Main Memory. 25th Int. Conf. Very Large Data Bases (VLDB 1999), Edinburgh, Scotland, UK, September 7\u201310, pp. 78\u201389. Morgan Kaufmann, Burlington."},{"key":"2016060203540689000_59.5.630.4","doi-asserted-by":"crossref","unstructured":"Bender M.A. , Demaine E.D. and Farach-Colton M. (2002) Efficient Tree Layout in a Multilevel Memory Hierarchy. 10th Annual European Symp. Algorithms (ESA 2002), Rome, Italy, September 17\u201321, Lecture Notes in Computer Science 2461, pp. 165\u2013173. Springer, Berlin.","DOI":"10.1007\/3-540-45749-6_18"},{"key":"2016060203540689000_59.5.630.5","first-page":"143","article-title":"Making T-trees cache conscious on commodity microprocessors","volume":"27","author":"Lee","year":"2011","journal-title":"J. Inf. Sci. Eng."},{"key":"2016060203540689000_59.5.630.6","doi-asserted-by":"crossref","unstructured":"Soisalon-Soininen E. and Widmayer P. (1999) Concurrency and Recovery in Full-Text Indexing. String Processing and Information Retrieval Symposium (SPIRE 1999), Cancun, Mexico, September 21\u201324, pp. 192\u2013198. IEEE Computer Society, Washington, DC.","DOI":"10.1109\/SPIRE.1999.796595"},{"key":"2016060203540689000_59.5.630.7","unstructured":"Bernstein P.A. , Reid C.W. and Das S. (2011) Hyder \u2013 A Transactional Record Manager for Shared Flash. 5th Biennial Conf. Innovative Data Systems Research (CIDR 2011), Asilomar, CA, USA, January 9\u201312, pp. 9\u201320."},{"key":"2016060203540689000_59.5.630.8","doi-asserted-by":"crossref","unstructured":"Haeupler B. , Sen S. and Tarjan R.E. (2009) Rank-Balanced Trees. 11th Algorithms and Data Structures Symposium (WADS 2009), Banff, Canada, August 21\u201323, Lecture Notes in Computer Science 5664, pp. 351\u2013362. Springer, Berlin.","DOI":"10.1007\/978-3-642-03367-4_31"},{"key":"2016060203540689000_59.5.630.9","doi-asserted-by":"crossref","unstructured":"Soisalon-Soininen E. and Widmayer P. (2003) Single and Bulk Updates in Stratified Trees: An Amortized and Worst-Case Analysis. Computer Science in Perspective: Essays Dedicated to Thomas Ottmann, Lecture Notes in Computer Science 2598, pp. 278\u2013292. Springer, Berlin.","DOI":"10.1007\/3-540-36477-3_21"},{"key":"2016060203540689000_59.5.630.10","unstructured":"Transaction Processing Performance Council (2010) TPC benchmark C. Standard Specification, Revision 5.11."},{"key":"2016060203540689000_59.5.630.11","unstructured":"Oksanen K. and Malmi L. (1995) Memory reference locality and periodic relocation in main memory search trees. 5th Hellenic Conf. Informatics. Greek Computer Society."},{"key":"2016060203540689000_59.5.630.12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1014"},{"key":"2016060203540689000_59.5.630.13","doi-asserted-by":"crossref","unstructured":"Saikkonen R. and Soisalon-Soininen E. (2008) Cache-sensitive memory layout for binary trees. 5th IFIP Int. Conf. Theoretical Computer Science (IFIP TCS 2008), Milan, Italy, September 8\u201310, IFIP International Federation for Information Processing 273, pp. 241\u2013255. Springer, Berlin.","DOI":"10.1007\/978-0-387-09680-3_17"},{"key":"2016060203540689000_59.5.630.14","unstructured":"Saikkonen R. (2009) Bulk Updates and Cache Sensitivity in Search Trees. PhD Thesis, Helsinki University of Technology."},{"key":"2016060203540689000_59.5.630.15","doi-asserted-by":"publisher","DOI":"10.1145\/359970.359989"},{"key":"2016060203540689000_59.5.630.16","doi-asserted-by":"crossref","unstructured":"Chen S. , Gibbons P.B. and Mowry T.C. (2001) Improving Index Performance Through Prefetching. 2001 ACM SIGMOD Int. Conf. Management of Data, Santa Barbara, CA, USA, May 21\u201324, pp. 235\u2013246. ACM Press, New York.","DOI":"10.1145\/375663.375688"},{"key":"2016060203540689000_59.5.630.17","doi-asserted-by":"crossref","unstructured":"Bohannon P. , McIlroy P. and Rastogi R. (2001) Main-memory Index Structures with Fixed-size Partial Keys. 2001 ACM SIGMOD Int. Conf. Management of Data, Santa Barbara, CA, USA, May 21\u201324, pp. 163\u2013174. ACM Press, New York.","DOI":"10.1145\/375663.375681"},{"key":"2016060203540689000_59.5.630.18","doi-asserted-by":"crossref","unstructured":"Jin R. and Chung T.-S. (2010) Node Compression Techniques Based on Cache-Sensitive ${\\rm B}^+$ -Tree. 9th IEEE\/ACIS Int. Conf. Computer and Information Science (ICIS 2010), Yamagata, Japan, August 18\u201320, pp. 133\u2013138. IEEE Computer Society, Washington, DC.","DOI":"10.1109\/ICIS.2010.9"},{"key":"2016060203540689000_59.5.630.19","doi-asserted-by":"crossref","unstructured":"Lee I. , Shim J. , Lee S. and Chun J. (2007) CST-trees: Cache sensitive T-trees. 12th Int. Conf. Database Systems for Advanced Applications (DASFAA 2007), Bangkok, Thailand, April 9\u201312, Lecture Notes in Computer Science 4443, pp. 398\u2013409. Springer, Berlin.","DOI":"10.1007\/978-3-540-71703-4_35"},{"key":"2016060203540689000_59.5.630.20","doi-asserted-by":"crossref","unstructured":"Kim K. , Shim J. and Lee I. (2007) Cache Conscious Trees: How do they Perform on Contemporary Commodity Microprocessors. 5th Int. Conf. Computational Science and its Applications (ICCSA 2007), Kuala Lumpur, Malaysia, August 26\u201329, Lecture Notes in Computer Science 4705, pp. 189\u2013200. Springer, Berlin.","DOI":"10.1007\/978-3-540-74472-6_15"},{"key":"2016060203540689000_59.5.630.21","doi-asserted-by":"crossref","unstructured":"Rahman N. , Cole R. and Raman R. (2001) Optimised Predecessor Data Structures for Internal Memory. 5th Workshop on Algorithm Engineering (WAE 2001), Aarhus, Denmark, August 28\u201331, pp. Lecture Notes in Computer Science 2141, pp. 67\u201378. Springer, Berlin.","DOI":"10.1007\/3-540-44688-5_6"},{"key":"2016060203540689000_59.5.630.22","doi-asserted-by":"crossref","unstructured":"Chen S. , Gibbons P.B. , Mowry T.C. and Valentin G. (2002) Fractal Prefetching B $^+$ -trees: Optimizing Both Cache and Disk Performance. 2002 ACM SIGMOD Int. Conf. Management of Data, Madison, WI, USA, June 2\u20136, pp. 157\u2013168. ACM Press, New York.","DOI":"10.1145\/564691.564710"},{"key":"2016060203540689000_59.5.630.23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389956"},{"key":"2016060203540689000_59.5.630.24","doi-asserted-by":"crossref","unstructured":"Brodal G.S. , Fagerberg R. and Jacob R. (2002) Cache Oblivious Search Trees via Binary Trees of Small Height. 13th Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2002), San Francisco, CA, January 6\u20138, pp. 39\u201348. Society for Industrial and Applied Mathematics, Philadelphia.","DOI":"10.7146\/brics.v8i36.21696"},{"key":"2016060203540689000_59.5.630.25","unstructured":"Bender M. A. , Duan Z. , Iacono J. and Wu J. (2002) A Locality-Preserving Cache-Oblivious Dynamic Dictionary. 13th Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2002), San Francisco, CA, USA, January 6\u20138, pp. 29\u201338. Society for Industrial and Applied Mathematics, Philadelphia."},{"key":"2016060203540689000_59.5.630.26","doi-asserted-by":"crossref","unstructured":"Bender M.A. , Farach-Colton M. and Kuszmaul B. C. (2006) Cache-Oblivious String B-Trees. 25th ACM SIGACT\u2013SIGMOD\u2013SIGART Symp. Principles of Database Systems (PODS 2006), Chicago, IL, USA, June 26\u201328, pp. 233\u2013242. ACM Press, New York.","DOI":"10.1145\/1142351.1142385"},{"key":"2016060203540689000_59.5.630.27","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1137\/S009753970240481X","article-title":"Optimal external memory interval management","volume":"22","author":"Arge","year":"2003","journal-title":"SIAM J. Comput."},{"key":"2016060203540689000_59.5.630.28","doi-asserted-by":"crossref","unstructured":"Itai A. , Konheim A.G. and Rodeh M. (1981) A Sparse Table Implementation of Priority Queues. 8th Colloquium on Automata, Languages and Programming (ICALP 1981), Acre, Israel, July 13\u201317, Lecture Notes in Computer Science 115, pp. 417\u2013431. Springer, Berlin.","DOI":"10.1007\/3-540-10843-2_34"},{"key":"2016060203540689000_59.5.630.29","unstructured":"Kasheff Z. (2004) Cache-oblivious dynamic search trees. Master's Thesis, Massachusetts Institute of Technology."},{"key":"2016060203540689000_59.5.630.30","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"2016060203540689000_59.5.630.31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"2016060203540689000_59.5.630.32","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"2016060203540689000_59.5.630.33","doi-asserted-by":"crossref","unstructured":"Bender M.A. , Brodal G.S. , Fagerberg R. , Ge D. , He S. , Hu H. , Iacono J. and L\u00f3pez-Ortiz A. (2003) The Cost of Cache-Oblivious Searching. 44th Annual IEEE Symp. Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, October 11\u201314, pp. 271\u2013282. IEEE Computer Society, Washington, DC.","DOI":"10.1109\/SFCS.2003.1238201"},{"key":"2016060203540689000_59.5.630.34","doi-asserted-by":"crossref","unstructured":"He B. and Luo Q. (2008) Cache-oblivious databases: limitations and opportunities. ACM Trans. Database Syst., 33, doi:10.1145\/1366102.1366105 .","DOI":"10.1145\/1366102.1366105"},{"key":"2016060203540689000_59.5.630.35","doi-asserted-by":"crossref","unstructured":"Jiang W. , Ding C. and Cheng R. (2004) Memory Access Analysis and Optimization Approaches on Splay Trees. 7th Workshop on Languages, Compilers and Run-time Support for Scalable Systems (LCR 2004), Houston, TX, USA, October 21\u201323, pp. 1\u20136. ACM Press, New York.","DOI":"10.1145\/1066650.1066655"},{"key":"2016060203540689000_59.5.630.36","doi-asserted-by":"crossref","unstructured":"Chilimbi T.M. , Hill M.D. and Larus J.R. (1999) Cache-Conscious Structure Layout. ACM SIGPLAN 1999 Conf. Programming Language Design and Implementation, Atlanta, GA, USA, May 1\u20134, pp. 1\u201312. ACM Press, New York.","DOI":"10.1145\/301618.301633"},{"key":"2016060203540689000_59.5.630.37","doi-asserted-by":"crossref","unstructured":"Askitis N. and Zobel J. (2011) Redesigning the string hash table, burst trie, and BST to exploit cache. ACM J. Exp. Algorithmics, 15, doi:10.1145\/1671970.1921704 .","DOI":"10.1145\/1671970.1921704"},{"key":"2016060203540689000_59.5.630.38","doi-asserted-by":"crossref","unstructured":"Bronson N.G. , Casper J. , Chafi H. and Olukotun K. (2010) A Practical Concurrent Binary Search Tree. 15th ACM SIGPLAN Symp. Principles and Practice of Parallel Programming, Bangalore, India, January 9\u201314, pp. 257\u2013268. ACM Press, New York.","DOI":"10.1145\/1693453.1693488"},{"key":"2016060203540689000_59.5.630.39","doi-asserted-by":"crossref","unstructured":"Graefe G. (2004) Write-Optimized B-Trees. 30th Int. Conf. Very Large Data Bases (VLDB 2004), Toronto, Canada, August 31\u2013September 3, pp. 672\u2013683. Morgan Kaufmann, Burlington.","DOI":"10.1016\/B978-012088469-8.50060-7"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/59\/5\/630\/7903009\/bxv090.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,1]],"date-time":"2019-09-01T09:02:38Z","timestamp":1567328558000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article-lookup\/doi\/10.1093\/comjnl\/bxv090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,4]]},"references-count":39,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2016,5,10]]},"published-print":{"date-parts":[[2016,5]]}},"alternative-id":["10.1093\/comjnl\/bxv090"],"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxv090","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,4]]}}}