{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T07:50:41Z","timestamp":1721980241392},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Once exotic, computational accelerators are now commonly available in many computing systems. Graphics processing units (GPUs) are perhaps the most frequently encountered computational accelerators. Recent work has shown that GPUs are beneficial when analyzing massive data sets. Specifically related to this study, it has been demonstrated that GPUs can significantly reduce the query processing time of database bitmap index queries. Bitmap indices are typically used for large, read-only data sets and are often compressed using some form of hybrid run-length compression. In this paper, we present three GPU algorithm enhancement strategies for executing queries of bitmap indices compressed using word aligned hybrid compression: (1) data structure reuse (2) metadata creation with various type alignment and (3) a preallocated memory pool. The data structure reuse greatly reduces the number of costly memory system calls. The use of metadata exploits the immutable nature of bitmaps to pre-calculate and store necessary intermediate processing results. This metadata reduces the number of required query-time processing steps. Preallocating a memory pool can reduce or entirely remove the overhead of memory operations during query processing. Our empirical study showed that performing a combination of these strategies can achieve 32.4<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u00d7<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to 98.7<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\times$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u00d7<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> speedup over the current state-of-the-art implementation. Our study also showed that by using our enhancements, a common gaming GPU can achieve a <jats:inline-formula><jats:alternatives><jats:tex-math>$$15.0\\times$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>15.0<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> speedup over a more expensive high-end CPU.<\/jats:p>","DOI":"10.1007\/s41019-020-00148-8","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T06:02:59Z","timestamp":1606716179000},"page":"209-228","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Exploring Means to Enhance the Efficiency of GPU Bitmap Index Query Processing"],"prefix":"10.1007","volume":"6","author":[{"given":"Brandon","family":"Tran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brennan","family":"Schaffner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph M.","family":"Myre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason","family":"Sawin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Chiu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,30]]},"reference":[{"key":"148_CR1","doi-asserted-by":"crossref","unstructured":"Andrzejewski W, Wrembel R (2010) GPU-WAH: applying GPUs to compressing bitmap indexes with word aligned hybrid. In: International conference on database and expert systems applications. Springer, Berlin, pp 315\u2013329","DOI":"10.1007\/978-3-642-15251-1_26"},{"key":"148_CR2","first-page":"627","volume":"40","author":"W Andrzejewski","year":"2011","unstructured":"Andrzejewski W, Wrembel R (2011) GPU-PLWAH: GPU-based implementation of the PLWAH algorithm for compressing bitmaps. Control Cybern 40:627\u2013650","journal-title":"Control Cybern"},{"key":"148_CR3","unstructured":"Antoshenkov G (1995) Byte-aligned bitmap compression. In: Proceedings DCC\u201995 data compression conference, p 476. IEEE"},{"key":"148_CR4","doi-asserted-by":"crossref","unstructured":"Bakkum P, Skadron K (2010) Accelerating sql database operations on a gpu with cuda. In: Proceedings of the 3rd workshop on general-purpose computation on graphics processing units, pp 94\u2013103","DOI":"10.1145\/1735688.1735706"},{"key":"148_CR5","unstructured":"Bonneville power administration, http:\/\/www.bpa.gov"},{"key":"148_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jretai.2016.12.004","volume":"93","author":"E Bradlow","year":"2017","unstructured":"Bradlow E, Gangwar M, Kopalle P, Voleti S (2017) The role of big data and predictive analytics in retailing. J Retail 93:79\u201395","journal-title":"J Retail"},{"issue":"5","key":"148_CR7","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1002\/spe.2325","volume":"46","author":"S Chambi","year":"2016","unstructured":"Chambi S, Lemire D, Kaser O, Godin R (2016) Better bitmap performance with roaring bitmaps. Softw Pract Exp 46(5):709\u2013719","journal-title":"Softw Pract Exp"},{"key":"148_CR8","doi-asserted-by":"crossref","unstructured":"Chang J, Chen Z, Zheng W, Cao J, Wen Y, Peng G, Huang W (2015) Splwah: a bitmap index compression scheme for searching in archival internet traffic. In: IEEE international conference on communications (ICC), pp 7089\u20137094","DOI":"10.1109\/ICC.2015.7249457"},{"key":"148_CR9","doi-asserted-by":"crossref","unstructured":"Chang J, Chen Z, Zheng W, Wen Y, Cao J, Huang W (2014) Plwah+: a bitmap index compressing scheme based on plwah. In: ACM\/IEEE symposium on architectures for networking and communications systems (ANCS), pp 257\u2013258","DOI":"10.1145\/2658260.2661777"},{"issue":"1","key":"148_CR10","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TST.2015.7040519","volume":"20","author":"Z Chen","year":"2015","unstructured":"Chen Z, Wen Y, Cao J, Zheng W, Chang J, Wu Y, Ma G, Hakmaoui M, Peng G (2015) A survey of bitmap index compression algorithms for big data. Tsinghua Sci Technol 20(1):100\u2013115","journal-title":"Tsinghua Sci Technol"},{"issue":"16","key":"148_CR11","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/j.ipl.2010.05.018","volume":"110","author":"A Colantonio","year":"2010","unstructured":"Colantonio A, Di Pietro R (2010) Concise: compressed \u2019n\u2019 composable integer set. Inf Process Lett 110(16):644\u2013650","journal-title":"Inf Process Lett"},{"key":"148_CR12","doi-asserted-by":"crossref","unstructured":"Corrales F, Chiu D, Sawin J (2011) Variable length compression for bitmap indices. In: Database and expert systems applications, pp 381\u2013395","DOI":"10.1007\/978-3-642-23091-2_32"},{"key":"148_CR13","unstructured":"CUDA, C.: Best practice guide (2019). https:\/\/docs.nvidia.com\/cuda\/cuda-c-best-practices-guide"},{"key":"148_CR14","unstructured":"Davenport T, Dyche J (2013) Big data in big companies. Tech. rep, International Institute for Analytics"},{"key":"148_CR15","doi-asserted-by":"crossref","unstructured":"Deli\u00e8ge F, Pedersen TB (2010) Position list word aligned hybrid: optimizing space and performance for compressed bitmaps. In: International conference on extending database technology, EDBT \u201910, pp 228\u2013239","DOI":"10.1145\/1739041.1739071"},{"key":"148_CR16","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1016\/j.jbusres.2015.07.001","volume":"69","author":"S Erevelles","year":"2016","unstructured":"Erevelles S, Fukawa N, Swaynea L (2016) Big data consumer analytics and the transformation of marketing. J Bus Res 69:897\u2013904","journal-title":"J Bus Res"},{"issue":"2","key":"148_CR17","first-page":"1382","volume":"3","author":"F Fusco","year":"2010","unstructured":"Fusco F, Stoecklin MP, Vlachos M (2010) Net-fli: on-the-fly compression, archiving and indexing of streaming network traffic. VLDB 3(2):1382\u20131393","journal-title":"VLDB"},{"key":"148_CR18","doi-asserted-by":"crossref","unstructured":"Fusco F, Vlachos M, Dimitropoulos X, Deri L (2013) Indexing million of packets per second using gpus. In: Proceedings of the 2013 conference on internet measurement conference, IMC \u201913, pp 327\u2013332","DOI":"10.1145\/2504730.2504756"},{"key":"148_CR19","doi-asserted-by":"crossref","unstructured":"Gelado I, Garland M (2019) Throughput-oriented gpu memory allocation. In: Proceedings of the 24th symposium on principles and practice of parallel programming, pp 27\u201337","DOI":"10.1145\/3293883.3295727"},{"key":"148_CR20","doi-asserted-by":"crossref","unstructured":"Gosink LJ, Wu K, Bethel EW, Owens JD, Joy KI (2009) Data parallel bin-based indexing for answering queries on multi-core architectures. In: Winslett M (ed) Scientific and statistical database management, pp 110\u2013129","DOI":"10.1007\/978-3-642-02279-1_9"},{"key":"148_CR21","doi-asserted-by":"crossref","unstructured":"Govindaraju NK, Lloyd B, Wang W, Lin M, Manocha D (2004) Fast computation of database operations using graphics processors. In: Proceedings of the 2004 ACM SIGMOD international conference on management of data, pp 215\u2013226","DOI":"10.1145\/1007568.1007594"},{"key":"148_CR22","doi-asserted-by":"crossref","unstructured":"Guzun G, Canahuate G, Chiu D, Sawin J (2014) A tunable compression framework for bitmap indices. In: 2014 IEEE 30th international conference on data engineering, pp 484\u2013495. IEEE","DOI":"10.1109\/ICDE.2014.6816675"},{"key":"148_CR23","doi-asserted-by":"crossref","unstructured":"He B, Yang K, Fang R, Lu M, Govindaraju N, Luo Q, Sander P (2008) Relational joins on graphics processors. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data, pp 511\u2013524","DOI":"10.1145\/1376616.1376670"},{"issue":"4","key":"148_CR24","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1109\/TVCG.2010.88","volume":"17","author":"Q Hou","year":"2011","unstructured":"Hou Q, Sun X, Zhou K, Lauterbach C, Manocha D (2011) Memory-scalable GPU spatial hierarchy construction. IEEE Trans Visual Comput Graphics 17(4):466\u2013474","journal-title":"IEEE Trans Visual Comput Graphics"},{"key":"148_CR25","doi-asserted-by":"crossref","unstructured":"Huang X, Rodrigues CI, Jones S, Buck I, Hwu Wm (2010) Xmalloc: a scalable lock-free dynamic memory allocator for many-core machines. In: 2010 10th IEEE international conference on computer and information technology, pp 1134\u20131139. IEEE","DOI":"10.1109\/CIT.2010.206"},{"key":"148_CR26","doi-asserted-by":"crossref","unstructured":"Kim C, Chhugani J, Satish N, Sedlar E, Nguyen AD, Kaldewey T, Lee VW, Brandt SA, Dubey P (2010) Fast: fast architecture sensitive tree search on modern cpus and gpus. In: Proceedings of the 2010 ACM SIGMOD international conference on management of data, pp 339\u2013350","DOI":"10.1145\/1807167.1807206"},{"issue":"8","key":"148_CR27","doi-asserted-by":"publisher","first-page":"1195","DOI":"10.1016\/j.jpdc.2013.03.015","volume":"73","author":"J Kim","year":"2013","unstructured":"Kim J, Kim SG, Nam B (2013) Parallel multi-dimensional range query processing with r-trees on gpu. J Parallel Distrib Comput 73(8):1195\u20131207","journal-title":"J Parallel Distrib Comput"},{"key":"148_CR28","unstructured":"Lichman M (2013) UCI machine learning repository. http:\/\/archive.ics.uci.edu\/ml"},{"issue":"2","key":"148_CR29","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S (1982) Least squares quantization in pcm. IEEE Trans Inf Theory 28(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"key":"148_CR30","unstructured":"Marr B (2018) Starbucks: using big data, analytics and artificial intelligence to boost performance. Forbes. https:\/\/www.forbes.com\/sites\/bernardmarr\/2018\/05\/28\/starbucks-using-big-data-analytics-and-artificial-intelligence-to-boost-performance\/#5784902e65cd"},{"key":"148_CR31","doi-asserted-by":"crossref","unstructured":"McAfee A, Brynjolfsson E (2012) Big data: the management revolution. Harvard Business Review, pp 61\u201368","DOI":"10.1111\/npqu.11362"},{"key":"148_CR32","unstructured":"Merrill D (2016) Cub: Cuda unbound. http:\/\/nvlabs.github.io\/cub"},{"key":"148_CR33","doi-asserted-by":"crossref","unstructured":"Nelson M, Sorenson Z, Myre JM, Sawin J, Chiu D (2019) GPU acceleration of range queries over large data sets. In: Proceedings of the 6th IEEE\/ACM international conference on big data computing, application, and technologies (BDCAT\u201919), pp 11\u201320","DOI":"10.1145\/3365109.3368789"},{"issue":"1","key":"148_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13677-020-00191-w","volume":"9","author":"M Nelson","year":"2020","unstructured":"Nelson M, Sorenson Z, Myre JM, Sawin J, Chiu D (2020) Parallel acceleration of CPU and GPU range queries over large data sets. J Cloud Comput 9(1):1\u201321","journal-title":"J Cloud Comput"},{"key":"148_CR35","unstructured":"Nvidia C (2020) Programming guide"},{"key":"148_CR36","doi-asserted-by":"crossref","unstructured":"Rui R, Tu YC (2017) Fast equi-join algorithms on GPUs: design and implementation. In: Proceedings of the 29th international conference on scientific and statistical database management, pp 1\u201312","DOI":"10.1145\/3085504.3085521"},{"issue":"4","key":"148_CR37","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.jbi.2011.02.008","volume":"44","author":"M Sariyar","year":"2011","unstructured":"Sariyar M, Borg A, Pommerening K (2011) Controlling false match rates in record linkage using extreme value theory. J Biomed Inform 44(4):648\u2013654","journal-title":"J Biomed Inform"},{"key":"148_CR38","doi-asserted-by":"crossref","unstructured":"Steinberger M, Kenzel M, Kainz B, Schmalstieg D (2012) Scatteralloc: massively parallel dynamic memory allocation for the GPU. In: 2012 Innovative parallel computing (InPar), pp 1\u201310. IEEE","DOI":"10.1109\/InPar.2012.6339604"},{"key":"148_CR39","doi-asserted-by":"crossref","unstructured":"Taufen B, Sawin J, Chiu D (2017) Improving the querying efficiency of the plwah bitmap algorithm. In: Proceedings of the 21st international database engineering and applications symposium, pp 127\u2013134","DOI":"10.1145\/3105831.3105868"},{"key":"148_CR40","doi-asserted-by":"crossref","unstructured":"Tran B, Schaffner B, Sawin J, Myre JM, Chiu D (2020) Increasing the efficiency of GPU bitmap index query processing. In: To appear in Proceedings of the 25th international conference on database systems for advanced applications (DASFAA\u201920)","DOI":"10.1007\/978-3-030-59419-0_21"},{"key":"148_CR41","doi-asserted-by":"crossref","unstructured":"Velez M, Sawin J, Ingerson A, Chiu D (2016) Improving bitmap execution performance using column-based metadata. In: 2016 IEEE 4th international conference on future internet of things and cloud (FiCloud), pp 371\u2013378. IEEE","DOI":"10.1109\/FiCloud.2016.59"},{"key":"148_CR42","doi-asserted-by":"crossref","unstructured":"Wang L, Ye J, Zhao Y, Wu W, Li A, Song SL, Xu Z, Kraska T (2018) Superneurons: dynamic GPU memory management for training deep neural networks. In: Proceedings of the 23rd ACM SIGPLAN symposium on principles and practice of parallel programming, pp 41\u201353","DOI":"10.1145\/3178487.3178491"},{"key":"148_CR43","doi-asserted-by":"crossref","unstructured":"Wen Y, Wang H, Chen Z, Cao J, Peng G, Huang W, Hu Z, Zhou J, Guo J (2016) Masc: a bitmap index encoding algorithm for fast data retrieval. In: IEEE international conference on communications (ICC), pp 1\u20136","DOI":"10.1109\/ICC.2016.7510827"},{"key":"148_CR44","doi-asserted-by":"crossref","unstructured":"Wu J, Di B, Sun J, Chen H, Zhong X, Hu D, Huang C (2019) A fast and secure GPU memory allocator. In: 2019 IEEE 21st international conference on high performance computing and communications; IEEE 17th international conference on smart city; IEEE 5th international conference on data science and systems (HPCC\/SmartCity\/DSS), pp 146\u2013153. IEEE","DOI":"10.1109\/HPCC\/SmartCity\/DSS.2019.00035"},{"key":"148_CR45","unstructured":"Wu K, Otoo EJ, Shoshani A (2002) Compressing bitmap indexes for faster search operations. In: Proceedings 14th international conference on scientific and statistical database management, pp 99\u2013108. IEEE"},{"issue":"1","key":"148_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1132863.1132864","volume":"31","author":"K Wu","year":"2006","unstructured":"Wu K, Otoo EJ, Shoshani A (2006) Optimizing bitmap indices with efficient compression. ACM Trans Database Syst 31(1):1\u201338","journal-title":"ACM Trans Database Syst"},{"key":"148_CR47","unstructured":"Wu K, Otoo EJ, Shoshani A, Nordberg H (2001) Notes on design and implementation of compressed bit vectors. Tech. Rep. LBNL\/PUB-3161, Lawrence Berkeley National Laboratory"},{"key":"148_CR48","doi-asserted-by":"crossref","unstructured":"You S, Zhang J, Gruenwald L (2013) Parallel spatial query processing on GPUs using r-trees. In: Proceedings of the 2Nd ACM SIGSPATIAL international workshop on analytics for big geospatial data, pp 23\u201331","DOI":"10.1145\/2534921.2534949"},{"key":"148_CR49","first-page":"39","volume":"2","author":"M Zaker","year":"2008","unstructured":"Zaker M, Phon-Amnuaisuk S, Haw SC (2008) An adequate design for large data warehouse systems: bitmap index versus b-tree index. Int J Comput Commun 2:39\u201346","journal-title":"Int J Comput Commun"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-020-00148-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-020-00148-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-020-00148-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T11:09:17Z","timestamp":1621681757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-020-00148-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,30]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["148"],"URL":"https:\/\/doi.org\/10.1007\/s41019-020-00148-8","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,30]]},"assertion":[{"value":"9 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}