{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T08:07:20Z","timestamp":1787731640469,"version":"build-2784847793"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>Compression techniques that support fast random access are a core component of any information system. Current state-of-the-art methods group documents into fixed-sized blocks and compress each block with a general-purpose adaptive algorithm such as gzip. Random access to a specific document then requires decompression of a block. The choice of block size is critical: it trades between compression effectiveness and document retrieval times. In this paper we present a scalable compression method for large document collections that allows fast random access. We build a representative sample of the collection and use it as a dictionary in a LZ77-like encoding of the rest of the collection, relative to the dictionary. We demonstrate on large collections, that using a dictionary as small as 0.1% of the collection size, our algorithm is dramatically faster than previous methods, and in general gives much better compression.<\/jats:p>","DOI":"10.14778\/2078331.2078341","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"265-273","source":"Crossref","is-referenced-by-count":28,"title":["Relative Lempel-Ziv factorization for efficient storage and retrieval of web collections"],"prefix":"10.14778","volume":"5","author":[{"given":"Christopher","family":"Hoobin","sequence":"first","affiliation":[{"name":"School of Computer Science and Information Technology, RMIT University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, RMIT University and King's College London"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Justin","family":"Zobel","sequence":"additional","affiliation":[{"name":"University of Melbourne"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:INRT.0000048490.99518.5c"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(01)00097-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409360.1409376"},{"key":"e_1_2_1_4_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/978-3-540-70881-0_13","volume-title":"Perspectives of Systems Informatics","author":"Brisaboa N. R.","year":"2007","unstructured":"N. R. Brisaboa , A. Fari\u00f1a , G. Navarro , and J. R. Param\u00e1 . Improving semistatic compression via pair-based coding . In I. Virbitskaite and A. Voronkov, editors, Perspectives of Systems Informatics , volume 4378 of Lecture Notes in Computer Science , pages 124 -- 134 . Springer Berlin\/Heidelberg , 2007 . N. R. Brisaboa, A. Fari\u00f1a, G. Navarro, and J. R. Param\u00e1. Improving semistatic compression via pair-based coding. In I. Virbitskaite and A. Voronkov, editors, Perspectives of Systems Informatics, volume 4378 of Lecture Notes in Computer Science, pages 124--134. Springer Berlin\/Heidelberg, 2007."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-006-9001-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.v38:13"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1777432.1777433"},{"key":"e_1_2_1_8_1","first-page":"761","volume-title":"Proc. 16th ACM Conference on Information and Knowledge Management (CIKM'07)","author":"B\u00fcttcher S.","year":"2007","unstructured":"S. B\u00fcttcher and C. L. A. Clarke . Index compression is good, especially for random access . In Proc. 16th ACM Conference on Information and Knowledge Management (CIKM'07) , pages 761 -- 770 . ACM, 2007 . 10.1145\/1321440.1321546 S. B\u00fcttcher and C. L. A. Clarke. Index compression is good, especially for random access. In Proc. 16th ACM Conference on Information and Knowledge Management (CIKM'07), pages 761--770. ACM, 2007. 10.1145\/1321440.1321546"},{"key":"e_1_2_1_9_1","volume-title":"Information Retrieval: Implementing and Evaluating Search Engines","author":"B\u00fcttcher S.","year":"2010","unstructured":"S. B\u00fcttcher , C. L. A. Clarke , and G. V. Cormack . Information Retrieval: Implementing and Evaluating Search Engines . MIT Press , 2010 . S. B\u00fcttcher, C. L. A. Clarke, and G. V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines. MIT Press, 2010."},{"key":"e_1_2_1_10_1","first-page":"6","volume-title":"Proc. 11th Australasian Database Conference (ADC'00)","author":"Cannane A.","unstructured":"A. Cannane and H. E. Williams . A compression scheme for large databases . In Proc. 11th Australasian Database Conference (ADC'00) , page 6 . IEEE Computer Society, 2000. A. Cannane and H. E. Williams. A compression scheme for large databases. In Proc. 11th Australasian Database Conference (ADC'00), page 6. IEEE Computer Society, 2000."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/568727.568730"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"issue":"4","key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/s11786-007-0024-4","article-title":"Lempel-Ziv factorization using less time & space","volume":"1","author":"Chen G.","year":"2008","unstructured":"G. Chen , S. J. Puglisi , and W. F. Smyth . Lempel-Ziv factorization using less time & space . Mathematics in Computer Science , 1 ( 4 ): 605 -- 623 , 2008 . G. Chen, S. J. Puglisi, and W. F. Smyth. Lempel-Ziv factorization using less time & space. Mathematics in Computer Science, 1(4):605--623, 2008.","journal-title":"Mathematics in Computer Science"},{"key":"e_1_2_1_14_1","volume-title":"Search Engines: Information Retrieval in Practice","author":"Croft B.","year":"2010","unstructured":"B. Croft , D. Metzler , and T. Strohman . Search Engines: Information Retrieval in Practice . Addison-Wesley , 2010 . B. Croft, D. Metzler, and T. Strohman. Search Engines: Information Retrieval in Practice. Addison-Wesley, 2010."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/348751.348754"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1145\/1718487.1718536","volume-title":"Proc. 3rd ACM International Conference on Web Search and Data Mining (WSDM'10)","author":"Ferragina P.","year":"2010","unstructured":"P. Ferragina and G. Manzini . On compressing the textual web . In Proc. 3rd ACM International Conference on Web Search and Data Mining (WSDM'10) , pages 391 -- 400 . ACM, 2010 . 10.1145\/1718487.1718536 P. Ferragina and G. Manzini. On compressing the textual web. In Proc. 3rd ACM International Conference on Web Search and Data Mining (WSDM'10), pages 391--400. ACM, 2010. 10.1145\/1718487.1718536"},{"key":"e_1_2_1_17_1","volume-title":"Proc. 34th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'11)","author":"Hoobin C.","year":"2011","unstructured":"C. Hoobin , S. J. Puglisi , and J. Zobel . Sample selection for dictionary-based corpus compression . In Proc. 34th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'11) . ACM, 2011 . 10.1145\/2009916.2010087 C. Hoobin, S. J. Puglisi, and J. Zobel. Sample selection for dictionary-based corpus compression. In Proc. 34th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'11). ACM, 2011. 10.1145\/2009916.2010087"},{"issue":"9","key":"e_1_2_1_18_1","first-page":"1098","article-title":"A method for the construction of minimum-redundancy codes","volume":"40","author":"Huffman D.","year":"1952","unstructured":"D. Huffman . A method for the construction of minimum-redundancy codes . Proc. of the Institute of Radio Engineers , 40 ( 9 ): 1098 -- 1101 , 1952 . D. Huffman. A method for the construction of minimum-redundancy codes. Proc. of the Institute of Radio Engineers, 40(9):1098--1101, 1952.","journal-title":"Proc. of the Institute of Radio Engineers"},{"key":"e_1_2_1_19_1","first-page":"239","volume-title":"Proc. 20th IEEE Data Compression Conference (DCC'10)","author":"Kreft S.","year":"2010","unstructured":"S. Kreft and G. Navarro . LZ77-like compression with fast random access . In Proc. 20th IEEE Data Compression Conference (DCC'10) , pages 239 -- 248 . IEEE Computer Society , 2010 . 10.1109\/DCC.2010.29 S. Kreft and G. Navarro. LZ77-like compression with fast random access. In Proc. 20th IEEE Data Compression Conference (DCC'10), pages 239--248. IEEE Computer Society, 2010. 10.1109\/DCC.2010.29"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/978-3-642-16321-0_20","volume-title":"Proc. 17th Symposium on String Processing and Information Retrieval (SPIRE'10)","author":"Kuruppu S.","year":"2010","unstructured":"S. Kuruppu , S. J. Puglisi , and J. Zobel . Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval . In Proc. 17th Symposium on String Processing and Information Retrieval (SPIRE'10) , pages 201 -- 206 . Springer , 2010 . S. Kuruppu, S. J. Puglisi, and J. Zobel. Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval. In Proc. 17th Symposium on String Processing and Information Retrieval (SPIRE'10), pages 201--206. Springer, 2010."},{"key":"e_1_2_1_21_1","first-page":"296","volume-title":"Proc. 9th Data Compression Conference (DCC'99)","author":"Larsson N. J.","year":"1999","unstructured":"N. J. Larsson and A. Moffat . Offline dictionary-based compression . In Proc. 9th Data Compression Conference (DCC'99) , pages 296 -- 305 . IEEE Computer Society , March 1999 . N. J. Larsson and A. Moffat. Offline dictionary-based compression. In Proc. 9th Data Compression Conference (DCC'99), pages 296--305. IEEE Computer Society, March 1999."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to Information Retrieval","author":"Manning C. D.","year":"2008","unstructured":"C. D. Manning , P. Raghavan , and H. Sch\u00fctze . Introduction to Information Retrieval . Cambridge University Press , 2008 . C. D. Manning, P. Raghavan, and H. Sch\u00fctze. Introduction to Information Retrieval. Cambridge University Press, 2008."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380190207"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0935-6","volume-title":"Compression and Coding Algorithms","author":"Moffat A.","year":"2002","unstructured":"A. Moffat and A. Turpin . Compression and Coding Algorithms . Kluwer Academic Publishers , 2002 . A. Moffat and A. Turpin. Compression and Coding Algorithms. Kluwer Academic Publishers, 2002."},{"key":"e_1_2_1_26_1","first-page":"222","volume-title":"Proc. 25th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'02)","author":"Scholer F.","year":"2002","unstructured":"F. Scholer , H. E. Williams , J. Yiannis , and J. Zobel . Compression of inverted indexes for fast query evaluation . In Proc. 25th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'02) , pages 222 -- 229 . ACM, 2002 . 10.1145\/564376.564416 F. Scholer, H. E. Williams, J. Yiannis, and J. Zobel. Compression of inverted indexes for fast query evaluation. In Proc. 25th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'02), pages 222--229. ACM, 2002. 10.1145\/564376.564416"},{"key":"e_1_2_1_27_1","first-page":"2","volume-title":"Proc. 21st ACM SIGIR Internationl Conference on Research and Development in Information Retrieval (SIGIR'98)","author":"Tombros A.","year":"1998","unstructured":"A. Tombros and M. Sanderson . Advantages of query biased summaries in information retrieval . In Proc. 21st ACM SIGIR Internationl Conference on Research and Development in Information Retrieval (SIGIR'98) , pages 2 -- 10 . ACM, 1998 . 10.1145\/290941.290947 A. Tombros and M. Sanderson. Advantages of query biased summaries in information retrieval. In Proc. 21st ACM SIGIR Internationl Conference on Research and Development in Information Retrieval (SIGIR'98), pages 2--10. ACM, 1998. 10.1145\/290941.290947"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/978-3-642-00958-7_45","volume-title":"Proc. 31st European Conference on IR Research on Advances in Information Retrieval (ECIR'09)","author":"Tsegay Y.","year":"2009","unstructured":"Y. Tsegay , S. J. Puglisi , A. Turpin , and J. Zobel . Document compaction for efficient query biased snippet generation . In Proc. 31st European Conference on IR Research on Advances in Information Retrieval (ECIR'09) , pages 509 -- 520 . Springer-Verlag , 2009 . 10.1007\/978-3-642-00958-7_45 Y. Tsegay, S. J. Puglisi, A. Turpin, and J. Zobel. Document compaction for efficient query biased snippet generation. In Proc. 31st European Conference on IR Research on Advances in Information Retrieval (ECIR'09), pages 509--520. Springer-Verlag, 2009. 10.1007\/978-3-642-00958-7_45"},{"key":"e_1_2_1_29_1","first-page":"127","volume-title":"Proc. 30th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'07)","author":"Turpin A.","year":"2007","unstructured":"A. Turpin , Y. Tsegay , D. Hawking , and H. E. Williams . Fast generation of result snippets in web search . In Proc. 30th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'07) , pages 127 -- 134 . ACM, 2007 . 10.1145\/1277741.1277766 A. Turpin, Y. Tsegay, D. Hawking, and H. E. Williams. Fast generation of result snippets in web search. In Proc. 30th ACM SIGIR International Conference on Research and Development in Information Retrieval (SIGIR'07), pages 127--134. ACM, 2007. 10.1145\/1277741.1277766"},{"key":"e_1_2_1_30_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, 2. edition","author":"Witten I. H.","year":"1999","unstructured":"I. H. Witten , A. Moffat , and T. C. Bell . Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, 2. edition , 1999 . I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, 2. edition, 1999."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv J.","year":"1977","unstructured":"J. Ziv and A. Lempel . A universal algorithm for sequential data compression . IEEE Transactions on Information Theory , 23 : 337 -- 343 , 1977 . J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23:337--343, 1977.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv J.","year":"1978","unstructured":"J. Ziv and A. Lempel . Compression of individual sequences via variable-rate coding . IEEE Transactions on Information Theory , 24 ( 5 ): 530 -- 536 , 1978 . J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5):530--536, 1978.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1109\/18.243444","article-title":"A measure of relative entropy between individual sequences with application to universal classification","volume":"39","author":"Ziv J.","year":"1993","unstructured":"J. Ziv and N. Merhav . A measure of relative entropy between individual sequences with application to universal classification . IEEE Transactions on Information Theory , 39 ( 4 ): 1270 -- 1279 , 1993 . J. Ziv and N. Merhav. A measure of relative entropy between individual sequences with application to universal classification. IEEE Transactions on Information Theory, 39(4):1270--1279, 1993.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.881693"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380250804"},{"key":"e_1_2_1_36_1","first-page":"59","volume-title":"Proc. 22nd International Conference of Data Engineering (ICDE'06)","author":"Zukowski M.","unstructured":"M. Zukowski , S. H\u00e9man , N. Nes , and P. Boncz . Super-scalar RAM-CPU cache compression . In Proc. 22nd International Conference of Data Engineering (ICDE'06) , page 59 . IEEE Computer Society, 2006. 10.1109\/ICDE.2006.150 M. Zukowski, S. H\u00e9man, N. Nes, and P. Boncz. Super-scalar RAM-CPU cache compression. In Proc. 22nd International Conference of Data Engineering (ICDE'06), page 59. IEEE Computer Society, 2006. 10.1109\/ICDE.2006.150"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2078331.2078341","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:14:33Z","timestamp":1672222473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2078331.2078341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["10.14778\/2078331.2078341"],"URL":"https:\/\/doi.org\/10.14778\/2078331.2078341","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,11]]}}}