{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T01:52:48Z","timestamp":1775785968230,"version":"3.50.1"},"reference-count":96,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,3,11]],"date-time":"2008-03-11T00:00:00Z","timestamp":1205193600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2009,1]]},"DOI":"10.1007\/s00778-008-0094-1","type":"journal-article","created":{"date-parts":[[2008,3,10]],"date-time":"2008-03-10T13:26:17Z","timestamp":1205155577000},"page":"157-179","source":"Crossref","is-referenced-by-count":12,"title":["B-tries for disk-based string management"],"prefix":"10.1007","volume":"18","author":[{"given":"Nikolas","family":"Askitis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Zobel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,3,11]]},"reference":[{"issue":"9","key":"94_CR1","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1002\/spe.4380220902","volume":"22","author":"J. Aoe","year":"1992","unstructured":"Aoe, J., Morimoto, K., Sato, T.: An efficient implementation of trie structures. Softw Practice Exp 22(9), 695\u2013721 (1992)","journal-title":"Softw Practice Exp"},{"key":"94_CR2","doi-asserted-by":"crossref","unstructured":"Arge, L.: The buffer tree: a new technique for optimal I\/O-algorithms. In: Proc. Int. Workshop on Algorithms and Data Structures, pp. 334\u2013345. Kingston (1995)","DOI":"10.1007\/3-540-60220-8_74"},{"key":"94_CR3","doi-asserted-by":"crossref","unstructured":"Arge, L.: External memory data structures. In: Handbook of Massive Data Sets, pp. 313\u2013357. Kluwer, Norwell (2002)","DOI":"10.1007\/978-1-4615-0005-6_9"},{"key":"94_CR4","doi-asserted-by":"crossref","unstructured":"Arnow, D.M., Tenenbaum, A.M.: An empirical comparison of B-trees, compact B-trees and multiway trees. In: Proc. ACM SIGMOD Int. Conf. on the Management of Data, pp. 33\u201346. Boston (1984)","DOI":"10.1145\/602259.602265"},{"key":"94_CR5","doi-asserted-by":"crossref","unstructured":"Arnow, D.M., Tenenbaum, A.M., Wu, C.: P-trees: Storage efficient multiway trees. In: Proc. ACM SIGIR Int. Conf. on Research and Development in Information Retrieval, pp. 111\u2013121. Montreal (1985)","DOI":"10.1145\/253495.253516"},{"key":"94_CR6","doi-asserted-by":"crossref","unstructured":"Askitis, N., Zobel, J.: Cache-conscious collision resolution in string hash tables. In: Proc. SPIRE String Processing and Information Retrieval Symp., pp. 91\u2013102. Buenos Aires (2005)","DOI":"10.1007\/11575832_11"},{"key":"94_CR7","doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R.A.: An adaptive overflow technique for B-trees. In: Proc. Int. Conf. on Extending Database Technology, pp. 16\u201328, Venice (1990)","DOI":"10.1007\/BFb0022161"},{"issue":"2","key":"94_CR8","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/69.87964","volume":"1","author":"R.A. Baeza-Yates","year":"1989","unstructured":"Baeza-Yates, R.A., Larson, P.A.: Performance of B+-trees with partial expansions. IEEE Trans Knowl Data Eng 1(2), 248\u2013257 (1989)","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"3","key":"94_CR9","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indices. Acta Inf 1(3), 173\u2013189 (1972)","journal-title":"Acta Inf"},{"issue":"1","key":"94_CR10","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/320521.320530","volume":"2","author":"R. Bayer","year":"1977","unstructured":"Bayer, R., Unterauer, K.: Prefix B-trees. ACM Trans Database Systems 2(1), 11\u201326 (1977)","journal-title":"ACM Trans Database Systems"},{"key":"94_CR11","volume-title":"Text Compression","author":"T.C. Bell","year":"1990","unstructured":"Bell, T.C., Cleary, J.G., Witten, I.H.: Text Compression, 1st edn. Prentice-Hall, New Jersey (1990)","edition":"1"},{"issue":"4","key":"94_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/205323.205327","volume":"38","author":"T.C. Bell","year":"1995","unstructured":"Bell, T.C., Moffat, A., Witten, I.H., Zobel, J.: The MG retrieval system: compressing for space and speed. Commun ACM 38(4), 41\u201342 (1995)","journal-title":"Commun ACM"},{"issue":"6","key":"94_CR13","doi-asserted-by":"crossref","first-page":"2090","DOI":"10.1137\/S009753979731858X","volume":"28","author":"Y. Ben-Asher","year":"1999","unstructured":"Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM J. Comput. 28(6), 2090\u20132102 (1999)","journal-title":"SIAM J. Comput."},{"key":"94_CR14","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. In: Proc. IEEE Foundations of Computer Science, pp. 399\u2013409, Redondo Beach (2000)","DOI":"10.1109\/SFCS.2000.892128"},{"key":"94_CR15","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Efficient tree layout in a multilevel memory hierarchy. In: Proc. European Symp. on Algorithms, pp. 165\u2013173, Rome (2002)","DOI":"10.1007\/3-540-45749-6_18"},{"issue":"2","key":"94_CR16","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.jalgor.2004.04.014","volume":"53","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. J. Algorithms 53(2), 115\u2013136 (2004)","journal-title":"J. Algorithms"},{"key":"94_CR17","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M., Kuszmaul, B.C.: Cache-oblivious string B-trees. In: Proc. of ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pp. 233\u2013242. Chicago (2006)","DOI":"10.1145\/1142351.1142385"},{"key":"94_CR18","unstructured":"Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proc. ACM SIAM Symp. on Discrete Algorithms, pp. 360\u2013369. New Orleans (1997)"},{"key":"94_CR19","doi-asserted-by":"crossref","unstructured":"de~la Briandais, R.: File searching using variable length keys. In: Proc. Western Joint Computer Conference, pp. 295\u2013298, New York (1959)","DOI":"10.1145\/1457838.1457895"},{"key":"94_CR20","doi-asserted-by":"crossref","unstructured":"Brodal, G., Fagerberg, R.: Cache-oblivious string dictionaries. In: Proc. ACM SIAM Symp. on Discrete Algorithms, pp. 581\u2013590, Miami (2006)","DOI":"10.1145\/1109557.1109621"},{"issue":"6","key":"94_CR21","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1109\/69.824617","volume":"11","author":"Y. Chang","year":"1999","unstructured":"Chang, Y., Lee, C., ChangLiaw, W.: Linear spiral hashing for expansible files. IEEE Trans. Knowl. Data Eng. 11(6), 969\u2013984 (1999)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"94_CR22","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/TKDE.2005.3","volume":"17","author":"C. Cheung","year":"2005","unstructured":"Cheung, C., Yu, J.X., Lu, H.: Constructing suffix tree for gigabyte sequences with megabyte memory. IEEE Trans. Knowl. Data Eng. 17, 90\u2013105 (2005)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"94_CR23","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/776985.777000","volume":"32","author":"E.I. Chong","year":"2003","unstructured":"Chong, E.I., Srinivasan, J., Das, S., Freiwald, C., Yalamanchi, A., Jagannath, M., Tran, A., Krishnan, R., Jiang, R.: A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+trees. ACM SIGMOD Record 32(2), 78\u201388 (2003)","journal-title":"ACM SIGMOD Record"},{"key":"94_CR24","unstructured":"Chowdhury, N.M.M.K., Akbar, M.M., Kaykobad, M.: Disk Trie: An efficient data structure using flash memory for mobile devices. In: Workshop on Algorithms and Computation, pp. 76\u201387. Bangladesh Computer Council Bhaban, Agargaon (2007)"},{"key":"94_CR25","doi-asserted-by":"crossref","unstructured":"Ciriani, V., Ferragina, P., Luccio, F., Muthukrishnan, S.: Static optimality theorem for external memory string access. In: IEEE Symp. on the Foundations of Computer Science, pp. 219\u2013227, Vancouver (2002)","DOI":"10.1109\/SFCS.2002.1181945"},{"issue":"1","key":"94_CR26","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/1186810.1186816","volume":"3","author":"V. Ciriani","year":"2007","unstructured":"Ciriani, V., Ferragina, P., Luccio, F., Muthukrishnan, S.: A data structure for a sequence of string accesses in external memory. ACM Trans. Algorithms 3(1), 6 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"94_CR27","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: Proc. ACM SIAM Symp. on Discrete Algorithms, pp. 383\u2013391, Atlanta (1996)"},{"issue":"3","key":"94_CR28","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1145\/320083.320102","volume":"4","author":"D. Comer","year":"1979","unstructured":"Comer, D.: Heuristics for trie index minimization. ACM Trans. Database Systems 4(3), 383\u2013395 (1979)","journal-title":"ACM Trans. Database Systems"},{"issue":"2","key":"94_CR29","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D.: Ubiquitous B-tree. ACM Comput. Surv. 11(2), 121\u2013137 (1979)","journal-title":"ACM Comput. Surv."},{"key":"94_CR30","doi-asserted-by":"crossref","unstructured":"Crauser, A., Ferragina, P.: On constructing suffix arrays in external memory. In: Proc. of European Symp. on Algorithms, pp. 224\u2013235, Prague (1999)","DOI":"10.1007\/3-540-48481-7_20"},{"issue":"3","key":"94_CR31","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/319587.319612","volume":"6","author":"K. Culik","year":"1981","unstructured":"Culik, K., Ottmann, T., Wood, D.: Dense multiway trees. ACM Trans. Database Systems 6(3), 486\u2013512 (1981)","journal-title":"ACM Trans. Database Systems"},{"key":"94_CR32","doi-asserted-by":"crossref","unstructured":"Deschler, K.W., Rundensteiner, E.A.: B+Retake: Sustaining high volume inserts into large data pages. In: Proc. Int. Workshop on Data Warehousing and OLAP, pp. 56\u201363, Atlanta (2001)","DOI":"10.1145\/512236.512244"},{"key":"94_CR33","unstructured":"Fan, X., Yang, Y., Zhang, L.: Implementation and evaluation of String B-tree. Tech. rep., University of Florida (2001)"},{"key":"94_CR34","doi-asserted-by":"crossref","unstructured":"Farach, M., Ferragina, P., Muthukrishnan, S.: Overcoming the memory bottleneck in suffix tree construction. In: IEEE Symp. on the Foundations of Computer Science, p. 174, Palo Alto (1998)","DOI":"10.1109\/SFCS.1998.743441"},{"key":"94_CR35","unstructured":"Ferragina, P., Grossi, R.: Fast string searching in secondary storage: theoretical developments and experimental results. In: Proc. ACM SIAM Symp. on Discrete Algorithms, pp. 373\u2013382, Atlanta (1996)"},{"issue":"2","key":"94_CR36","doi-asserted-by":"crossref","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":"94_CR37","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/inco.1998.2733","volume":"146","author":"P. Ferragina","year":"1998","unstructured":"Ferragina, P., Luccio, F.: Dynamic dictionary matching in external memory. Inf. Comput. 146(2), 85\u201399 (1998)","journal-title":"Inf. Comput."},{"issue":"4","key":"94_CR38","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"issue":"2","key":"94_CR39","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1145\/5383.5453","volume":"33","author":"P. Flajolet","year":"1986","unstructured":"Flajolet, P., Puech, C.: Partial match retrieval of multimedia data. J. ACM 33(2), 371\u2013407 (1986)","journal-title":"J. ACM"},{"key":"94_CR40","doi-asserted-by":"crossref","unstructured":"Foster, C.C.: Information retrieval: information storage and retrieval using AVL trees. In: Proc. National Conf., pp. 192\u2013205, Cleveland (1965)","DOI":"10.1145\/800197.806043"},{"issue":"9","key":"94_CR41","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E. Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie memory. Commun. ACM 3(9), 490\u2013499 (1960)","journal-title":"ACM"},{"key":"94_CR42","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: IEEE Symp. on the Foundations of Computer Science, p. 285, New York City (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"94_CR43","volume-title":"Database Systems: the Complete Book","author":"H. Garcia-Molina","year":"2001","unstructured":"Garcia-Molina, H., Ullman, J.D., Widom, J.: Database Systems: the Complete Book, 1st edn. Prentice-Hall, New Jersey (2001)","edition":"1"},{"issue":"1","key":"94_CR44","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1145\/42267.42274","volume":"35","author":"G.H. Gonnet","year":"1988","unstructured":"Gonnet, G.H., Larson, P.: External hashing with limited internal storage. J. ACM 35(1), 161\u2013184 (1988)","journal-title":"J. ACM"},{"issue":"4","key":"94_CR45","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/271074.271094","volume":"26","author":"J. Gray","year":"1997","unstructured":"Gray, J., Graefe, G.: The five-minute rule ten years later, and other computer storage rules of thumb. SIGMOD Record 26(4), 63\u201368 (1997)","journal-title":"SIGMOD Record"},{"key":"94_CR46","volume-title":"Transaction Processing: Concepts and Techniques","author":"J. Gray","year":"1992","unstructured":"Gray, J., Reuter, A.: Transaction Processing: Concepts and Techniques, 1st edn. Morgan Kaufmann, San Francisco (1992)","edition":"1"},{"key":"94_CR47","doi-asserted-by":"crossref","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). In: Proc. ACM Symp. on Theory of Computing, pp. 397\u2013406, Portland (2000)","DOI":"10.1145\/335305.335351"},{"key":"94_CR48","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: IEEE Symp. on the Foundations of Computer Science, pp. 8\u201321, Ann Arbor (1978)","DOI":"10.1109\/SFCS.1978.3"},{"issue":"4","key":"94_CR49","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1145\/357146.357152","volume":"3","author":"W.J. Hansen","year":"1981","unstructured":"Hansen, W.J.: A cost model for the internal organization of B+-tree nodes. ACM Trans. Program. Languages Systems 3(4), 508\u2013532 (1981)","journal-title":"ACM Trans. Program. Languages Systems"},{"issue":"3","key":"94_CR50","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0306-4573(94)00047-7","volume":"31","author":"D. Harman","year":"1995","unstructured":"Harman, D.: Overview of the second text retrieval conf. (TREC-2). Inf. Process. Manage. 31(3), 271\u2013289 (1995)","journal-title":"Inf. Process. Manage."},{"issue":"2","key":"94_CR51","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1145\/506309.506312","volume":"20","author":"S. Heinz","year":"2002","unstructured":"Heinz, S., Zobel, J., Williams, H.E.: Burst tries: A fast, efficient data structure for string keys. ACM Trans. Inf. Systems 20(2), 192\u2013223 (2002)","journal-title":"ACM Trans. Inf. Systems"},{"key":"94_CR52","unstructured":"Hui, L.C.K., Martel, C.: On efficient unsuccessful search. In: Proc. ACM SIAM Symp. on Discrete Algorithms, pp. 217\u2013227, Orlando (1992)"},{"issue":"1","key":"94_CR53","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/202660.202666","volume":"24","author":"J. Jannink","year":"1995","unstructured":"Jannink, J.: Implementing deletion in B+-trees. Proc. ACM SIGMOD Int. Conf. Manag. Data 24(1), 33\u201338 (1995)","journal-title":"Proc. ACM SIGMOD Int. Conf. Manag. Data"},{"key":"94_CR54","doi-asserted-by":"crossref","unstructured":"Johnson, T., Shasha, D.: Utilization of B-trees with inserts, deletes and modifies. In: Proc. of ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pp. 235\u2013246, Philadelphia (1989)","DOI":"10.1145\/73721.73745"},{"issue":"1","key":"94_CR55","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0022-0000(93)90020-W","volume":"47","author":"T. Johnson","year":"1993","unstructured":"Johnson, T., Shasha, D.: B-trees with inserts and deletes: why free-at-empty is better than merge-at-half. J. Comput. System Sci. 47(1), 45\u201376 (1993)","journal-title":"J. Comput. System Sci."},{"key":"94_CR56","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Rao, S.S.: Full-text indexes in external memory. In: Algorithms for Memory Hierarchies, pp. 149\u2013170. Dagstuhl Research Seminar, Schloss Dagstuhl (2002)","DOI":"10.1007\/3-540-36574-5_7"},{"issue":"3","key":"94_CR57","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1109\/TKDE.2003.1198400","volume":"15","author":"K. Kato","year":"2003","unstructured":"Kato, K.: Persistently cached B-trees. IEEE Trans. Knowl. Data Eng. 15(3), 706\u2013720 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"4","key":"94_CR58","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1109\/52.17804","volume":"05","author":"K.L. Kelley","year":"1988","unstructured":"Kelley, K.L., Rusinkiewicz, M.: Multikey extensible hashing for relational databases. IEEE Softw. 05(4), 77\u201385 (1988)","journal-title":"IEEE Softw."},{"key":"94_CR59","doi-asserted-by":"crossref","unstructured":"Knessl, C., Szpankowski, W.: A note on the asymptotic behavior of the height in B-tries for B large. Electron. J. Combinat. 7(R39) (2000)","DOI":"10.37236\/1517"},{"issue":"1","key":"94_CR60","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0196-6774(02)00212-2","volume":"44","author":"C. Knessl","year":"2002","unstructured":"Knessl, C., Szpankowski, W.: Limit laws for the height in Patricia tries. J. Algorithms 44(1), 63\u201397 (2002)","journal-title":"J. Algorithms"},{"key":"94_CR61","volume-title":"The Art of Computer Programming: Sorting and Searching, vol. 3","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming: Sorting and Searching, vol. 3, 2nd edn. Addison-Wesley Longman, Redwood City (1998)","edition":"2"},{"key":"94_CR62","doi-asserted-by":"crossref","unstructured":"Ko, P., Aluru, S.: Obtaining provably good performance from suffix trees in secondary storage. In: Proc. Symp. on Combinatorial Pattern Matching, pp. 72\u201383, Barcelona (2006)","DOI":"10.1007\/11780441_8"},{"key":"94_CR63","doi-asserted-by":"crossref","unstructured":"Ko, P., Aluru, S.: Optimal self-adjusting trees for dynamic string data in secondary storage. In: Proc. SPIRE String Processing and Information Retrieval Symp., pp. 184\u2013194, Santiago (2007)","DOI":"10.1007\/978-3-540-75530-2_17"},{"key":"94_CR64","doi-asserted-by":"crossref","unstructured":"Kumar, P.: Cache oblivious algorithms. In: Algorithms for Memory Hierarchies, pp. 193\u2013212. Dagstuhl Research Seminar, Schloss Dagstuhl (2003)","DOI":"10.1007\/3-540-36574-5_9"},{"issue":"13","key":"94_CR65","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","volume":"29","author":"S. Kurtz","year":"1999","unstructured":"Kurtz, S.: Reducing the space requirement of suffix trees. Softw. Practice Exp. 29(13), 1149\u20131171 (1999)","journal-title":"Softw. Practice Exp."},{"key":"94_CR66","doi-asserted-by":"crossref","unstructured":"Ladner, R.E., Fortna, R., Nguyen, B.: 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, pp. 78\u201392, New York City (2002)","DOI":"10.1007\/3-540-36383-1_4"},{"issue":"3","key":"94_CR67","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1145\/44498.44500","volume":"13","author":"P. Larson","year":"1988","unstructured":"Larson, P.: Linear hashing with separators\u2014a dynamic hashing scheme achieving one-access. ACM Trans. Database Systems 13(3), 366\u2013388 (1988)","journal-title":"ACM Trans. Database Systems"},{"issue":"1","key":"94_CR68","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/12047.12049","volume":"12","author":"D.B. Lomet","year":"1987","unstructured":"Lomet, D.B.: Partial expansions for file organizations with an index. ACM Trans. Database Systems 12(1), 65\u201384 (1987)","journal-title":"ACM Trans. Database Systems"},{"key":"94_CR69","volume-title":"Evolution of Random Search Trees","author":"H.M. Mahmoud","year":"1992","unstructured":"Mahmoud, H.M.: Evolution of Random Search Trees, 1st edn. J Wiley, New York (1992)","edition":"1"},{"key":"94_CR70","doi-asserted-by":"crossref","unstructured":"Makawita, D., Tan, K., Liu, H.: Sampling from databases using B+-trees. In: Proc. CIKM Int. Conf. on Information and Knowledge Management, pp. 158\u2013164, McLean (2000)","DOI":"10.1145\/354756.354814"},{"key":"94_CR71","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. In: Proc. ACM SIAM Symp. on Discrete Algorithms, pp. 319\u2013327, San Francisco (1990)"},{"issue":"3","key":"94_CR72","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(91)90235-A","volume":"38","author":"C. Martel","year":"1991","unstructured":"Martel, C.: Self-adjusting multi-way search trees. Inf. Process. Lett. 38(3), 135\u2013141 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"94_CR73","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262\u2013271 (1976)","journal-title":"J. ACM"},{"key":"94_CR74","doi-asserted-by":"crossref","unstructured":"Na, J.C., Park, K.: Simple implementation of String B-trees. In: Proc. SPIRE String Processing and Information Retrieval Symp., pp. 214\u2013215, Padova (2004)","DOI":"10.1007\/978-3-540-30213-1_31"},{"issue":"1","key":"94_CR75","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G. Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), 1\u201361 (2007)","journal-title":"ACM Comput. Surv."},{"key":"94_CR76","unstructured":"Ooi, B.C., Tan, K.: B-trees: Bearing fruits of all kinds. In: Proc. Australasian Database Conf., pp. 13\u201320, Melbourne (2002)"},{"key":"94_CR77","unstructured":"Oracle: Berkeley DB, Oracle Embedded Database (2007). http:\/\/www.oracle.com\/technology\/software\/products\/berkeley-db\/index.html . Version 4.5.20"},{"key":"94_CR78","doi-asserted-by":"crossref","unstructured":"Pagh, R.: Basic external memory data structures. In: Algorithms for Memory Hierarchies, pp. 14\u201335. Dagstuhl Research Seminar, Schloss Dagstuhl (2002)","DOI":"10.1007\/3-540-36574-5_2"},{"issue":"6","key":"94_CR79","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33(6), 668\u2013676 (1990)","journal-title":"Commun. ACM"},{"key":"94_CR80","doi-asserted-by":"crossref","unstructured":"Rao, J., Ross, K.A.: Making B+-trees cache conscious in main memory. In: Proc. ACM SIGMOD Int. Conf. on the Management of Data, pp. 475\u2013486, Dallas (2000)","DOI":"10.1145\/342009.335449"},{"key":"94_CR81","unstructured":"Rose, K.R.: Asynchronous generic key\/value database. Master\u2019s thesis, Massachusetts Institute of Technology (2000)"},{"issue":"1","key":"94_CR82","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1145\/319540.319565","volume":"6","author":"A.L. Rosenberg","year":"1981","unstructured":"Rosenberg, A.L., Snyder, L.: Time and space optimality in B-trees. ACM Trans. Database Systems 6(1), 174\u2013193 (1981)","journal-title":"ACM Trans. Database Systems"},{"key":"94_CR83","volume-title":"Algorithms in C, Parts 1-4: Fundamentals, Data structures, Sorting, and Searching","author":"R. Sedgewick","year":"1998","unstructured":"Sedgewick, R.: Algorithms in C, Parts 1-4: Fundamentals, Data structures, Sorting, and Searching, 3rd edn. Addison-Wesley, Boston (1998)","edition":"3"},{"issue":"3","key":"94_CR84","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1145\/356631.356633","volume":"6","author":"D.G. Severance","year":"1974","unstructured":"Severance, D.G.: Identifier search mechanisms: a survey and generalized model. ACM Comput. Surv. 6(3), 175\u2013194 (1974)","journal-title":"ACM Comput. Surv."},{"key":"94_CR85","doi-asserted-by":"crossref","unstructured":"Sherk, M.: Self-adjusting k-ary search trees. In: Proc. of Workshop on Algorithms and Data Structures, pp. 381\u2013392, Ottawa (1989)","DOI":"10.1007\/3-540-51542-9_32"},{"key":"94_CR86","volume-title":"Operating System Concepts","author":"A. Silberschatz","year":"2004","unstructured":"Silberschatz, A., Galvin, P.B., Gagne, G.: Operating System Concepts, 7th edn. Wiley, Boston (2004)","edition":"7"},{"issue":"3","key":"94_CR87","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"key":"94_CR88","unstructured":"Software, T.M.: C++ string B-tree library (2007). http:\/\/wikipedia-clustering.speedblue.org\/strBTree.php"},{"key":"94_CR89","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032770","volume-title":"Average Case Analysis of Algorithms on Sequences","author":"W. Szpankowski","year":"2001","unstructured":"Szpankowski, W.: Average Case Analysis of Algorithms on Sequences, 1st edn. Wiley, New York City (2001)","edition":"1"},{"issue":"3","key":"94_CR90","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s00778-005-0154-8","volume":"14","author":"Y. Tian","year":"2005","unstructured":"Tian, Y., Tata, S., Hankins, R.A., Patel, J.M.: Practical methods for constructing suffix trees. Int. J. Very Large Databases 14(3), 281\u2013299 (2005)","journal-title":"Int. J. Very Large Databases"},{"issue":"2","key":"94_CR91","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. 33(2), 209\u2013271 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"10","key":"94_CR92","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1002\/spe.394","volume":"31","author":"H.E. Williams","year":"2001","unstructured":"Williams, H.E., Zobel, J., Heinz, S.: Self-adjusting trees in practice for large text collections. Softw. Practice Exp. 31(10), 925\u2013939 (2001)","journal-title":"Softw. Practice Exp."},{"key":"94_CR93","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"I.H. Witten","year":"1999","unstructured":"Witten, I.H., Bell, T.C., Moffat, A.: Managing Gigabytes: Compressing and Indexing Documents and Images, 1st edn. Morgan Kaufmann, San Francisco (1999)","edition":"1"},{"key":"94_CR94","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF00289075","volume":"9","author":"A.C. Yao","year":"1978","unstructured":"Yao, A.C.: On random 2-3 trees. Acta Inf. 9, 159\u2013170 (1978)","journal-title":"Acta Inf."},{"key":"94_CR95","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1132956.1132959","volume":"38","author":"J. Zobel","year":"2006","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38, 1\u201356 (2006)","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"94_CR96","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1145\/296854.277632","volume":"23","author":"J. Zobel","year":"1998","unstructured":"Zobel, J., Moffat, A., Ramamohanarao, K.: Inverted files versus signature files for text indexing. ACM Trans. Database Systems 23(4), 453\u2013490 (1998)","journal-title":"ACM Trans. Database Systems"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-008-0094-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-008-0094-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-008-0094-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T00:58:44Z","timestamp":1738112324000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-008-0094-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,11]]},"references-count":96,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["94"],"URL":"https:\/\/doi.org\/10.1007\/s00778-008-0094-1","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,11]]}}}