{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:26:55Z","timestamp":1772119615720,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002957","name":"Technische Universit\u00e4t Dresden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002957","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Integer compression plays an important role in columnar database systems to reduce the main memory footprint as well as to speedup query processing. To keep the additional computational effort of (de)compression as low as possible, the powerful\n                    <jats:italic>Single Instruction Multiple Data<\/jats:italic>\n                    (\n                    <jats:italic>SIMD<\/jats:italic>\n                    ) extensions of modern CPUs are heavily applied. While a scalar compression algorithm usually compresses a block of\n                    <jats:italic>N<\/jats:italic>\n                    consecutive integers, the state-of-the-art\n                    <jats:italic>SIMDified<\/jats:italic>\n                    implementation scales the block size to\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$k \\cdot N$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:mi>N<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with\n                    <jats:italic>k<\/jats:italic>\n                    as the number of elements which could be simultaneously processed in an SIMD register. On the one hand, this scaling SIMD approach improves the performance of (de)compression. But on the other hand, it can lead to a degradation of the memory footprint of the compressed data. Within this article, we analyze this degradation effect for various integer compression algorithms and present a novel SIMD concept to overcome that effect. The core idea of our novel SIMD concept called\n                    <jats:italic>BOUNCE<\/jats:italic>\n                    is to concurrently compress\n                    <jats:italic>k<\/jats:italic>\n                    different blocks of size\n                    <jats:italic>N<\/jats:italic>\n                    within SIMD registers, guaranteeing the same compression ratio as scalar variant. As we are going to show, our proposed SIMD idea works well on various Intel CPUs and may offer a new generalized SIMD concept to optimize further algorithms.\n                  <\/jats:p>","DOI":"10.1007\/s10619-023-07426-0","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T05:22:50Z","timestamp":1683782570000},"page":"439-466","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["BOUNCE: memory-efficient SIMD approach for lightweight integer compression"],"prefix":"10.1007","volume":"41","author":[{"given":"Juliana","family":"Hildebrandt","sequence":"first","affiliation":[]},{"given":"Dirk","family":"Habich","sequence":"additional","affiliation":[]},{"given":"Wolfgang","family":"Lehner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,10]]},"reference":[{"key":"7426_CR1","doi-asserted-by":"publisher","unstructured":"Lomet, D.B.: Cost\/performance in modern data stores: how data caching systems succeed. In: Lehner, W., Salem, K. (eds.) Proceedings of the 14th International Workshop on Data Management on New Hardware, Houston, TX, June 11, 2018, pp. 9\u20131910. ACM (2018). https:\/\/doi.org\/10.1145\/3211922.3211927","DOI":"10.1145\/3211922.3211927"},{"key":"7426_CR2","doi-asserted-by":"publisher","unstructured":"Abadi, D.J., Madden, S., Ferreira, M.: Integrating compression and execution in column-oriented database systems. In: Chaudhuri, S., Hristidis, V., Polyzotis, N. (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, IL, June 27\u201329, 2006, pp. 671\u2013682. ACM (2006). https:\/\/doi.org\/10.1145\/1142473.1142548","DOI":"10.1145\/1142473.1142548"},{"issue":"11","key":"7426_CR3","doi-asserted-by":"publisher","first-page":"2396","DOI":"10.14778\/3407790.3407833","volume":"13","author":"P Damme","year":"2020","unstructured":"Damme, P., Ungeth\u00fcm, A., Pietrzyk, J., Krause, A., Habich, D., Lehner, W.: Morphstore: analytical query engine with a holistic compression-enabled processing model. Proc. VLDB Endow. 13(11), 2396\u20132410 (2020)","journal-title":"Proc. VLDB Endow."},{"key":"7426_CR4","unstructured":"Landgraf, L., Lehner, W., Wolf, F., Boehm, A.: Memory efficient scheduling of query pipeline execution. In: 12th Conference on Innovative Data Systems Research, CIDR 2022, Chaminade, CA, January 9\u201312, 2022. (2022). www.cidrdb.org, https:\/\/www.cidrdb.org\/cidr2022\/papers\/p82-landgraf.pdf"},{"key":"7426_CR5","doi-asserted-by":"publisher","unstructured":"Boissier, M., Jendruk, M.: Workload-driven and robust selection of compression schemes for column stores. In: Herschel, M., Galhardas, H., Reinwald, B., Fundulaki, I., Binnig, C., Kaoudi, Z. (eds.) Advances in Database Technology\u201422nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, March 26\u201329, 2019, pp. 674\u2013677. OpenProceedings.org (2019). https:\/\/doi.org\/10.5441\/002\/edbt.2019.84","DOI":"10.5441\/002\/edbt.2019.84"},{"issue":"3","key":"7426_CR6","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/3323991","volume":"44","author":"P Damme","year":"2019","unstructured":"Damme, P., Ungeth\u00fcm, A., Hildebrandt, J., Habich, D., Lehner, W.: From a comprehensive experimental survey to a cost-based selection strategy for lightweight integer compression algorithms. ACM Trans. Database Syst. 44(3), 9\u20131946 (2019). https:\/\/doi.org\/10.1145\/3323991","journal-title":"ACM Trans. Database Syst."},{"issue":"1","key":"7426_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/spe.2203","volume":"45","author":"D Lemire","year":"2015","unstructured":"Lemire, D., Boytsov, L.: Decoding billions of integers per second through vectorization. Softw. Pract. Exp. 45(1), 1\u201329 (2015). https:\/\/doi.org\/10.1002\/spe.2203","journal-title":"Softw. Pract. Exp."},{"issue":"3","key":"7426_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/2735629","volume":"33","author":"WX Zhao","year":"2015","unstructured":"Zhao, W.X., Zhang, X., Lemire, D., Shan, D., Nie, J., Yan, H., Wen, J.: A general SIMD-based approach to accelerating compression algorithms. ACM Trans. Inf. Syst. 33(3), 15\u201311528 (2015). https:\/\/doi.org\/10.1145\/2735629","journal-title":"ACM Trans. Inf. Syst."},{"key":"7426_CR9","doi-asserted-by":"publisher","unstructured":"Hughes, C.J.: Single-instruction multiple-data execution. Synthesis Lectures on Computer Architecture. Morgan & Claypool Publishers (2015). https:\/\/doi.org\/10.2200\/S00647ED1V01Y201505CAC032","DOI":"10.2200\/S00647ED1V01Y201505CAC032"},{"key":"7426_CR10","doi-asserted-by":"publisher","unstructured":"Schlegel, B., Gemulla, R., Lehner, W.: Fast integer compression using SIMD instructions. In: Ailamaki, A., Boncz, P.A. (eds.) Proceedings of the Sixth International Workshop on Data Management on New Hardware, DaMoN 2010, Indianapolis, IN, June 7, 2010, pp. 34\u201340. ACM (2010). https:\/\/doi.org\/10.1145\/1869389.1869394","DOI":"10.1145\/1869389.1869394"},{"key":"7426_CR11","doi-asserted-by":"publisher","unstructured":"Hildebrandt, J., Habich, D., Lehner, W.: BOUNCE: memory-efficient SIMD approach for lightweight integer compression. In: 38th IEEE International Conference on Data Engineering Workshops, ICDE Workshops 2022, Kuala Lumpur, May 9, 2022, pp. 123\u2013128. IEEE (2022). https:\/\/doi.org\/10.1109\/ICDEW55742.2022.00025","DOI":"10.1109\/ICDEW55742.2022.00025"},{"key":"7426_CR12","doi-asserted-by":"publisher","unstructured":"Vogelsgesang, A., Haubenschild, M., Finis, J., Kemper, A., Leis, V., M\u00fchlbauer, T., Neumann, T., Then, M.: Get real: how benchmarks fail to represent the real world. In: B\u00f6hm, A., Rabl, T. (eds.) Proceedings of the 7th International Workshop on Testing Database Systems, DBTest@SIGMOD 2018, Houston, TX, June 15, 2018, pp. 1\u2013116. ACM (2018). https:\/\/doi.org\/10.1145\/3209950.3209952","DOI":"10.1145\/3209950.3209952"},{"key":"7426_CR13","doi-asserted-by":"publisher","unstructured":"Goldstein, J., Ramakrishnan, R., Shaft, U.: Compressing relations and indexes. In: Urban, S.D., Bertino, E. (eds.) Proceedings of the Fourteenth International Conference on Data Engineering, Orlando, FL, February 23\u201327, 1998, pp. 370\u2013379. IEEE Computer Society (1998). https:\/\/doi.org\/10.1109\/ICDE.1998.655800","DOI":"10.1109\/ICDE.1998.655800"},{"key":"7426_CR14","doi-asserted-by":"publisher","unstructured":"Zukowski, M., H\u00e9man, S., Nes, N., Boncz, P.A.: Super-scalar RAM-CPU cache compression. In: Liu, L., Reuter, A., Whang, K., Zhang, J. (eds.) Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3\u20138 April 2006, Atlanta, GA, p. 59. IEEE Computer Society (2006). https:\/\/doi.org\/10.1109\/ICDE.2006.150","DOI":"10.1109\/ICDE.2006.150"},{"issue":"3","key":"7426_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/163090.163096","volume":"22","author":"MA Roth","year":"1993","unstructured":"Roth, M.A., Horn, S.J.V.: Database compression. SIGMOD Rec. 22(3), 31\u201339 (1993). https:\/\/doi.org\/10.1145\/163090.163096","journal-title":"SIGMOD Rec."},{"key":"7426_CR16","doi-asserted-by":"publisher","unstructured":"Ungeth\u00fcm, A., Pietrzyk, J., Damme, P., Habich, D., Lehner, W.: Conflict detection-based run-length encoding\u2014AVX-512 CD instruction set in action. In: 34th IEEE International Conference on Data Engineering Workshops, ICDE Workshops 2018, Paris, April 16\u201320, 2018, pp. 96\u2013101. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/ICDEW.2018.00023","DOI":"10.1109\/ICDEW.2018.00023"},{"key":"7426_CR17","doi-asserted-by":"publisher","unstructured":"Li, Y., Patel, J.M.: Bitweaving: fast scans for main memory data processing. In: Ross, K.A., Srivastava, D., Papadias, D. (eds.) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, June 22\u201327, 2013, pp. 289\u2013300. ACM (2013). https:\/\/doi.org\/10.1145\/2463676.2465322","DOI":"10.1145\/2463676.2465322"},{"issue":"1","key":"7426_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.14778\/1687627.1687671","volume":"2","author":"T Willhalm","year":"2009","unstructured":"Willhalm, T., Popovici, N., Boshmaf, Y., Plattner, H., Zeier, A., Schaffner, J.: SIMD-scan: ultra fast in-memory table scan using on-chip vector processing units. Proc. VLDB Endow. 2(1), 385\u2013394 (2009). https:\/\/doi.org\/10.14778\/1687627.1687671","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"7426_CR19","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1023\/B:INRT.0000048490.99518.5c","volume":"8","author":"VN Anh","year":"2005","unstructured":"Anh, V.N., Moffat, A.: Inverted index compression using word-aligned binary codes. Inf. Retr. 8(1), 151\u2013166 (2005). https:\/\/doi.org\/10.1023\/B:INRT.0000048490.99518.5c","journal-title":"Inf. Retr."},{"issue":"2","key":"7426_CR20","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/spe.948","volume":"40","author":"VN Anh","year":"2010","unstructured":"Anh, V.N., Moffat, A.: Index compression using 64-bit words. Softw. Pract. Exp. 40(2), 131\u2013147 (2010). https:\/\/doi.org\/10.1002\/spe.948","journal-title":"Softw. Pract. Exp."},{"key":"7426_CR21","doi-asserted-by":"publisher","unstructured":"Stepanov, A.A., Gangolli, A.R., Rose, D.E., Ernst, R.J., Oberoi, P.S.: SIMD-based decoding of posting lists. In: Macdonald, C., Ounis, I., Ruthven, I. (eds.) Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, October 24\u201328, 2011, pp. 317\u2013326. ACM (2011). https:\/\/doi.org\/10.1145\/2063576.2063627","DOI":"10.1145\/2063576.2063627"},{"key":"7426_CR22","doi-asserted-by":"publisher","unstructured":"Habich, D., Pietrzyk, J., Krause, A., Hildebrandt, J., Lehner, W.: To use or not to use the SIMD gather instruction? In: Blanas, S., May, N. (eds.) International Conference on Management of Data, DaMoN 2022, Philadelphia, PA, 13 June 2022, pp. 9\u2013195. ACM (2022). https:\/\/doi.org\/10.1145\/3533737.3535089","DOI":"10.1145\/3533737.3535089"},{"key":"7426_CR23","doi-asserted-by":"publisher","unstructured":"Monil, M.A.H., Lee, S., Vetter, J.S., Malony, A.D.: Understanding the impact of memory access patterns in intel processors. In: IEEE\/ACM Workshop on Memory Centric High Performance Computing, MCHPC@SC 2020, Atlanta, GA, November 11, 2020, pp. 52\u201361. IEEE (2020). https:\/\/doi.org\/10.1109\/MCHPC51950.2020.00012","DOI":"10.1109\/MCHPC51950.2020.00012"},{"key":"7426_CR24","doi-asserted-by":"publisher","unstructured":"Xin, X., Guo, Y., Zhang, Y., Yang, J.: SAM: accelerating strided memory accesses. In: MICRO \u201921: 54th Annual IEEE\/ACM International Symposium on Microarchitecture, Virtual Event, Greece, October 18\u201322, 2021, pp. 324\u2013336. ACM (2021). https:\/\/doi.org\/10.1145\/3466752.3480091","DOI":"10.1145\/3466752.3480091"},{"key":"7426_CR25","doi-asserted-by":"publisher","unstructured":"Damme, P., Habich, D., Hildebrandt, J., Lehner, W.: Lightweight data compression algorithms: an experimental survey (experiments and analyses). In: Markl, V., Orlando, S., Mitschang, B., Andritsos, P., Sattler, K., Bre\u00df, S. (eds.) Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, March 21\u201324, 2017, pp. 72\u201383. OpenProceedings.org (2017). https:\/\/doi.org\/10.5441\/002\/edbt.2017.08","DOI":"10.5441\/002\/edbt.2017.08"},{"key":"7426_CR26","doi-asserted-by":"publisher","unstructured":"Hildebrandt, J., Habich, D., Damme, P., Lehner, W.: Model kit for lightweight data compression algorithms. In: Pitoura, E., Maabout, S., Koutrika, G., Marian, A., Tanca, L., Manolescu, I., Stefanidis, K. (eds.) Proceedings of the 19th International Conference on Extending Database Technology, EDBT, Bordeaux, France, March 15\u201316, 2016, pp. 692\u2013693. OpenProceedings.org (2016). https:\/\/doi.org\/10.5441\/002\/edbt.2016.90","DOI":"10.5441\/002\/edbt.2016.90"},{"key":"7426_CR27","doi-asserted-by":"publisher","unstructured":"Pietrzyk, J., Habich, D., Lehner, W.: To share or not to share vector registers? In: Porobic, D., Neumann, T. (eds.) 16th International Workshop on Data Management on New Hardware, DaMoN 2020, Portland, Oregon, June 15, 2020, pp. 12\u201311210. ACM (2020). https:\/\/doi.org\/10.1145\/3399666.3399923","DOI":"10.1145\/3399666.3399923"}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-023-07426-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10619-023-07426-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-023-07426-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T10:53:43Z","timestamp":1694688823000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10619-023-07426-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,10]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["7426"],"URL":"https:\/\/doi.org\/10.1007\/s10619-023-07426-0","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2223225\/v1","asserted-by":"object"}]},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"value":"0926-8782","type":"print"},{"value":"1573-7578","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,10]]},"assertion":[{"value":"20 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}