{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:14:46Z","timestamp":1792156486832,"version":"4.4.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,2]]},"abstract":"\n We introduce a new paradigm for querying strings in external memory, suited to the execution of sequences of operations. Formally, given a dictionary of\n n<\/jats:italic>\n strings\n S<\/jats:italic>\n 1<\/jats:sub>\n , \u2026,\n S<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n , we aim at supporting a search sequence for\n m<\/jats:italic>\n not necessarily distinct strings\n T<\/jats:italic>\n 1<\/jats:sub>\n ,\n T<\/jats:italic>\n 2<\/jats:sub>\n , \u2026,\n T<\/jats:italic>\n \n m<\/jats:italic>\n <\/jats:sub>\n , as well as inserting and deleting individual strings. The dictionary is stored on disk, where each access to a disk page fetches\n B<\/jats:italic>\n items, the cost of an operation is the number of pages accessed (I\/Os), and efficiency must be attained on entire sequences of string operations rather than on individual ones.\n <\/jats:p>\n \n Our approach relies on a novel and conceptually simple self-adjusting data structure (SASL) based on skip lists, that is also interesting\n per se<\/jats:italic>\n . The search for the whole sequence\n T<\/jats:italic>\n 1<\/jats:sub>\n ,\n T<\/jats:italic>\n 2<\/jats:sub>\n , \u2026,\n T<\/jats:italic>\n \n m<\/jats:italic>\n <\/jats:sub>\n can be done in an expected number of I\/Os:\n <\/jats:p>\n \n O<\/jats:italic>\n (\u2211\n \n j<\/jats:italic>\n =1\n <\/jats:sub>\n \n m<\/jats:italic>\n <\/jats:sup>\n |\n T<\/jats:italic>\n \n j<\/jats:italic>\n <\/jats:sub>\n |\/\n B<\/jats:italic>\n + \u2211\n \n i<\/jats:italic>\n =1\n <\/jats:sub>\n \n n<\/jats:italic>\n n\n <\/jats:sup>\n (\n n<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n log\n \n B<\/jats:italic>\n <\/jats:sub>\n m<\/jats:italic>\n \/\n n<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n )),\n <\/jats:p>\n \n where each\n T<\/jats:italic>\n \n j<\/jats:italic>\n <\/jats:sub>\n may or may not be present in the dictionary, and\n n<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n is the number of times\n S<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n is queried (i.e., the number of\n T<\/jats:italic>\n \n j<\/jats:italic>\n <\/jats:sub>\n s equal to\n S<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n ). Moreover, inserting or deleting a string\n S<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n takes an expected amortized number\n O<\/jats:italic>\n (|\n S<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n |\/\n B<\/jats:italic>\n + log\n \n B<\/jats:italic>\n <\/jats:sub>\n n<\/jats:italic>\n ) of I\/Os. The term \u2211\n \n j<\/jats:italic>\n =1\n <\/jats:sub>\n \n m<\/jats:italic>\n <\/jats:sup>\n |\n T<\/jats:italic>\n j<\/jats:sub>\n |\/\n B<\/jats:italic>\n in the search formula is a lower bound for reading the input, and the term \u2211\n \n i<\/jats:italic>\n =1\n <\/jats:sub>\n \n n<\/jats:italic>\n <\/jats:sup>\n n<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n log\n \n B<\/jats:italic>\n <\/jats:sub>\n m<\/jats:italic>\n \/\n n<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n (entropy of the query sequence) is a standard information-theoretic lower bound. We regard this result as the\n static optimality theorem for external-memory string access<\/jats:italic>\n , as compared to Sleator and Tarjan's classical theorem for numerical dictionaries [Sleator and Tarjan 1985]. Finally, we reformulate the search bound if a cache is available, taking advantage of common prefixes among the strings examined in the search.\n <\/jats:p>","DOI":"10.1145\/1186810.1186816","type":"journal-article","created":{"date-parts":[[2009,10,13]],"date-time":"2009-10-13T15:10:54Z","timestamp":1255446654000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A data structure for a sequence of string accesses in external memory"],"prefix":"10.1145","volume":"3","author":[{"given":"Valentina","family":"Ciriani","sequence":"first","affiliation":[{"name":"University of Milano, Via Bramante, Crema"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paolo","family":"Ferragina","sequence":"additional","affiliation":[{"name":"University of Pisa, Largo Pontecorro, Pisa"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrizio","family":"Luccio","sequence":"additional","affiliation":[{"name":"University of Pisa, Largo Pontecorro, Pisa"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,2,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases. 591--600","author":"Aboulnaga A.","unstructured":"Aboulnaga , A. , Alameldeen , A. R. , and Naughton , J. F . 2001. Estimating the selectivity of XML path expressions for Internet scale applications . In Proceedings of the 27th International Conference on Very Large Data Bases. 591--600 . Aboulnaga, A., Alameldeen, A. R., and Naughton, J. F. 2001. Estimating the selectivity of XML path expressions for Internet scale applications. In Proceedings of the 27th International Conference on Very Large Data Bases. 591--600."},{"key":"e_1_2_1_2_1","volume-title":"Information Theory and Coding","author":"Abramson N.","unstructured":"Abramson , N. 1983. Information Theory and Coding . McGraw-Hill , New York . Abramson, N. 1983. Information Theory and Coding. McGraw-Hill, New York."},{"key":"e_1_2_1_3_1","unstructured":"Ailamaki A. DeWitt D. J. Hill M. D. and Wood D. A. 1999. DBMSs on a modern processor: Where does time go? In Proceedings of the 25th International Conference on Very Large Data Bases. 266--277. Ailamaki A. DeWitt D. J. Hill M. D. and Wood D. A. 1999. DBMSs on a modern processor: Where does time go? In Proceedings of the 25th International Conference on Very Large Data Bases. 266--277."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 20th International Conference on Data Engineering. 720--731","author":"Bedathur S. J.","unstructured":"Bedathur , S. J. , and Haritsa , J. R . 2004. Engineering a fast online persistent suffix tree construction . In Proceedings of the 20th International Conference on Data Engineering. 720--731 . Bedathur, S. J., and Haritsa, J. R. 2004. Engineering a fast online persistent suffix tree construction. In Proceedings of the 20th International Conference on Data Engineering. 720--731."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1015-8"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 4th Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science","volume":"955","author":"Callahan P. B.","unstructured":"Callahan , P. B. , Goodrich , M. T. , and Ramaiyer , K . 1995. Topology B-trees and their applications . In Proceedings of the 4th Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science , vol. 955 , Springer Verlag. 381--392. Callahan, P. B., Goodrich, M. T., and Ramaiyer, K. 1995. Topology B-trees and their applications. In Proceedings of the 4th Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 955, Springer Verlag. 381--392."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.3"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases. 341--350","author":"Cooper B.","unstructured":"Cooper , B. , Sample , N. , Franklin , M. J. , Hjaltason , G. R. , and Shadmon , M . 2001. A fast index for semistructured data . In Proceedings of the 27th International Conference on Very Large Data Bases. 341--350 . Cooper, B., Sample, N., Franklin, M. J., Hjaltason, G. R., and Shadmon, M. 2001. A fast index for semistructured data. In Proceedings of the 27th International Conference on Very Large Data Bases. 341--350."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380843"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/129888.129896"},{"key":"e_1_2_1_12_1","volume-title":"Handbook of Computational Molecular Biology","author":"Ferragina P.","unstructured":"Ferragina , P. 2005. String search in external memory: Algorithms and data structures . In Handbook of Computational Molecular Biology , S. Aluru, ed., Chapman and Hall , London . Ferragina, P. 2005. String search in external memory: Algorithms and data structures. In Handbook of Computational Molecular Biology, S. Aluru, ed., Chapman and Hall, London."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 40th IEEE Symposium on the Foundations of Computer Science. 285--298","author":"Frigo M.","unstructured":"Frigo , M. , Leiserson , C. , Prokop , H. , and Ramachandran , S . 1999. Cache-Oblivious algorithms . In Proceedings of the 40th IEEE Symposium on the Foundations of Computer Science. 285--298 . Frigo, M., Leiserson, C., Prokop, H., and Ramachandran, S. 1999. Cache-Oblivious algorithms. In Proceedings of the 40th IEEE Symposium on the Foundations of Computer Science. 285--298."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.535"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science","volume":"1644","author":"Grossi R.","unstructured":"Grossi , R. , and Italiano , G . 1999. Efficient techniques for maintaining multidimensional keys in linked data structures . In Proceedings of the 26th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science , vol. 1644 . Springer Verlag. 372--381. Grossi, R., and Italiano, G. 1999. Efficient techniques for maintaining multidimensional keys in linked data structures. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 1644. Springer Verlag. 372--381."},{"key":"e_1_2_1_17_1","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield D.","unstructured":"Gusfield , D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology . Cambridge University Press , New York . Gusfield, D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200064"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 516--522","author":"Iacono J.","year":"2001","unstructured":"Iacono , J. 2001 . Alternatives to splay trees with o(log n) worst-case times . In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 516--522 . Iacono, J. 2001. Alternatives to splay trees with o(log n) worst-case times. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms. 516--522."},{"key":"e_1_2_1_20_1","volume-title":"Lecture Notes in Computer Science","volume":"2625","author":"K\u00e4rkk\u00e4inen J.","unstructured":"K\u00e4rkk\u00e4inen , J. , and Rao , S . 2003. Full-Text indexes in external memory. In Algorithms for Memory Hierarchies, U. Meyer et al. eds . Lecture Notes in Computer Science , vol. 2625 . Springer Verlag, 149--170. K\u00e4rkk\u00e4inen, J., and Rao, S. 2003. Full-Text indexes in external memory. In Algorithms for Memory Hierarchies, U. Meyer et al. eds. Lecture Notes in Computer Science, vol. 2625. Springer Verlag, 149--170."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90235-A"},{"key":"e_1_2_1_23_1","volume-title":"Data Structures and Algorithms 1: Searching and Sorting. EATCS Monographs on Theoretical Computer Science","author":"Mehlhorn K.","unstructured":"Mehlhorn , K. 1984. Data Structures and Algorithms 1: Searching and Sorting. EATCS Monographs on Theoretical Computer Science , vol. 1 . Springer Verlag . Mehlhorn, K. 1984. Data Structures and Algorithms 1: Searching and Sorting. EATCS Monographs on Theoretical Computer Science, vol. 1. Springer Verlag."},{"key":"e_1_2_1_24_1","volume-title":"IFIP World Computer Congress","volume":"1","author":"Mehlhorn K.","unstructured":"Mehlhorn , K. , and Naher , S . 1992. Algorithm design and software libraries: Recent developments in the Leda project . In IFIP World Computer Congress , vol. 1 , 493--505. Mehlhorn, K., and Naher, S. 1992. Algorithm design and software libraries: Recent developments in the Leda project. In IFIP World Computer Congress, vol. 1, 493--505."},{"key":"e_1_2_1_25_1","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"Mulmuley K.","year":"1994","unstructured":"Mulmuley , K. 1994 . Computational Geometry: An Introduction Through Randomized Algorithms . Prentice-Hall , Upper Saddle River, NJ. Mulmuley, K. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Upper Saddle River, NJ."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1026"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 13th International Conference on Very Large Data Bases. 36--47","author":"Tata S.","unstructured":"Tata , S. , Hankins , R. A. , and Patel , J. M . 2004. Practical suffix tree construction . In Proceedings of the 13th International Conference on Very Large Data Bases. 36--47 . Tata, S., Hankins, R. A., and Patel, J. M. 2004. Practical suffix tree construction. In Proceedings of the 13th International Conference on Very Large Data Bases. 36--47."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/234752.234753"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 21st IEEE INFOCOM Conference. 1238--1247","author":"Xie Y.","year":"2002","unstructured":"Xie , Y. , and O'Hallaran , D. 2002 . Locality in search engine queries and its implications for caching . In Proceedings of the 21st IEEE INFOCOM Conference. 1238--1247 . Xie, Y., and O'Hallaran, D. 2002. Locality in search engine queries and its implications for caching. In Proceedings of the 21st IEEE INFOCOM Conference. 1238--1247."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1186810.1186816","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:34:23Z","timestamp":1672263263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1186810.1186816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2]]},"references-count":32,"aliases":["10.1145\/1219944.1219952"],"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,2]]}},"alternative-id":["10.1145\/1186810.1186816"],"URL":"https:\/\/doi.org\/10.1145\/1186810.1186816","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2]]},"assertion":[{"value":"2007-02-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}