{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T08:50:04Z","timestamp":1784019004826,"version":"3.55.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T00:00:00Z","timestamp":1722902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Major Key Project of PCL","award":["PCL2022A03"],"award-info":[{"award-number":["PCL2022A03"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62372137"],"award-info":[{"award-number":["62372137"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Guangdong Major Project of Basic and Applied Basic Research","award":["2019B030302002"],"award-info":[{"award-number":["2019B030302002"]}]},{"name":"Shenzhen Science and Technology Program","award":["RCYX20210609104510007, KJZD20230923114610021"],"award-info":[{"award-number":["RCYX20210609104510007, KJZD20230923114610021"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2024,11,30]]},"abstract":"<jats:p>Delta encoding is a data reduction technique capable of calculating the differences (i.e., delta) among very similar files and chunks. It is widely used for various applications, such as synchronization replication, backup\/archival storage, cache compression, and so on. However, delta encoding is computationally costly due to its time-consuming word-matching operations for delta calculation. Existing delta encoding approaches either run at a slow encoding speed, such as Xdelta and Zdelta, or at a low compression ratio, such as Ddelta and Edelta. In this article, we propose Gdelta, a fast delta encoding approach with a high compression ratio. The key idea behind Gdelta is the combined use of five techniques: (1) employing an improved Gear-based rolling hash to replace Adler32 hash for fast scanning overlapping words of similar chunks, (2)\u00a0adopting a quick array-based indexing for word-matching, (3) applying a sampling indexing scheme to reduce the cost of traditional building full indexes for base chunks\u2019 words, (4) skipping unmatched words to accelerate delta encoding through non-redundant areas, and (5) last but not least, after word-matching, further batch compressing the remainder to improve the compression ratio. Our evaluation results driven by seven real-world datasets suggest that Gdelta achieves encoding\/decoding speedups of 3.5X\u223c25X over the classic Xdelta and Zdelta approaches while increasing the compression ratio by about 10%\u223c240%.<\/jats:p>","DOI":"10.1145\/3664817","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T11:04:16Z","timestamp":1715684656000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["The Design of Fast Delta Encoding for Delta Compression Based Storage Systems"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-9919-1926","authenticated-orcid":false,"given":"Haoliang","family":"Tan","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, China and Peng Cheng Laboratory, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4093-6391","authenticated-orcid":false,"given":"Wen","family":"Xia","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, China and Peng Cheng Laboratory, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5104-8301","authenticated-orcid":false,"given":"Xiangyu","family":"Zou","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7717-6990","authenticated-orcid":false,"given":"Cai","family":"Deng","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1012-5301","authenticated-orcid":false,"given":"Qing","family":"Liao","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, China and Peng Cheng Laboratory, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7546-852X","authenticated-orcid":false,"given":"Zhaoquan","family":"Gu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, Shenzhen, China and Peng Cheng Laboratory, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2018. New Generation Entropy Codecs: Finite State Entropy and Huff0. Retrieved 2023 from https:\/\/github.com\/Cyan4973\/FiniteStateEntropy"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1210596.1210599"},{"key":"e_1_3_2_4_2","first-page":"21","volume-title":"Proceedings of the Compression and Complexity of Sequences (SEQUENCES\u201997)","author":"Broder Andrei Z.","year":"1997","unstructured":"Andrei Z. Broder. 1997. On the resemblance and containment of documents. In Proceedings of the Compression and Complexity of Sequences (SEQUENCES\u201997). IEEE, Washington, DC, USA, 21\u201329."},{"key":"e_1_3_2_5_2","article-title":"Zstandard compression and the application\/zstd media type","author":"Collet Y.","year":"2018","unstructured":"Y. Collet and M. Kucherawy. 2018. Zstandard compression and the application\/zstd media type. RFC 8478 (2018).","journal-title":"RFC 8478"},{"key":"e_1_3_2_6_2","first-page":"1","volume-title":"Proceedings of the Slides from Linux Kongress","author":"Melo Arnaldo Carvalho De","year":"2010","unstructured":"Arnaldo Carvalho De Melo. 2010. The new linux\u2019perf\u2019tools. In Proceedings of the Slides from Linux Kongress. 1\u201342."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00085"},{"key":"e_1_3_2_8_2","article-title":"Zlib compressed data format specification version 3.3","author":"Deutsch Peter","year":"1996","unstructured":"Peter Deutsch and J.-L. Gailly. 1996. Zlib compressed data format specification version 3.3. RFC Editor. Retrieved from http:\/\/tools.ietf.org\/html\/rfc1950","journal-title":"RFC Editor"},{"key":"e_1_3_2_9_2","first-page":"481","volume-title":"Proceedings of the 2012 ACM Conference on Internet Measurement Conference (IMC\u201912)","year":"2012","unstructured":"Idilio Drago, Marco Mellia, Maurizio M. Munafo, Anna Sperotto, Ramin Sadre, and Aiko Pras. 2012. Inside dropbox: Understanding personal cloud storage services. In Proceedings of the 2012 ACM Conference on Internet Measurement Conference (IMC\u201912). ACM Association, Boston, MA, USA, 481\u2013494."},{"key":"e_1_3_2_10_2","unstructured":"Jarek Duda. 2013. Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. arXiv:1311.2540. Retrieved from https:\/\/arxiv.org\/abs\/1311.2540"},{"key":"e_1_3_2_11_2","unstructured":"J. L. Gailly and M. Adler. 1991. The GZIP Compressor. Retrieved from http:\/\/www.gzip.org\/"},{"key":"e_1_3_2_12_2","first-page":"309","volume-title":"Proceedings of the 8th Symposium on Operating Systems Design and Implementation (OSDI\u201908)","year":"2008","unstructured":"Diwaker Gupta, Sangmin Lee, Michael Vrable, Stefan Savage, Alex C. Snoeren, George Varghese, Geoffrey M. Voelker, and Amin Vahdat. 2008. Difference engine: Harnessing memory redundancy in virtual machines. In Proceedings of the 8th Symposium on Operating Systems Design and Implementation (OSDI\u201908). USENIX Association, San Diego, CA, USA, 309\u2013322."},{"issue":"9","key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","article-title":"A method for the construction of minimum redundancy codes","volume":"40","author":"Huffman David A.","year":"1952","unstructured":"David A. Huffman. 1952. A method for the construction of minimum redundancy codes. Proceedings of the IRE: Institute of Radio Engineers 40, 9 (1952), 1098\u20131101.","journal-title":"Proceedings of the IRE: Institute of Radio Engineers"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3568426"},{"key":"e_1_3_2_15_2","unstructured":"J. MacDonald. 2000. File system support for delta compression. Masters thesis. Department of Electrical Engineering and Computer Science University of California at Berkeley."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502052"},{"key":"e_1_3_2_17_2","first-page":"247","volume-title":"Proceedings of the 20th USENIX Conference on File and Storage Technologies (FAST\u201922)","author":"Park Jisung","year":"2022","unstructured":"Jisung Park, Jeonggyun Kim, Yeseong Kim, Sungjin Lee, and Onur Mutlu. 2022. DeepSketch: A new machine Learning-Based reference search technique for Post-Deduplication delta compression. In Proceedings of the 20th USENIX Conference on File and Storage Technologies (FAST\u201922). 247\u2013264."},{"key":"e_1_3_2_18_2","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201902)","author":"Quinlan S.","year":"2002","unstructured":"S. Quinlan and S. Dorward. 2002. Venti: A new approach to archival storage. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201902)."},{"key":"e_1_3_2_19_2","unstructured":"David Reinsel John Gantz and John Rydning. 2018. The digitization of the world from edge to core. IDC White Paper 16 (2018) 1\u201328."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2385603.2385606"},{"key":"e_1_3_2_21_2","volume-title":"Proceedings of the USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201912)","author":"Shilane Philip","year":"2012","unstructured":"Philip Shilane, Grant Wallace, Mark Huang, and Windsor Hsu. 2012. Delta compressed and deduplicated storage using stream-informed locality. In Proceedings of the USENIX Conference on Hot Topics in Storage and File Systems (HotStorage\u201912)."},{"key":"e_1_3_2_22_2","article-title":"Zdelta: An Efficient Delta Compression Tool","author":"Trendafilov Dimitre","year":"2002","unstructured":"Dimitre Trendafilov, Nasir Memon, and Torsten Suel. 2002. Zdelta: An Efficient Delta Compression Tool. Technical Report. Department of Computer and Information Science at Polytechnic University.","journal-title":"Technical Report. Department of Computer and Information Science at Polytechnic University."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00255"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3607536"},{"key":"e_1_3_2_25_2","volume-title":"Proceedings of the USENIX ATC","year":"2011","unstructured":"Wen Xia, Hong Jiang, Dan Feng, and Yu Hua. 2011. Silo: A similarity-locality based near-exact deduplication scheme with low ram overhead and high throughput. In Proceedings of the USENIX ATC."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2014.38"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.07.016"},{"key":"e_1_3_2_28_2","first-page":"1","volume-title":"Proceedings of the 7th USENIX conference on Hot Topics in Storage and File Systems (HotStorage\u201915)","author":"Xia Wen","year":"2015","unstructured":"Wen Xia, Chunguang Li, Hong Jiang, Dan Feng, Yu Hua, Leihua Qin, and Yucheng Zhang. 2015. Edelta: A word-enlarging based fast delta compression approach. In Proceedings of the 7th USENIX conference on Hot Topics in Storage and File Systems (HotStorage\u201915). USENIX Association, Santa Clara, CA, 1\u20135."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3584663"},{"key":"e_1_3_2_30_2","first-page":"101","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201916)","author":"Xia Wen","year":"2016","unstructured":"Wen Xia, Yukun Zhou, Hong Jiang, Dan Feng, Yu Hua, Yuchong Hu, Qing Liu, and Yucheng Zhang. 2016. FastCDC: A fast and efficient content-defined chunking approach for data deduplication. In Proceedings of the USENIX Annual Technical Conference (ATC\u201916). USENIX Association, Denver, CO, 101\u2013114."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035938"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2011.5749736"},{"key":"e_1_3_2_33_2","first-page":"133","volume-title":"Proceedings of the 2023 USENIX Annual Technical Conference (USENIX ATC\u201923)","author":"Zhang Yucheng","year":"2023","unstructured":"Yucheng Zhang, Hong Jiang, Dan Feng, Nan Jiang, Taorong Qiu, and Wei Huang. 2023. LoopDelta: Embedding locality-aware opportunistic delta compression in inline deduplication for highly efficient data reduction. In Proceedings of the 2023 USENIX Annual Technical Conference (USENIX ATC\u201923). 133\u2013148."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218510"},{"key":"e_1_3_2_35_2","first-page":"121","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201919)","author":"Zhang Yucheng","year":"2019","unstructured":"Yucheng Zhang, Wen Xia, Dan Feng, Hong Jiang, Yu Hua, and Qiang Wang. 2019. Finesse: Fine-grained feature locality based fast resemblance detection for post-deduplication delta compression. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201919). 121\u2013128."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00164"},{"key":"e_1_3_2_37_2","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201908)","author":"Zhu Benjamin","year":"2008","unstructured":"Benjamin Zhu, Kai Li, and R. Hugo Patterson. 2008. Avoiding the disk bottleneck in the data domain deduplication file system.. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201908). San Jose, CA, USA."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00048"},{"key":"e_1_3_2_41_2","first-page":"19","volume-title":"Proceedings of the 2022 USENIX Annual Technical Conference (USENIX ATC\u201922)","author":"Zou Xiangyu","year":"2022","unstructured":"Xiangyu Zou, Wen Xia, Philip Shilane, Haijun Zhang, and Xuan Wang. 2022. Building a high-performance fine-grained deduplication framework for backup storage with high deduplication ratio. In Proceedings of the 2022 USENIX Annual Technical Conference (USENIX ATC\u201922). 19\u201336."},{"key":"e_1_3_2_42_2","first-page":"171","volume-title":"Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST\u201921)","author":"Zou Xiangyu","year":"2021","unstructured":"Xiangyu Zou, Jingsong Yuan, Philip Shilane, Wen Xia, Haijun Zhang, and Xuan Wang. 2021. The dilemma between deduplication and locality: Can both be achieved?. In Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST\u201921). 171\u2013185."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3507921"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664817","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3664817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:29Z","timestamp":1750295849000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,6]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,11,30]]}},"alternative-id":["10.1145\/3664817"],"URL":"https:\/\/doi.org\/10.1145\/3664817","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,6]]},"assertion":[{"value":"2023-09-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}