{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T21:40:08Z","timestamp":1736458808840,"version":"3.32.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,7,12]],"date-time":"2006-07-12T00:00:00Z","timestamp":1152662400000},"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":[[2007,1,29]]},"DOI":"10.1007\/s00778-006-0005-2","type":"journal-article","created":{"date-parts":[[2006,7,11]],"date-time":"2006-07-11T09:10:39Z","timestamp":1152609039000},"page":"269-291","source":"Crossref","is-referenced-by-count":7,"title":["Compression techniques for fast external sorting"],"prefix":"10.1007","volume":"16","author":[{"given":"John","family":"Yiannis","sequence":"first","affiliation":[]},{"given":"Justin","family":"Zobel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,7,12]]},"reference":[{"issue":"2","key":"5_CR1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/329.295","volume":"9","author":"M. Al-Suwaiye","year":"1984","unstructured":"Al-Suwaiye, M., Horwitz, E.: Algorthims for trie compation. ACM Trans. Database Syst. 9(2), 243\u2013263 (1984)","journal-title":"ACM Trans. Database Syst."},{"issue":"9","key":"5_CR2","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1002\/(SICI)1097-4571(199310)44:9<508::AID-ASI2>3.0.CO;2-A","volume":"44","author":"T.C. Bell","year":"1993","unstructured":"Bell, T.C., Moffat, A., Nevill-Manning, C.G., Witten, I.H., Zobel, J.: Data compression in full-text retrieval systems. J. Am. Soc. Inf. Sci. 44(9), 508\u2013531 (1993)","journal-title":"J. Am. Soc. Inf. Sci."},{"key":"5_CR3","unstructured":"Bentley, J., Sedgewick, R.: Fast alogorithms for sorting and searching strings. In: Proceedings of the 8th annual ACM-SIAM Symposium on Discrete algorithms, pp. 360\u2013369. New Orleans, USA (1997)"},{"issue":"11","key":"5_CR4","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1002\/spe.4380231105","volume":"23","author":"J.L. Bentley","year":"1993","unstructured":"Bentley, J.L., McIlroy, M.D.: Engineering a sort function. Software Pract. Exp. 23(11), 1249\u20131265 (1993)","journal-title":"Software Pract. Exp."},{"key":"5_CR5","unstructured":"Boncz, P.A., Manegold, S., Kersten, M.L.: Database architecture optimized for the new bottleneck: Memory access. In: Proceedings of the Very Large Data Bases {VLDB} Conference, pp. 54\u201365. Edinburgh, Scotland (1999)"},{"issue":"3","key":"5_CR6","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/568727.568730","volume":"20","author":"A. Cannane","year":"2002","unstructured":"Cannane, A., Williams, H.E.: A general-purpose compression scheme for large collections. ACM Trans. Inf. Syst. 20(3), 329\u2013355 (2002)","journal-title":"ACM Trans. Inf. Syst."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Z., Gehrke, J., Korn, F.: Query optimization in compressed database systems. In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 271\u2013282. Santa Barbara, California, USA (2001)","DOI":"10.1145\/375663.375692"},{"key":"5_CR8","unstructured":"Clement, J., Flajolet, P., Vallee, B.: The analysis of hybrid trie structures. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 531\u2013539. San Francisco, USA (1998)"},{"issue":"3","key":"5_CR9","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/322017.322023","volume":"24","author":"D. Comer","year":"1977","unstructured":"Comer, D., Sethi, R.: The complexity of trie index construction. J. ACM 24(3), 428\u2013440 (1977)","journal-title":"J. ACM"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Fredkin, E.: Trie memory. Commun. ACM 3(9), 490\u2013499 (1960)","DOI":"10.1145\/367390.367400"},{"key":"5_CR11","volume-title":"Database Systems Implementation","author":"H. Garcia-Molina","year":"2000","unstructured":"Garcia-Molina, H., Ullman, J.D., Widom, J.: Database Systems Implementation, 1st edn. Prentice-Hall, Upper Saddle River, NJ (2000)","edition":"1"},{"key":"5_CR12","unstructured":"Goldstein, J., Ramakrishnan, R., Shaft, U.: Compressing relations and indexes. In: Proceedings of the 14th International Conference on Data Engineering, pp. 370\u2013379. IEEE Computer Society, Orlando, Florida, USA (1998)"},{"issue":"2","key":"5_CR13","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1145\/152610.152611","volume":"25","author":"G. Graefe","year":"1993","unstructured":"Graefe, G.: Query evaluation techniques for large databases. ACM Comput. Survey 25(2), 152\u2013153 (1993)","journal-title":"ACM Comput. Survey"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Graefe, G., Shapiro, L.: Data compression and database performance. In: ACM\/IEEE-CS Symposium On Applied Computing, pp. 22\u201327 (1991)","DOI":"10.1109\/SOAC.1991.143840"},{"issue":"2","key":"5_CR15","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. Syst. 20(2), 192\u2013223 (2002)","journal-title":"ACM Trans. Inf. Syst."},{"key":"5_CR16","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd edn. Addison-Wesley, Reading, MA (1973)","edition":"2"},{"issue":"3","key":"5_CR17","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1145\/79147.79150","volume":"37","author":"L.L. Larmore","year":"1990","unstructured":"Larmore, L.L., Hirschberg, D.S.: A fast algorithm for optimal length-limited {H}uffman codes. J. ACM 37(3), 464\u2013473 (1990)","journal-title":"J. ACM"},{"issue":"4","key":"5_CR18","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1109\/TKDE.2003.1209012","volume":"15","author":"P.-A. Larson","year":"2003","unstructured":"Larson, P.-A.: External sorting: Run formation revisited. IEEE Trans. Knowledge Data Eng. 15(4), 961\u2013972 (2003)","journal-title":"IEEE Trans. Knowledge Data Eng."},{"issue":"4","key":"5_CR19","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1109\/TKDE.2002.1019210","volume":"14","author":"S. Manegold","year":"2002","unstructured":"Manegold, S., Boncz, P., Kersten, M.: Optimizing main-memory join on modern hardware. IEEE Trans. Knowledge Data Eng. 14(4), 709\u2013730 (2002)","journal-title":"IEEE Trans. Knowledge Data Eng."},{"key":"5_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0935-6","volume-title":"Compression and Coding Algorithms","author":"A. Moffat","year":"2002","unstructured":"Moffat, A., Turpin, A.: Compression and Coding Algorithms, 1st edn. Kluwer, Dordretch (2002)","edition":"1"},{"issue":"2","key":"5_CR21","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1109\/69.591454","volume":"9","author":"A. Moffat","year":"1997","unstructured":"Moffat, A., Zobel, J., Sharman, N.: Text compression for dynamic document databases. IEEE Trans. Knowledge Data Eng. 9(2), 302\u2013313 (1997)","journal-title":"IEEE Trans. Knowledge Data Eng."},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Nevill-Manning, C.G., Witten, I.H.: Phrase hierarchy inference and compression in bounded space. In: Proceedings of the Data Compression Conference, pp. 179\u2013188 (1998)","DOI":"10.1109\/DCC.1998.672146"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Ng, W.K., Ravishankar, C.V.: Relational database compression using augmented vector quantization. In: Proceedings of the Eleventh International Conference on Data Engineering, pp. 540\u2013549. IEEE Computer Society, Taipei, Taiwan (1995)","DOI":"10.1109\/ICDE.1995.380352"},{"issue":"4","key":"5_CR24","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1007\/BF01354877","volume":"4","author":"C. Nyberg","year":"1995","unstructured":"Nyberg, C., Barclay, T., Cvetanovic, Z., Gray, J., Lomet, D.: Alphasort: A cache-sensitive parallel external sort. VLDB J. 4(4), 603\u2013627 (1995)","journal-title":"VLDB J."},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Purdin, T.D.M.: Compressing tries for storing dictionaries. In: Proceedings of the IEEE Symposium on Applied Computing, pp. 336\u2013340, (1990)","DOI":"10.1109\/SOAC.1990.82193"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Ramakrishna, M.V., Zobel, J.: Performance in practice of string hashing functions. In: Proceedings of the Databases Systems for Advanced Applications Symposium, pp. 215\u2013223. Melbourne, Australia (1997)","DOI":"10.1142\/9789812819536_0023"},{"key":"5_CR27","volume-title":"Database Management Systems","author":"R. Ramakrishnan","year":"2000","unstructured":"Ramakrishnan, R., Gehrke, J.: Database Management Systems, 2nd edn. McGraw-Hill, New York (2000)","edition":"2"},{"issue":"1","key":"5_CR28","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/62032.77249","volume":"14","author":"R. Ramesh","year":"1989","unstructured":"Ramesh, R., Babu, A.J.G., Kincaid, J.P.: Variable-depth trie index optimization: Theory and experimental results. ACM Trans. Database Syst. 14(1), 41\u201374 (1989)","journal-title":"ACM Trans. Database Syst."},{"key":"5_CR29","unstructured":"Ray, G., Harista, J.R., Seshadri, S.: Database compression: A performance enhancement tool. In: Proceedings of the 7th International Conference on Management of Data (COMAD). Pune, India (1995)"},{"issue":"3","key":"5_CR30","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/163090.163096","volume":"22","author":"M. Roth","year":"1993","unstructured":"Roth, M., Van Horn, S.: Database compression. ACM SIGMOD Rec. 22(3), 31\u201339 (1993)","journal-title":"ACM SIGMOD Rec."},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Scholer, F., Williams, H.E., Yiannis, J., Zobel, J.: Compression of inverted indexes for fast query evaluation. In: Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 222\u2013229. Tampere, Finland (2002)","DOI":"10.1145\/564376.564416"},{"key":"5_CR32","volume-title":"Algorithms in C, Parts 1\u20134","author":"R. Sedgewick","year":"2002","unstructured":"Sedgewick, R.: Algorithms in C, Parts 1\u20134, 3rd edn. Addison-Wesley, Reading, MA (2002)","edition":"3"},{"key":"5_CR33","doi-asserted-by":"crossref","unstructured":"Sinha, R.: Using tries for cache-efficient efficient sorting of integers. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA International Workshop On Experimental Algorithmics, pp. 513\u2013528. Angra dos Reis, Brazil. Springer, Berlin. Published as LNCS 3059 (2004)","DOI":"10.1007\/978-3-540-24838-5_38"},{"key":"5_CR34","doi-asserted-by":"crossref","unstructured":"Sinha, R., Zobel, J.: Cache-conscious sorting of large sets of strings with dynamic tries. In: Ladner, R. (ed.) Proceedings of the 5th ALENEX Workshop on Algorithm Engineering and Experiments, pp. 93\u2013105. Baltimore, Maryland (2003)","DOI":"10.1145\/1005813.1041517"},{"key":"5_CR35","unstructured":"Sinha, R., Zobel, J.: Efficient trie-based sorting of large sets of strings. In: Proceedings of the Australasian Computer Science Conference, pp. 11\u201318. Adelaide, Australia (2003)"},{"issue":"2","key":"5_CR36","first-page":"209","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Trans. Database Syst. 33(2), 209\u2013271 (2001)","journal-title":"ACM Trans. Database Syst."},{"key":"5_CR37","doi-asserted-by":"crossref","unstructured":"Westman, T., Kossmann, D., Helmer, S., Moerkotte, G.: The implementation and performance of compressed databases. ACM SIGMOD Rec. 29(3) (2000)","DOI":"10.1145\/362084.362137"},{"key":"5_CR38","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/944618.944627","volume":"7","author":"R. Wickremesinghe","year":"2002","unstructured":"Wickremesinghe, R., Arge, L., Chase, J.S., Scott Vitter, J.: Efficient sorting using registers and caches. J. Exp. Algorithm. 7, 9\u201326 (2002)","journal-title":"J. Exp. Algorithm."},{"issue":"3","key":"5_CR39","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1093\/comjnl\/42.3.193","volume":"42","author":"H.E. Williams","year":"1999","unstructured":"Williams, H.E., Zobel, J.: Compressing integers for fast file access. Comput. J. 42(3), 193\u2013201 (1999)","journal-title":"Comput. J."},{"key":"5_CR40","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"I.H. Witten","year":"1999","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann, San Francisco, CA (1999)","edition":"2"},{"key":"5_CR41","doi-asserted-by":"crossref","unstructured":"Yiannis, J., Zobel, J.: External sorting with on-the-fly compression. In: James, A. (ed.) Proceedings of the British National Conference on Databases, pp. 115\u2013130. Coventry, UK, July (2003)","DOI":"10.1007\/3-540-45073-4_10"},{"issue":"8","key":"5_CR42","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1002\/spe.4380250804","volume":"25","author":"J. Zobel","year":"1995","unstructured":"Zobel, J., Moffat, A.: Adding compression to a full-text retrieval system. Software Pract. Exp. 25(8), 891\u2013903 (1995)","journal-title":"Software Pract. Exp."},{"key":"5_CR43","doi-asserted-by":"crossref","unstructured":"Zobel, J., Williams, H.E., Kimberley, S.: Trends in retrieval system performance. In: Edwards, J. (ed.) Proceedings of the Australasian Computer Science Conference, pp. 241\u2013248. Canberra, Australia (2000)","DOI":"10.1109\/ACSC.2000.824410"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-006-0005-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-006-0005-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-006-0005-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T21:25:43Z","timestamp":1736457943000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-006-0005-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7,12]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,29]]}},"alternative-id":["5"],"URL":"https:\/\/doi.org\/10.1007\/s00778-006-0005-2","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2006,7,12]]}}}