{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:32Z","timestamp":1750308812932,"version":"3.41.0"},"reference-count":138,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>A key decision when developing in-memory computing applications is choice of a mechanism to store and retrieve strings. The most efficient current data structures for this task are the hash table with move-to-front chains and the burst trie, both of which use linked lists as a substructure, and variants of binary search tree. These data structures are computationally efficient, but typical implementations use large numbers of nodes and pointers to manage strings, which is not efficient in use of cache. In this article, we explore two alternatives to the standard representation: the simple expedient of including the string in its node, and, for linked lists, the more drastic step of replacing each list of nodes by a contiguous array of characters. Our experiments show that, for large sets of strings, the improvement is dramatic. For hashing, in the best case the total space overhead is reduced to less than 1 bit per string. For the burst trie, over 300MB of strings can be stored in a total of under 200MB of memory with significantly improved search time. These results, on a variety of data sets, show that cache-friendly variants of fundamental data structures can yield remarkable gains in performance.<\/jats:p>","DOI":"10.1145\/1671970.1921704","type":"journal-article","created":{"date-parts":[[2012,10,12]],"date-time":"2012-10-12T19:06:47Z","timestamp":1350068807000},"source":"Crossref","is-referenced-by-count":5,"title":["Redesigning the string hash table, burst trie, and BST to exploit cache"],"prefix":"10.1145","volume":"15","author":[{"given":"Nikolas","family":"Askitis","sequence":"first","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Zobel","sequence":"additional","affiliation":[{"name":"NICTA, University of Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,2,7]]},"reference":[{"volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments. SIAM","author":"Acharya A.","key":"e_1_2_1_1_1","unstructured":"Acharya , A. , Zhu , H. , and Shen , K . 1999. Adaptive algorithms for cache-efficient trie search . In Proceedings of the Workshop on Algorithm Engineering and Experiments. SIAM , Philadelphia, PA, 296--311. Acharya, A., Zhu, H., and Shen, K. 1999. Adaptive algorithms for cache-efficient trie search. In Proceedings of the Workshop on Algorithm Engineering and Experiments. SIAM, Philadelphia, PA, 296--311."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233336"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/512429.512450"},{"key":"e_1_2_1_4_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms 1st Ed. Addison-Wesley Boston MA.   Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms 1st Ed. Addison-Wesley Boston MA."},{"key":"e_1_2_1_5_1","unstructured":"Allen R. and Kennedy K. 2001. Optimizing Compilers for Modern Architectures. Morgan Kaufmann San Francisco CA.   Allen R. and Kennedy K. 2001. Optimizing Compilers for Modern Architectures. Morgan Kaufmann San Francisco CA."},{"volume-title":"Proceedings of the Cache-Oblivious and Cache-Aware Algorithms Seminar. Schloss Dagstuhl","author":"Arge L.","key":"e_1_2_1_6_1","unstructured":"Arge , L. , Bender , M. A. , Demaine , E. , Leiserson , C. , and Mehlhorn , K . 2005. Abstracts collection . In Proceedings of the Cache-Oblivious and Cache-Aware Algorithms Seminar. Schloss Dagstuhl , Wadern, Germany. Arge, L., Bender, M. A., Demaine, E., Leiserson, C., and Mehlhorn, K. 2005. Abstracts collection. In Proceedings of the Cache-Oblivious and Cache-Aware Algorithms Seminar. Schloss Dagstuhl, Wadern, Germany."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509950"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Arge L. Brodal G. and Fagerberg R. 2005. Cache-oblivious data structures. In Handbook on Data Structures and Applications D. P. Mehta and S. Sahni Eds. CRC Press Boca Raton FL 34--41.  Arge L. Brodal G. and Fagerberg R. 2005. Cache-oblivious data structures. In Handbook on Data Structures and Applications D. P. Mehta and S. Sahni Eds. CRC Press Boca Raton FL 34--41.","DOI":"10.1201\/9781420035179.ch34"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 32nd Australasian Computer Science Conference. Australian Computer Society","author":"Askitis N.","year":"2009","unstructured":"Askitis , N. 2009 . Fast and compact hash tables for integer keys . In Proceedings of the 32nd Australasian Computer Science Conference. Australian Computer Society , Sydney, Australia, 101--110. Askitis, N. 2009. Fast and compact hash tables for integer keys. In Proceedings of the 32nd Australasian Computer Science Conference. Australian Computer Society, Sydney, Australia, 101--110."},{"volume-title":"Proceedings of the of the 30th Australasian Computer Science Conference. Australian Computer Society","author":"Askitis N.","key":"e_1_2_1_11_1","unstructured":"Askitis , N. and Sinha , R . 2007. HAT-trie: A cache-conscious trie-based data structure for strings . In Proceedings of the of the 30th Australasian Computer Science Conference. Australian Computer Society , Sydney, Australia, 97--105. Askitis, N. and Sinha, R. 2007. HAT-trie: A cache-conscious trie-based data structure for strings. In Proceedings of the of the 30th Australasian Computer Science Conference. Australian Computer Society, Sydney, Australia, 97--105."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0183-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_11"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0094-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/197405.197406"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/377792.377906"},{"key":"e_1_2_1_17_1","first-page":"7","article-title":"The efficacy of software prefetching and locality optimizations on future memory systems","volume":"6","author":"Badawy A. A.","year":"2004","unstructured":"Badawy , A. A. , Aggarwal , A. , Yeung , D. , and Tseng , C. 2004 . The efficacy of software prefetching and locality optimizations on future memory systems . J. Instruct. Level Parall. 6 , 7 . Badawy, A. A., Aggarwal, A., Yeung, D., and Tseng, C. 2004. The efficacy of software prefetching and locality optimizations on future memory systems. J. Instruct. Level Parall. 6, 7.","journal-title":"J. Instruct. Level Parall."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125932"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.381947"},{"key":"e_1_2_1_20_1","unstructured":"Baskins D. 2004. A 10-minute description of how Judy arrays work and why they are so fast. judy.sourceforge. net\/doc\/shop_interm.pdf.  Baskins D. 2004. A 10-minute description of how Judy arrays work and why they are so fast. judy.sourceforge. net\/doc\/shop_interm.pdf."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230403"},{"volume-title":"Proceedings of the Symposium on the Foundations of Computer Science. IEEE","author":"Bender M.","key":"e_1_2_1_22_1","unstructured":"Bender , M. , Brodal , G. S. , Fagerberg , R. , Ge , D. , He , S. , Hu , H. , Iacono , J. , and Lopez-Ortiz , A . 2003. The cost of cache-oblivious searching . In Proceedings of the Symposium on the Foundations of Computer Science. IEEE , Los Alamitos, CA, 271--282. Bender, M., Brodal, G. S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J., and Lopez-Ortiz, A. 2003. The cost of cache-oblivious searching. In Proceedings of the Symposium on the Foundations of Computer Science. IEEE, Los Alamitos, CA, 271--282."},{"volume-title":"Cache-oblivious B-trees. In Proceedings of the Foundations of Computer Science. IEEE","author":"Bender M. A.","key":"e_1_2_1_23_1","unstructured":"Bender , M. A. , Demaine , E. D. , and Farach-Colton , M . 2000 . Cache-oblivious B-trees. In Proceedings of the Foundations of Computer Science. IEEE , Los Alamitos, CA, 399--409. Bender, M. A., Demaine, E. D., and Farach-Colton, M. 2000. Cache-oblivious B-trees. In Proceedings of the Foundations of Computer Science. IEEE, Los Alamitos, CA, 399--409."},{"volume-title":"Proceedings of the European Symposium on Algorithms. Springer","author":"Bender M. A.","key":"e_1_2_1_24_1","unstructured":"Bender , M. A. , Demaine , E. D. , and Farach-Colton , M . 2002. Efficient tree layout in a multilevel memory hierarchy . In Proceedings of the European Symposium on Algorithms. Springer , Berlin, 165--173. Bender, M. A., Demaine, E. D., and Farach-Colton, M. 2002. Efficient tree layout in a multilevel memory hierarchy. In Proceedings of the European Symposium on Algorithms. Springer, Berlin, 165--173."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.014"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142385"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms. ACM","author":"Bentley J. L.","key":"e_1_2_1_28_1","unstructured":"Bentley , J. L. and Sedgewick , R . 1997. Fast algorithms for sorting and searching strings . In Proceedings of the Symposium on Discrete Algorithms. ACM , New York, 360--369. Bentley, J. L. and Sedgewick, R. 1997. Fast algorithms for sorting and searching strings. In Proceedings of the Symposium on Discrete Algorithms. ACM, New York, 360--369."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/582419.582421"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1128022.1128071"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109621"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms. ACM","author":"Brodal G. S.","key":"e_1_2_1_32_1","unstructured":"Brodal , G. S. , Fagerberg , R. , and Jacob , R . 2002. Cache oblivious search trees via binary trees of small height . In Proceedings of the Symposium on Discrete Algorithms. ACM , New York, 39--48. Brodal, G. S., Fagerberg, R., and Jacob, R. 2002. Cache oblivious search trees via binary trees of small height. In Proceedings of the Symposium on Discrete Algorithms. ACM, New York, 39--48."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/232973.232983"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/291069.291036"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/106972.106979"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/195473.195557"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301635"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301633"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.889095"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134011"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms. ACM","author":"Clement J.","key":"e_1_2_1_42_1","unstructured":"Clement , J. , Flajolet , P. , and Vallee , B . 1998. The analysis of hybrid trie structures . In Proceedings of the Symposium on Discrete Algorithms. ACM , New York, 531--539. Clement, J., Flajolet, P., and Vallee, B. 1998. The analysis of hybrid trie structures. In Proceedings of the Symposium on Discrete Algorithms. ACM, New York, 531--539."},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Clement J. Flajolet P. and Vallee B. 2001. Dynamic sources in information theory: A general analysis of trie structures. Algorithmica 29 1\/2 307--369.  Clement J. Flajolet P. and Vallee B. 2001. Dynamic sources in information theory: A general analysis of trie structures. Algorithmica 29 1\/2 307--369.","DOI":"10.1007\/BF02679623"},{"volume-title":"Proceedings of the Annual International Symposium on Microarchitecture. ACM","author":"Collins J.","key":"e_1_2_1_44_1","unstructured":"Collins , J. , Sair , S. , Calder , B. , and Tullsen , D. M . 2002. Pointer cache assisted prefetching . In Proceedings of the Annual International Symposium on Microarchitecture. ACM , New York, 62--73. Collins, J., Sair, S., Calder, B., and Tullsen, D. M. 2002. Pointer cache assisted prefetching. In Proceedings of the Annual International Symposium on Microarchitecture. ACM, New York, 62--73."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320102"},{"volume-title":"Proceedings of the 2nd International Workshop Experimental and Efficient Algorithms. Springer","author":"Crescenzi P.","key":"e_1_2_1_46_1","unstructured":"Crescenzi , P. , Grossi , R. , and Italiano , G. F . 2003. Search data structures for skewed strings . In Proceedings of the 2nd International Workshop Experimental and Efficient Algorithms. Springer , Berlin, 81--96. Crescenzi, P., Grossi, R., and Italiano, G. F. 2003. Search data structures for skewed strings. In Proceedings of the 2nd International Workshop Experimental and Efficient Algorithms. Springer, Berlin, 81--96."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1457838.1457895"},{"volume-title":"Proceedings of the Conference on Linux Clusters: The HPC Revolution. IEEE","author":"Dongarra J.","key":"e_1_2_1_48_1","unstructured":"Dongarra , J. , London , K. , Moore , S. , Mucci , S. , and Terpstra , D . 2001. Using PAPI for hardware performance monitoring on linux systems . In Proceedings of the Conference on Linux Clusters: The HPC Revolution. IEEE , Los Alamitos, CA. Dongarra, J., London, K., Moore, S., Mucci, S., and Terpstra, D. 2001. Using PAPI for hardware performance monitoring on linux systems. In Proceedings of the Conference on Linux Clusters: The HPC Revolution. IEEE, Los Alamitos, CA."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/263580.263597"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/60290"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_11"},{"volume-title":"Proceedings of the Symposium on the Foundations of Computer Science. IEEE","author":"Frigo M.","key":"e_1_2_1_54_1","unstructured":"Frigo , M. , Leiserson , C. , Prokop , H. , and Ramachandran , S . 1999. Cache-oblivious algorithms . In Proceedings of the Symposium on the Foundations of Computer Science. IEEE , Los Alamitos, CA, 285. Frigo, M., Leiserson, C., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proceedings of the Symposium on the Foundations of Computer Science. IEEE, Los Alamitos, CA, 285."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/144965.145006"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0025-y"},{"key":"e_1_2_1_57_1","volume-title":"Handbook of Algorithms and Data Structures: In Pascal and C","author":"Gonnet G. H.","unstructured":"Gonnet , G. H. and Baeza-Yates , R. 1991. Handbook of Algorithms and Data Structures: In Pascal and C , 2 nd Ed. Addison-Wesley , Boston, MA . Gonnet, G. H. and Baeza-Yates, R. 1991. Handbook of Algorithms and Data Structures: In Pascal and C, 2nd Ed. Addison-Wesley, Boston, MA.","edition":"2"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. Morgan Kaufmann","author":"Graefe G.","key":"e_1_2_1_58_1","unstructured":"Graefe , G. , Bunker , R. , and Cooper , S . 1998. Hash joins and hash teams in Microsoft SQL server . In Proceedings of the International Conference on Very Large Databases. Morgan Kaufmann , San Francisco, CA, 86--97. Graefe, G., Bunker, R., and Cooper, S. 1998. Hash joins and hash teams in Microsoft SQL server. In Proceedings of the International Conference on Very Large Databases. Morgan Kaufmann, San Francisco, CA, 86--97."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/165939.165944"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359560"},{"volume-title":"Proceedings of the 2nd Annual Workshop on Duplicating, Deconstructing, and Debunking. http:\/\/www.ece.wisc.edu\/~wddd\/2003\/01_hallberg.pdf.","author":"Hallberg J.","key":"e_1_2_1_61_1","unstructured":"Hallberg , J. , Palm , T. , and Brorsson , M . 2003. Cache-conscious allocation of pointer-based data structures revisited with HW\/SW prefetching . In Proceedings of the 2nd Annual Workshop on Duplicating, Deconstructing, and Debunking. http:\/\/www.ece.wisc.edu\/~wddd\/2003\/01_hallberg.pdf. Hallberg, J., Palm, T., and Brorsson, M. 2003. Cache-conscious allocation of pointer-based data structures revisited with HW\/SW prefetching. In Proceedings of the 2nd Annual Workshop on Duplicating, Deconstructing, and Debunking. http:\/\/www.ece.wisc.edu\/~wddd\/2003\/01_hallberg.pdf."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_63_1","volume-title":"The Cache Memory Book","author":"Handy J.","unstructured":"Handy , J. 1998. The Cache Memory Book , 2 nd Ed. Academic Press Professional, Inc. , San Diego, CA . Handy, J. 1998. The Cache Memory Book, 2nd Ed. Academic Press Professional, Inc., San Diego, CA.","edition":"2"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/357146.357152"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(94)00047-7"},{"volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments. SIAM","author":"Heileman G. L.","key":"e_1_2_1_66_1","unstructured":"Heileman , G. L. and Luo , W . 2005. How caching affects hashing . In Proceedings of the Workshop on Algorithm Engineering and Experiments. SIAM , Philadelphia, PA, 141--154. Heileman, G. L. and Luo, W. 2005. How caching affects hashing. In Proceedings of the Workshop on Algorithm Engineering and Experiments. SIAM, Philadelphia, PA, 141--154."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_1_68_1","volume-title":"Computer Architecture: A Quantitative Approach","author":"Hennessy J. L.","year":"2003","unstructured":"Hennessy , J. L. and Patterson , D. A . 2003 . Computer Architecture: A Quantitative Approach , 3 rd Ed. Morgan Kaufmann , San Francisco, CA . Hennessy, J. L. and Patterson, D. A. 2003. Computer Architecture: A Quantitative Approach, 3rd Ed. Morgan Kaufmann, San Francisco, CA.","edition":"3"},{"key":"e_1_2_1_69_1","unstructured":"Hewlett-Packard. 2001. Programming with Judy: C language Judy version 4.0. Tech. rep. HP Part Number: B6841-90001.  Hewlett-Packard. 2001. Programming with Judy: C language Judy version 4.0. Tech. rep. HP Part Number: B6841-90001."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.40842"},{"key":"e_1_2_1_71_1","first-page":"1","article-title":"The microarchitecture of the Pentium 4 processor","volume":"5","author":"Hinton G.","year":"2001","unstructured":"Hinton , G. , Sager , D. , Upton , M. , Boggs , D. , Carmean , D. , Kyker , A. , and Roussel , P. 2001 . The microarchitecture of the Pentium 4 processor . Intel Technol. J. 5 , 1 -- 13 . Hinton, G., Sager, D., Upton, M., Boggs, D., Carmean, D., Kyker, A., and Roussel, P. 2001. The microarchitecture of the Pentium 4 processor. Intel Technol. J. 5, 1--13.","journal-title":"Intel Technol. J."},{"key":"e_1_2_1_72_1","volume-title":"Beginning C: From Novice to Professional","author":"Horton I.","unstructured":"Horton , I. 2006. Beginning C: From Novice to Professional , 4 th Ed. Apress , Berkeley, CA . Horton, I. 2006. Beginning C: From Novice to Professional, 4th Ed. Apress, Berkeley, CA.","edition":"4"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.11.004"},{"volume-title":"Basic architecture. Tech. rep., Intel Developer's Manual","author":"Intel","key":"e_1_2_1_74_1","unstructured":"Intel . 2007. Intel 64 and IA-32 architectures software developer's manual . Vol. 1 : Basic architecture. Tech. rep., Intel Developer's Manual . http:\/\/www.intel.com\/products\/processor\/manuals\/index.htm. Intel. 2007. Intel 64 and IA-32 architectures software developer's manual. Vol. 1: Basic architecture. Tech. rep., Intel Developer's Manual. http:\/\/www.intel.com\/products\/processor\/manuals\/index.htm."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.133271"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1987.233491"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/264107.264207"},{"volume-title":"Proceedings of the Symposium on High-Performance Computer Architecture. IEEE","author":"Karlsson M.","key":"e_1_2_1_78_1","unstructured":"Karlsson , M. , Dahlgren , F. , and Stenstrom , P . 2000. A prefetching technique for irregular accesses to linked data structures . In Proceedings of the Symposium on High-Performance Computer Architecture. IEEE , Los Alamitos, CA, 206--217. Karlsson, M., Dahlgren, F., and Stenstrom, P. 2000. A prefetching technique for irregular accesses to linked data structures. In Proceedings of the Symposium on High-Performance Computer Architecture. IEEE, Los Alamitos, CA, 206--217."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155117"},{"key":"e_1_2_1_80_1","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1998. The Art of Computer Programming: Sorting and Searching , 2 nd Ed. Vol. 3 . Addison-Wesley Longman, Redwood City , CA. Knuth, D. E. 1998. The Art of Computer Programming: Sorting and Searching, 2nd Ed. Vol. 3. Addison-Wesley Longman, Redwood City, CA.","edition":"2"},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","unstructured":"Kowarschik M. and Weiss C. 2003. An overview of cache optimization techniques and cache-aware numerical algorithms. In Algorithms for Memory Hierarchies U. Meyer P. Sanders and J. F. Sibeyn Eds. Dagstuhl Research Seminar Schloss Dagstuhl Germany 213--232.  Kowarschik M. and Weiss C. 2003. An overview of cache optimization techniques and cache-aware numerical algorithms. In Algorithms for Memory Hierarchies U. Meyer P. Sanders and J. F. Sibeyn Eds. Dagstuhl Research Seminar Schloss Dagstuhl Germany 213--232.","DOI":"10.1007\/3-540-36574-5_10"},{"volume-title":"Algorithms for Memory Hierarchies","author":"Kumar P.","key":"e_1_2_1_82_1","unstructured":"Kumar , P. 2003. Cache oblivious algorithms . In Algorithms for Memory Hierarchies , U. Meyer, P. Sanders, and J. F. Sibeyn, Eds. Dagstuhl Research Seminar, Schloss Dagstuhl , Germany , 193--212. Kumar, P. 2003. Cache oblivious algorithms. In Algorithms for Memory Hierarchies, U. Meyer, P. Sanders, and J. F. Sibeyn, Eds. Dagstuhl Research Seminar, Schloss Dagstuhl, Germany, 193--212."},{"key":"e_1_2_1_83_1","doi-asserted-by":"crossref","unstructured":"Ladner R. E. Fortna R. and Nguyen B. 2002. A comparison of cache aware and cache oblivious static search trees using program instrumentation. In Experimental Algorithmics: From Algorithm Design to Robust and Efficient Software R. Fleischer B. Moret and E. M. Schmidt Eds. Springer Berlin 78--92.   Ladner R. E. Fortna R. and Nguyen B. 2002. A comparison of cache aware and cache oblivious static search trees using program instrumentation. In Experimental Algorithmics: From Algorithm Design to Robust and Efficient Software R. Fleischer B. Moret and E. M. Schmidt Eds. Springer Berlin 78--92.","DOI":"10.1007\/3-540-36383-1_4"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/235141.235145"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/319758.319763"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065027"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/299649.299772"},{"key":"e_1_2_1_88_1","unstructured":"Leung S. and Zahorjan J. 1995. Optimizing data locality by array restructuring. Tech. rep. TR-95-09-01 Department of Computer Science and Engineering University of Washington.  Leung S. and Zahorjan J. 1995. Optimizing data locality by array restructuring. Tech. rep. TR-95-09-01 Department of Computer Science and Engineering University of Washington."},{"volume-title":"Proceedings of the Annual International Symposium on Microarchitecture. ACM","author":"Lipasti M. H.","key":"e_1_2_1_89_1","unstructured":"Lipasti , M. H. , Schmidt , W. J. , Kunkel , S. R. , and Roediger , R. R . 1995. Spiad: Software prefetching in pointer and call-intensive environments . In Proceedings of the Annual International Symposium on Microarchitecture. ACM , New York, 252--263. Lipasti, M. H., Schmidt, W. J., Kunkel, S. R., and Roediger, R. R. 1995. Spiad: Software prefetching in pointer and call-intensive environments. In Proceedings of the Annual International Symposium on Microarchitecture. ACM, New York, 252--263."},{"key":"e_1_2_1_90_1","volume-title":"Efficient Memory Programming","author":"Loshin D.","unstructured":"Loshin , D. 1998. Efficient Memory Programming , 1 st Ed. McGraw-Hill Professional , New York . Loshin, D. 1998. Efficient Memory Programming, 1st Ed. McGraw-Hill Professional, New York.","edition":"1"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/379240.379250"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237190"},{"volume-title":"Proceedings of the International Conference on Parallel and Distributed Computing Systems. ISCA.","author":"Manjikian N.","key":"e_1_2_1_93_1","unstructured":"Manjikian , N. and Abdelrahman , T . 1995. Array data layout for the reduction of cache conflicts . In Proceedings of the International Conference on Parallel and Distributed Computing Systems. ISCA. Manjikian, N. and Abdelrahman, T. 1995. Array data layout for the reduction of cache conflicts. In Proceedings of the International Conference on Parallel and Distributed Computing Systems. ISCA."},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274812"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.13.4.609"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_97_1","volume-title":"Eds","author":"Meyer U.","year":"2003","unstructured":"Meyer , U. , Sanders , P. , and Sibeyn , J. F. , Eds . 2003 . Algorithms for Memory Hierarchies, Advanced Lectures . Dagstuhl Research Seminar, Schloss Dagstuhl, Germany . Meyer, U., Sanders, P., and Sibeyn, J. F., Eds. 2003. Algorithms for Memory Hierarchies, Advanced Lectures. Dagstuhl Research Seminar, Schloss Dagstuhl, Germany."},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/015\/09"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_2_1_101_1","volume-title":"Advanced Compiler Design and Implementation","author":"Muchnick S. S.","unstructured":"Muchnick , S. S. 1997. Advanced Compiler Design and Implementation , 1 st Ed. Morgan Kaufmann , San Francisco, CA . Muchnick, S. S. 1997. Advanced Compiler Design and Implementation, 1st Ed. Morgan Kaufmann, San Francisco, CA.","edition":"1"},{"volume-title":"Proceedings of the Fall Joint Computer Conference. ACM","author":"Munro J. I.","key":"e_1_2_1_102_1","unstructured":"Munro , J. I. and Celis , P . 1986. Techniques for collision resolution in hash tables with open addressing . In Proceedings of the Fall Joint Computer Conference. ACM , New York, 601--610. Munro, J. I. and Celis, P. 1986. Techniques for collision resolution in hash tables with open addressing. In Proceedings of the Fall Joint Computer Conference. ACM, New York, 601--610."},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/1152922.1101876"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/367177.367205"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.592312"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.12.0130"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"volume-title":"Algorithms for Memory Hierarchies","author":"Rahman N.","key":"e_1_2_1_108_1","unstructured":"Rahman , N. 2002. Algorithms for hardware caches and TLB . In Algorithms for Memory Hierarchies , U. Meyer, P. Sanders, and J. F. Sibeyn, Eds. Dagstuhl Research Seminar, Schloss Dagstuhl , Germany , 171--192. Rahman, N. 2002. Algorithms for hardware caches and TLB. In Algorithms for Memory Hierarchies, U. Meyer, P. Sanders, and J. F. Sibeyn, Eds. Dagstuhl Research Seminar, Schloss Dagstuhl, Germany, 171--192."},{"volume-title":"Proceedings of the International Workshop on Algorithm Engineering. Springer","author":"Rahman N.","key":"e_1_2_1_109_1","unstructured":"Rahman , N. , Cole , R. , and Raman , R . 2001. Optimized predecessor data structures for internal memory . In Proceedings of the International Workshop on Algorithm Engineering. Springer , Berlin, 67--78. Rahman, N., Cole, R., and Raman, R. 2001. Optimized predecessor data structures for internal memory. In Proceedings of the International Workshop on Algorithm Engineering. Springer, Berlin, 67--78."},{"volume-title":"Proceedings of the Symposium on Databases Systems for Advanced Applications. IEEE","author":"Ramakrishna M. V.","key":"e_1_2_1_110_1","unstructured":"Ramakrishna , M. V. and Zobel , J . 1997. Performance in practice of string hashing functions . In Proceedings of the Symposium on Databases Systems for Advanced Applications. IEEE , Los Alamitos, CA, 215--224. Ramakrishna, M. V. and Zobel, J. 1997. Performance in practice of string hashing functions. In Proceedings of the Symposium on Databases Systems for Advanced Applications. IEEE, Los Alamitos, CA, 215--224."},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1145\/62032.77249"},{"volume-title":"Proceedings of the International Conference on Very Large Databases. ACM","author":"Rao J.","key":"e_1_2_1_112_1","unstructured":"Rao , J. and Ross , K. A . 1999. Cache conscious indexing for decision-support in main memory . In Proceedings of the International Conference on Very Large Databases. ACM , New York, 78--89. Rao, J. and Ross, K. A. 1999. Cache conscious indexing for decision-support in main memory. In Proceedings of the International Conference on Very Large Databases. ACM, New York, 78--89."},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1145\/122045.122048"},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277661"},{"key":"e_1_2_1_116_1","doi-asserted-by":"publisher","DOI":"10.1145\/223982.224419"},{"key":"e_1_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.1145\/322003.322006"},{"key":"e_1_2_1_118_1","doi-asserted-by":"publisher","DOI":"10.1145\/291069.291034"},{"key":"e_1_2_1_119_1","doi-asserted-by":"publisher","DOI":"10.1145\/300979.300989"},{"volume-title":"Proceedings of the International Conference on Compiler Construction. Springer","author":"Rubin S.","key":"e_1_2_1_120_1","unstructured":"Rubin , S. , Bernstein , D. , and Rodeh , M . 1999. Virtual cache line: A new technique to improve cache exploitation for recursive data structures . In Proceedings of the International Conference on Compiler Construction. Springer , Berlin, 259--273. Rubin, S., Bernstein, D., and Rodeh, M. 1999. Virtual cache line: A new technique to improve cache exploitation for recursive data structures. In Proceedings of the International Conference on Compiler Construction. Springer, Berlin, 259--273."},{"key":"e_1_2_1_121_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90122-2"},{"key":"e_1_2_1_122_1","volume-title":"Parts 1-4: Fundamentals, Data structures, Sorting, and Searching","author":"Sedgewick R.","unstructured":"Sedgewick , R. 1998. Algorithms in C , Parts 1-4: Fundamentals, Data structures, Sorting, and Searching , 3 rd Ed. Addison-Wesley , Boston, MA . Sedgewick, R. 1998. Algorithms in C, Parts 1-4: Fundamentals, Data structures, Sorting, and Searching, 3rd Ed. Addison-Wesley, Boston, MA.","edition":"3"},{"key":"e_1_2_1_123_1","doi-asserted-by":"publisher","DOI":"10.1145\/356631.356633"},{"key":"e_1_2_1_124_1","volume-title":"The Unabridged Pentium 4: IA32 Processor Genealogy","author":"Shanley T.","unstructured":"Shanley , T. 2004. The Unabridged Pentium 4: IA32 Processor Genealogy , 1 st Ed. Addison-Wesley , Boston, MA . Shanley, T. 2004. The Unabridged Pentium 4: IA32 Processor Genealogy, 1st Ed. Addison-Wesley, Boston, MA.","edition":"1"},{"key":"e_1_2_1_125_1","unstructured":"Silverstein A. 2002. Judy IV shop manual. judy.sourceforge.net\/doc\/shop_interm.pdf.  Silverstein A. 2002. Judy IV shop manual. judy.sourceforge.net\/doc\/shop_interm.pdf."},{"key":"e_1_2_1_126_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1187439"},{"key":"e_1_2_1_127_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_128_1","doi-asserted-by":"publisher","DOI":"10.1145\/356887.356892"},{"volume-title":"Proceedings of the International Conference on Compiler Construction. Springer","author":"Stoutchinin A.","key":"e_1_2_1_129_1","unstructured":"Stoutchinin , A. , Amaral , J. N. , Gao , G. R. , Dehnert , J. C. , Jain , S. , and Douillet , A . 2001. Speculative prefetching of induction pointers . In Proceedings of the International Conference on Compiler Construction. Springer , Berlin, 289--303. Stoutchinin, A., Amaral, J. N., Gao, G. R., Dehnert, J. C., Jain, S., and Douillet, A. 2001. Speculative prefetching of induction pointers. In Proceedings of the International Conference on Compiler Construction. Springer, Berlin, 289--303."},{"key":"e_1_2_1_130_1","doi-asserted-by":"publisher","DOI":"10.1145\/366552.366600"},{"key":"e_1_2_1_131_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759045"},{"key":"e_1_2_1_132_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.706059"},{"volume-title":"Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. IEEE","author":"Truong D. N.","key":"e_1_2_1_133_1","unstructured":"Truong , D. N. , Bodin , F. , and Seznec , A . 1998. Improving cache behavior of dynamically allocated data structures . In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. IEEE , Los Alamitos, CA,--329. Truong, D. N., Bodin, F., and Seznec, A. 1998. Improving cache behavior of dynamically allocated data structures. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. IEEE, Los Alamitos, CA,--329."},{"key":"e_1_2_1_134_1","doi-asserted-by":"publisher","DOI":"10.1145\/358923.358939"},{"key":"e_1_2_1_135_1","doi-asserted-by":"publisher","DOI":"10.1145\/322374.322375"},{"key":"e_1_2_1_136_1","doi-asserted-by":"publisher","DOI":"10.1145\/859618.859663"},{"key":"e_1_2_1_137_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.394"},{"key":"e_1_2_1_138_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044823.1044827"},{"key":"e_1_2_1_139_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248394"},{"key":"e_1_2_1_140_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127577.1127584"},{"key":"e_1_2_1_141_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00239-3"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1671970.1921704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1671970.1921704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:24Z","timestamp":1750278384000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1671970.1921704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":138,"alternative-id":["10.1145\/1671970.1921704"],"URL":"https:\/\/doi.org\/10.1145\/1671970.1921704","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}