{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T10:59:19Z","timestamp":1780743559158,"version":"3.54.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,11]]},"abstract":"<jats:p>\n            Suffix trees and suffix arrays are widely used and largely interchangeable index structures on strings and sequences. Practitioners prefer suffix arrays due to their simplicity and space efficiency while theoreticians use suffix trees due to linear-time construction algorithms and more explicit structure. We narrow this gap between theory and practice with a simple linear-time construction algorithm for suffix arrays. The simplicity is demonstrated with a C++ implementation of 50 effective lines of code. The algorithm is called DC3, which stems from the central underlying concept of\n            <jats:italic>difference cover<\/jats:italic>\n            . This view leads to a generalized algorithm, DC, that allows a space-efficient implementation and, moreover, supports the choice of a space--time tradeoff. For any\n            <jats:italic>v<\/jats:italic>\n            \u2208 [1,\n            <jats:italic>\u221an<\/jats:italic>\n            ], it runs in O(\n            <jats:italic>vn<\/jats:italic>\n            ) time using O(\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>\u221av<\/jats:italic>\n            ) space in addition to the input string and the suffix array. We also present variants of the algorithm for several parallel and hierarchical memory models of computation. The algorithms for BSP and EREW-PRAM models are asymptotically faster than all previous suffix tree or array construction algorithms.\n          <\/jats:p>","DOI":"10.1145\/1217856.1217858","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"918-936","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":314,"title":["Linear work suffix array construction"],"prefix":"10.1145","volume":"53","author":[{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"first","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"University of Karlsruhe, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Burkhardt","sequence":"additional","affiliation":[{"name":"Google, Inc., Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00065-0"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 9th International Symposium on String Processing and Information Retrieval. Lecture Notes in Computer Science","volume":"2476","author":"Abouelhoda M. I.","unstructured":"Abouelhoda , M. I. , Ohlebusch , E. , and Kurtz , S . 2002. Optimal exact string matching based on suffix arrays . In Proceedings of the 9th International Symposium on String Processing and Information Retrieval. Lecture Notes in Computer Science , vol. 2476 . Springer-Verlag, Berlin\/Heidelberg, Germany, 31--43. Abouelhoda, M. I., Ohlebusch, E., and Kurtz, S. 2002. Optimal exact string matching based on suffix arrays. In Proceedings of the 9th International Symposium on String Processing and Information Retrieval. Lecture Notes in Computer Science, vol. 2476. Springer-Verlag, Berlin\/Heidelberg, Germany, 31--43."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009260"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002060"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science","volume":"2676","author":"Burkhardt S.","unstructured":"Burkhardt , S. , and K\u00e4rkk\u00e4inen , J . 2003. Fast lightweight suffix array construction and checking . In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science , vol. 2676 . Springer-Verlag Berlin\/Heidelberg, Germany, 55--69. Burkhardt, S., and K\u00e4rkk\u00e4inen, J. 2003. Fast lightweight suffix array construction and checking. In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag Berlin\/Heidelberg, Germany, 55--69."},{"key":"e_1_2_1_6_1","volume-title":"Tech. Rep. 124, SRC (digital, Palo Alto).","author":"Burrows M.","year":"1994","unstructured":"Burrows , M. , and Wheeler , D. J . 1994 . A block-sorting lossless data compression algorithm. Tech. Rep. 124, SRC (digital, Palo Alto). Burrows, M., and Wheeler, D. J. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124, SRC (digital, Palo Alto)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626499000499"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science","volume":"2676","author":"Clifford R.","unstructured":"Clifford , R. , and Sergot , M . 2003. Distributed and paged suffix trees for large genetic databases . In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science , vol. 2676 . Springer-Verlag Berlin\/Heidelberg, Germany, 70--82. Clifford, R., and Sergot, M. 2003. Distributed and paged suffix trees for large genetic databases. In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag Berlin\/Heidelberg, Germany, 70--82."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00080-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0051-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Crochemore M. and Rytter W. 2002. Jewels of Stringology. World Scientific Singapore.  Crochemore M. and Rytter W. 2002. Jewels of Stringology. World Scientific Singapore.","DOI":"10.1142\/4838"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1402296"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777435"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796326"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Farach M.","unstructured":"Farach , M. , Ferragina , P. , and Muthukrishnan , S . 1998. Overcoming the memory bottleneck in suffix tree construction . In Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, 174--183. Farach, M., Ferragina, P., and Muthukrishnan, S. 1998. Overcoming the memory bottleneck in suffix tree construction. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 174--183."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 23th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science","volume":"1099","author":"Farach M.","unstructured":"Farach , M. , and Muthukrishnan , S . 1996. Optimal logarithmic time randomized suffix tree construction . In Proceedings of the 23th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science , vol. 1099 . Springer-Verlag London, UK, 550--561. Farach, M., and Muthukrishnan, S. 1996. Optimal logarithmic time randomized suffix tree construction. In Proceedings of the 23th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 1099. Springer-Verlag London, UK, 550--561."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Frigo M.","unstructured":"Frigo , M. , Leiserson , C. E. , Prokop , H. , and Ramachandran , S . 1999. Cache-oblivious algorithms . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, 285--298. Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 285--298."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00104-6"},{"key":"e_1_2_1_22_1","unstructured":"Gonnet G. Baeza-Yates R. and Snider T. 1992. New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures & Algorithms W. B. Frakes and R. Baeza-Yates Eds. Prentice-Hall Englewood Cliffs NJ.   Gonnet G. Baeza-Yates R. and Snider T. 1992. New indices for text: PAT trees and PAT arrays. In Information Retrieval: Data Structures & Algorithms W. B. Frakes and R. Baeza-Yates Eds. Prentice-Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294141"},{"key":"e_1_2_1_24_1","unstructured":"Grossi R. and Italiano G. F. 1996. Suffix trees and their applications in string algorithms. Rapporto di Ricerca CS-96-14 Universit\u00e0 \u201cCa' Foscari\u201d di Venezia Italy.  Grossi R. and Italiano G. F. 1996. Suffix trees and their applications in string algorithms. Rapporto di Ricerca CS-96-14 Universit\u00e0 \u201cCa' Foscari\u201d di Venezia Italy."},{"key":"e_1_2_1_25_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 , Cambridge, UK . Gusfield, D. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Hagerup T.","unstructured":"Hagerup , T. , and Raman , R . 1992. Waste makes haste: Tight bounds for loose parallel sorting . In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, 628--637. Hagerup, T., and Raman, R. 1992. Waste makes haste: Tight bounds for loose parallel sorting. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 628--637."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90138-5"},{"key":"e_1_2_1_28_1","volume-title":"-K","author":"Hon W.-K.","year":"2003","unstructured":"Hon , W.-K. , Lam , T.-W. , Sadakane , K. , and Sung , W . -K . 2003 a. Constructing compressed suffix arrays with large alphabets. In Proceedings of the 14th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2906 . Springer , Berlin\/Heidelberg, Germany, 240--249. Hon, W.-K., Lam, T.-W., Sadakane, K., and Sung, W.-K. 2003a. Constructing compressed suffix arrays with large alphabets. In Proceedings of the 14th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2906. Springer, Berlin\/Heidelberg, Germany, 240--249."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 44th Annual Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Hon W.-K.","unstructured":"Hon , W.-K. , Sadakane , K. , and Sung , W . -K. 2003b. Breaking a time-and-space barrier in constructing full-text indices . In Proceedings of the 44th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, 251--260. Hon, W.-K., Sadakane, K., and Sung, W.-K. 2003b. Breaking a time-and-space barrier in constructing full-text indices. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 251--260."},{"key":"e_1_2_1_30_1","volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e1j\u00e1 J.","unstructured":"J\u00e1j\u00e1 , J. 1992. An Introduction to Parallel Algorithms . Addison Wesley , Reading, MA . J\u00e1j\u00e1, J. 1992. An Introduction to Parallel Algorithms. Addison Wesley, Reading, MA."},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching","author":"K\u00e4rkk\u00e4inen J.","unstructured":"K\u00e4rkk\u00e4inen , J. 1995. Suffix cactus: A cross between suffix tree and suffix array . In Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching . Lecture Notes in Computer Science , vol. 937 . Springer-Verlag , Berlin\/ Heidelberg, UK , 191--204. K\u00e4rkk\u00e4inen, J. 1995. Suffix cactus: A cross between suffix tree and suffix array. In Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 937. Springer-Verlag, Berlin\/Heidelberg, UK, 191--204."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen J. 2006. Fast BWT in small space by blockwise suffix sorting. Theor. Comput. Sci. To appear.  K\u00e4rkk\u00e4inen J. 2006. Fast BWT in small space by blockwise suffix sorting. Theor. Comput. Sci. To appear.","DOI":"10.1016\/j.tcs.2007.07.018"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 30th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science","volume":"2719","author":"K\u00e4rkk\u00e4inen J.","unstructured":"K\u00e4rkk\u00e4inen , J. , and Sanders , P . 2003. Simple linear work suffix array construction . In Proceedings of the 30th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science , vol. 2719 . Springer-Verlag, Berlin\/Heidelberg, Germany, 943--955. K\u00e4rkk\u00e4inen, J., and Sanders, P. 2003. Simple linear work suffix array construction. In Proceedings of the 30th International Conference on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2719. Springer-Verlag, Berlin\/Heidelberg, Germany, 943--955."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 2nd Annual International Conference on Computing and Combinatorics. Lecture Notes in Computer Science","volume":"1090","author":"K\u00e4rkk\u00e4inen J.","unstructured":"K\u00e4rkk\u00e4inen , J. , and Ukkonen , E . 1996. Sparse suffix trees . In Proceedings of the 2nd Annual International Conference on Computing and Combinatorics. Lecture Notes in Computer Science , vol. 1090 . Springer-Verlag, Berlin\/Heidelberg, Germany, 219--230. K\u00e4rkk\u00e4inen, J., and Ukkonen, E. 1996. Sparse suffix trees. In Proceedings of the 2nd Annual International Conference on Computing and Combinatorics. Lecture Notes in Computer Science, vol. 1090. Springer-Verlag, Berlin\/Heidelberg, Germany, 219--230."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science","volume":"2089","author":"Kasai T.","unstructured":"Kasai , T. , Lee , G. , Arimura , H. , Arikawa , S. , and Park , K . 2001. Linear-time longest-common-prefix computation in suffix arrays and its applications . In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science , vol. 2089 . Springer-Verlag, Berlin\/Heidelberg, Germany, 181--192. Kasai, T., Lee, G., Arimura, H., Arikawa, S., and Park, K. 2001. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 2089. Springer-Verlag, Berlin\/Heidelberg, Germany, 181--192."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.61044"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.019"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.002"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11846802_12"},{"key":"e_1_2_1_40_1","volume-title":"S.-M.","author":"Lam T.-W.","year":"2002","unstructured":"Lam , T.-W. , Sadakane , K. , and Sung , W . -K., and Yiu , S.-M. 2002 . A space and time efficient algorithm for constructing compressed suffix arrays. In Proceedings of the 8th Annual Itnternational Conference on Computing and Combinatorics. Lecture Notes in Computer Science, vol. 2387 . Springer-Verlag , Berlin\/Heidelberg, Germany, 401--410. Lam, T.-W., Sadakane, K., and Sung, W.-K., and Yiu, S.-M. 2002. A space and time efficient algorithm for constructing compressed suffix arrays. In Proceedings of the 8th Annual Itnternational Conference on Computing and Combinatorics. Lecture Notes in Computer Science, vol. 2387. Springer-Verlag, Berlin\/Heidelberg, Germany, 401--410."},{"key":"e_1_2_1_41_1","volume-title":"Tech. Rep. LU-CS-TR:99-214, Dept. Computer Science","author":"Larsson N. J.","year":"1999","unstructured":"Larsson , N. J. , and Sadakane , K . 1999 . Faster suffix sorting. Tech. Rep. LU-CS-TR:99-214, Dept. Computer Science , Lund University , Sweden . Larsson, N. J., and Sadakane, K. 1999. Faster suffix sorting. Tech. Rep. LU-CS-TR:99-214, Dept. Computer Science, Lund University, Sweden."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 17th International Conference on Distributed Computing Systems. IEEE Computer Society","author":"Luk W.-S.","unstructured":"Luk , W.-S. , and Wong , T . -T. 1997. Two new quorum based algorithms for distributed mutual exclusion . In Proceedings of the 17th International Conference on Distributed Computing Systems. IEEE Computer Society , Los Alamitos, CA, 100--106. Luk, W.-S., and Wong, T.-T. 1997. Two new quorum based algorithms for distributed mutual exclusion. In Proceedings of the 17th International Conference on Distributed Computing Systems. IEEE Computer Society, Los Alamitos, CA, 100--106."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_44_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th Scandinavian Workshop on Algorithm Theory","author":"Manzini G.","unstructured":"Manzini , G. 2004. Two space saving tricks for linear time LCP array computation . In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory . Lecture Notes in Computer Science , vol. 3111 . Springer-Verlag , Berlin\/ Heidelberg, Germany , 372--383. Manzini, G. 2004. Two space saving tricks for linear time LCP array computation. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 3111. Springer-Verlag, Berlin\/Heidelberg, Germany, 372--383."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1094-1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_47_1","first-page":"5","article-title":"Engineering radix sort","volume":"6","author":"McIlroy P. M.","year":"1993","unstructured":"McIlroy , P. M. , Bostic , K. , and McIlroy , M. D. 1993 . Engineering radix sort . Comput. Syst. 6 , 1, 5 -- 27 . McIlroy, P. M., Bostic, K., and McIlroy, M. D. 1993. Engineering radix sort. Comput. Syst. 6, 1, 5--27.","journal-title":"Comput. Syst."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/11496656_6"},{"key":"e_1_2_1_49_1","first-page":"205","article-title":"A hybrid indexing method for approximate string matching","volume":"1","author":"Navarro G.","year":"2000","unstructured":"Navarro , G. , and Baeza-Yates , R. 2000 . A hybrid indexing method for approximate string matching . J. Disc. Algor. 1 , 1, 205 -- 239 . (Special issue on Matching Patterns.) Navarro, G., and Baeza-Yates, R. 2000. A hybrid indexing method for approximate string matching. J. Disc. Algor. 1, 1, 205--239. (Special issue on Matching Patterns.)","journal-title":"J. Disc. Algor."},{"key":"e_1_2_1_50_1","first-page":"2","article-title":"The Flashsort1 algorithm","volume":"23","author":"Neubert K.-D.","year":"1998","unstructured":"Neubert , K.-D. 1998 . The Flashsort1 algorithm . Dr. Dobb's J. 23 , 2 (Feb.), 123--125. Neubert, K.-D. 1998. The Flashsort1 algorithm. Dr. Dobb's J. 23, 2 (Feb.), 123--125.","journal-title":"Dr. Dobb's J."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165247"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210343"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.87"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"e_1_2_1_55_1","unstructured":"Smyth B. 2003. Computing Patterns in Strings. Pearson Addison--Wesley Harlow England.  Smyth B. 2003. Computing Patterns in Strings. Pearson Addison--Wesley Harlow England."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_58_1","volume-title":"I: Two level memories. Algorithmica 12, 2\/3, 110--147.","author":"Vitter J. S.","year":"1994","unstructured":"Vitter , J. S. , and Shriver , E. A. M . 1994 . Algorithms for parallel memory, I: Two level memories. Algorithmica 12, 2\/3, 110--147. Vitter, J. S., and Shriver, E. A. M. 1994. Algorithms for parallel memory, I: Two level memories. Algorithmica 12, 2\/3, 110--147."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_2_1_60_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann","author":"Witten I. H.","year":"1999","unstructured":"Witten , I. H. , Moffat , A. , and Bell , T. C . 1999 . Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann , San Francisco, CA . Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, San Francisco, CA."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1217856.1217858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:32:00Z","timestamp":1672263120000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1217856.1217858"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11]]},"references-count":60,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2006,11]]}},"alternative-id":["10.1145\/1217856.1217858"],"URL":"https:\/\/doi.org\/10.1145\/1217856.1217858","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,11]]},"assertion":[{"value":"2006-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}