{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,15]],"date-time":"2026-11-15T11:55:58Z","timestamp":1794743758035,"version":"4.9.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,3,23]],"date-time":"2015-03-23T00:00:00Z","timestamp":1427068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Basic Research Program (973 Program) of China","award":["2014CB340403"],"award-info":[{"award-number":["2014CB340403"]}]},{"name":"Fundamental Research Funds for the Central Universities and the Research Funds of Renmin University of China","award":["261437"],"award-info":[{"award-number":["261437"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["M13210007"],"award-info":[{"award-number":["M13210007"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada's","doi-asserted-by":"crossref","award":["261437"],"award-info":[{"award-number":["261437"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2015,3,23]]},"abstract":"<jats:p>Compression algorithms are important for data-oriented tasks, especially in the era of \u201cBig Data.\u201d Modern processors equipped with powerful SIMD instruction sets provide us with an opportunity for achieving better compression performance. Previous research has shown that SIMD-based optimizations can multiply decoding speeds. Following these pioneering studies, we propose a general approach to accelerate compression algorithms. By instantiating the approach, we have developed several novel integer compression algorithms, called Group-Simple, Group-Scheme, Group-AFOR, and Group-PFD, and implemented their corresponding vectorized versions. We evaluate the proposed algorithms on two public TREC datasets, a Wikipedia dataset, and a Twitter dataset. With competitive compression ratios and encoding speeds, our SIMD-based algorithms outperform state-of-the-art nonvectorized algorithms with respect to decoding speeds.<\/jats:p>","DOI":"10.1145\/2735629","type":"journal-article","created":{"date-parts":[[2015,3,24]],"date-time":"2015-03-24T12:26:59Z","timestamp":1427200019000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["A General SIMD-Based Approach to Accelerating Compression Algorithms"],"prefix":"10.1145","volume":"33","author":[{"given":"Wayne Xin","family":"Zhao","sequence":"first","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xudong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lemire","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongdong","family":"Shan","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jian-Yun","family":"Nie","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongfei","family":"Yan","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji-Rong","family":"Wen","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,3,23]]},"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.1109\/TKDE.2006.99"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.v40:2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956944"},{"key":"e_1_2_1_5_1","volume-title":"Information Retrieval: Implementing and Evaluating Search Engines","author":"B\u00fcttcher S.","year":"2010","unstructured":"S. B\u00fcttcher , C. Clarke , and G. V. Cormack . 2010 . Information Retrieval: Implementing and Evaluating Search Engines . MIT Press . S. B\u00fcttcher, C. Clarke, and G. V. Cormack. 2010. Information Retrieval: Implementing and Evaluating Search Engines. MIT Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.492.0377"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498759.1498761"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2010048"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2011.04.004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_11_1","series-title":"Version 37","volume-title":"Intel 64 and IA-32 Architectures Software Developers Manual","author":"Intel Corporation","unstructured":"Intel Corporation . 2010. Intel 64 and IA-32 Architectures Software Developers Manual ( Version 37 ) . Intel Corporation , Santa Clara, CA . Intel Corporation. 2010. Intel 64 and IA-32 Architectures Software Developers Manual (Version 37). Intel Corporation, Santa Clara, CA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070736.2070747"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 33rd European Conference on Advances in Information Retrieval. Springer","author":"Jonassen S.","unstructured":"S. Jonassen and S. E. Bratsberg . 2011. Efficient compressed inverted index skipping for disjunctive text-queries . In Proceedings of the 33rd European Conference on Advances in Information Retrieval. Springer , Berlin, 530--542. S. Jonassen and S. E. Bratsberg. 2011. Efficient compressed inverted index skipping for disjunctive text-queries. In Proceedings of the 33rd European Conference on Advances in Information Retrieval. Springer, Berlin, 530--542."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of IEEE Asian Solid-State Circuits Conference, 115--118","author":"Liu K.","unstructured":"K. Liu , X. Qin , X. Yan , and L. Quan . 2006. A SIMD video signal processor with efficient data organization . In Proceedings of IEEE Asian Solid-State Circuits Conference, 115--118 . K. Liu, X. Qin, X. Yan, and L. Quan. 2006. A SIMD video signal processor with efficient data organization. In Proceedings of IEEE Asian Solid-State Circuits Conference, 115--118."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 12th International Conference on Data Warehousing and Knowledge Discovery, 117--129","author":"Lemke C.","unstructured":"C. Lemke , K. U. Sattler , F. Faerber , and A. Zeier . 2010. Speeding up queries in column stores: A case for compression . In Proceedings of the 12th International Conference on Data Warehousing and Knowledge Discovery, 117--129 . C. Lemke, K. U. Sattler, F. Faerber, and A. Zeier. 2010. Speeding up queries in column stores: A case for compression. In Proceedings of the 12th International Conference on Data Warehousing and Knowledge Discovery, 117--129."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 2nd Annual ASCI Conference.","author":"Lomont C.","year":"2011","unstructured":"C. Lomont . 2011 . Introduction to Intel advanced vector extensions . In Proceedings of the 2nd Annual ASCI Conference. C. Lomont. 2011. Introduction to Intel advanced vector extensions. In Proceedings of the 2nd Annual ASCI Conference."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2203"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of IEEE Pacific Rim Conference on Multimedia. 1080--1087","author":"Ma W.","unstructured":"W. Ma and C. Yang . 2002. Using Intel streaming SIMD extensions for 3D geometry processing . In Proceedings of IEEE Pacific Rim Conference on Multimedia. 1080--1087 . W. Ma and C. Yang. 2002. Using Intel streaming SIMD extensions for 3D geometry processing. In Proceedings of IEEE Pacific Rim Conference on Multimedia. 1080--1087."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"C. D. Manning P. Raghavan and H. Sch\u00fctze. 2008. Introduction to Information Retrieval. Cambridge University Press. C. D. Manning P. Raghavan and H. Sch\u00fctze. 2008. Introduction to Information Retrieval. Cambridge University Press.","DOI":"10.1017\/CBO9780511809071"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009934302807"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1971.1090789"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"S. E. Robertson S. Walker M. Beaulieu and P. Willett. 1999. Okapi at TREC-7: Automatic ad hoc filtering VLC and interactive track. NIST Special Publication SP 253--264. S. E. Robertson S. Walker M. Beaulieu and P. Willett. 1999. Okapi at TREC-7: Automatic ad hoc filtering VLC and interactive track. NIST Special Publication SP 253--264.","DOI":"10.6028\/NIST.SP.500-242.okapi"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536233"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/564376.564416"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869389.1869394"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871592"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063627"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124346"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687671"},{"key":"e_1_2_1_31_1","unstructured":"T. Willhalm I. Oukid I. M\u00fcller and F. Faerber. 2013. Vectorizing database column scans with complex predicates. Accelerating Data Management Systems Using Modern Processor and Storage Architectures 1--12. T. Willhalm I. Oukid I. M\u00fcller and F. Faerber. 2013. Vectorizing database column scans with complex predicates. Accelerating Data Management Systems Using Modern Processor and Storage Architectures 1--12."},{"key":"e_1_2_1_32_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann.","author":"Witten I. H.","year":"1999","unstructured":"I. H. Witten , A. Moffat , and T. C. Bell . 1999 . Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann. I. H. Witten, A. Moffat, and T. C. Bell. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2011.06.019"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526764"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.150"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367550"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2735629","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2735629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:35Z","timestamp":1750227395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2735629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,23]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3,23]]}},"alternative-id":["10.1145\/2735629"],"URL":"https:\/\/doi.org\/10.1145\/2735629","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,23]]},"assertion":[{"value":"2014-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}