{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T01:11:02Z","timestamp":1788570662535,"version":"build-2803163510"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Hong Kong Research Grants Council","award":["152043\/23E"],"award-info":[{"award-number":["152043\/23E"]}]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["62422206,62472289"],"award-info":[{"award-number":["62422206,62472289"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shenzhen Natural Sponsored by Science Foundation","award":["20220810142731001"],"award-info":[{"award-number":["20220810142731001"]}]},{"name":"The Pearl River Talent Recruitment Program","award":["2019ZT08X603"],"award-info":[{"award-number":["2019ZT08X603"]}]},{"DOI":"10.13039\/501100015947","name":"Guangdong Province Key Laboratory of Popular High Performance Computers","doi-asserted-by":"crossref","award":["2017B030314073"],"award-info":[{"award-number":["2017B030314073"]}],"id":[{"id":"10.13039\/501100015947","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Hash tables are widely used to support fast lookup operations for various applications on key-value stores and relational databases. In recent years, hash tables have been significantly improved by utilizing the high memory bandwidth and large parallelism degree offered by Graphics Processing Units (GPUs). However, there is still a lack of comprehensive analysis of the lookup performance on existing GPU-based hash tables. In this work, we develop a micro-benchmark and devise an effective and general performance analysis model, which enables uniform and accurate lookup performance evaluation of GPU-based hash tables. Moreover, we propose GPH, a novel GPU-based hash table, to improve lookup performance with the guidance of the benchmark results from the analysis model devised above. In particular, GPH employs the perfect hashing scheme that ensures exactly 1 bucket probe for every lookup operation. Besides, we optimize the bucket requests to global memory in GPH by devising vectorization and instruction-level parallelism techniques. We also introduce the insert kernel in GPH to support dynamic updates (e.g., processing insert operations) on GPU. Experimentally, GPH achieves over 8500 million operations per second (MOPS) for lookup operation processing in both synthetic and real-world workloads, which outperforms all evaluated GPU-based hash tables.<\/jats:p>","DOI":"10.1145\/3725406","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:22:29Z","timestamp":1750281749000},"page":"1-26","source":"Crossref","is-referenced-by-count":4,"title":["GPH: An Efficient and Effective Perfect Hashing Scheme for GPU Architectures"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8967-5941","authenticated-orcid":false,"given":"Jiaping","family":"Cao","sequence":"first","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1073-5655","authenticated-orcid":false,"given":"Le","family":"Xu","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9619-4924","authenticated-orcid":false,"given":"Man Lung","family":"Yiu","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4298-3215","authenticated-orcid":false,"given":"Jianbin","family":"Qin","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8424-0092","authenticated-orcid":false,"given":"Bo","family":"Tang","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, Guangdong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2011. TPC-H DBGEN. https:\/\/github.com\/electrum\/tpch-dbgen"},{"key":"e_1_2_2_2_1","unstructured":"2013. CUDA pro tip: Increase performance with vectorized memory access. https:\/\/developer.nvidia.com\/blog\/cudapro-tip-increase-performance-with-vectorized-memory-access\/"},{"key":"e_1_2_2_3_1","unstructured":"2015. Achieved Occupancy. https:\/\/docs.nvidia.com\/gameworks\/content\/developertools\/desktop\/analysis\/report\/ cudaexperiments\/kernellevel\/achievedoccupancy.htm."},{"key":"e_1_2_2_4_1","unstructured":"2019. May 2015 Reddit Comments. https:\/\/www.kaggle.com\/datasets\/kaggle\/reddit-comments-may-2015."},{"key":"e_1_2_2_5_1","unstructured":"2024. CUDA C Programming Guide Performance Guidelines. https:\/\/docs.nvidia.com\/cuda\/cuda-c-programmingguide\/."},{"key":"e_1_2_2_6_1","unstructured":"2024. CUDA Data Parallel Primitives library. https:\/\/github.com\/cudpp\/cudpp\/blob\/master\/apps\/cudpp_hash_testrig\/ random_numbers.cpp"},{"key":"e_1_2_2_7_1","unstructured":"2024. Kernel Profiling Guide: Sections and Rules. https:\/\/docs.nvidia.com\/nsight-compute\/ProfilingGuide\/index.html# id12."},{"key":"e_1_2_2_8_1","unstructured":"2024. Kernel Profiling Guide: Source Metrics. https:\/\/docs.nvidia.com\/nsight-compute\/ProfilingGuide\/index.html#id34."},{"key":"e_1_2_2_9_1","unstructured":"2024. NSIGHT COMPUTE. https:\/\/docs.nvidia.com\/nsight-compute\/NsightCompute\/index.html."},{"key":"e_1_2_2_10_1","unstructured":"2024. REDIS. https:\/\/redis.io\/."},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Dan A Alcantara Andrei Sharf Fatemeh Abbasinejad Shubhabrata Sengupta Michael Mitzenmacher John D Owens and Nina Amenta. 2009. Real-time parallel hashing on the GPU. In ACM SIGGRAPH Asia. 1--9.","DOI":"10.1145\/1661412.1618500"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Dan A Alcantara Vasily Volkov Shubhabrata Sengupta Michael Mitzenmacher John D Owens and Nina Amenta. 2012. Building an efficient hash table on the GPU. In GPU Computing Gems Jade Edition. 39--53.","DOI":"10.1016\/B978-0-12-385963-1.00004-6"},{"key":"e_1_2_2_13_1","unstructured":"Austin Appleby. 2024. MURMURHASH3. https:\/\/github.com\/aappleby\/smhasher\/blob\/master\/src\/MurmurHash3.cpp."},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Saman Ashkiani Martin Farach-Colton and John D Owens. 2018. A dynamic hash table for the GPU. In IPDPS. 419--429.","DOI":"10.1109\/IPDPS.2018.00052"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Berk Atikoglu Yuehai Xu Eitan Frachtenberg Song Jiang and Mike Paleczny. 2012. Workload analysis of a large-scale key-value store. In SIGMETRICS. 53--64.","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Muhammad A Awad Saman Ashkiani Serban D Porumbescu Mart\u00edn Farach-Colton and John D Owens. 2023. Analyzing and implementing GPU hash tables. In APOCS. 33--50.","DOI":"10.1137\/1.9781611977578.ch3"},{"key":"e_1_2_2_17_1","first-page":"85","article-title":"Multi-core, main-memory joins: sort vs. hash revisited","volume":"7","author":"Balkesen Cagri","year":"2013","unstructured":"Cagri Balkesen, Gustavo Alonso, Jens Teubner, and M. Tamer \u00d6zsu. 2013. Multi-core, main-memory joins: sort vs. hash revisited. PVLDB 7, 1 (2013), 85--96.","journal-title":"PVLDB"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Djamal Belazzougui Fabiano C Botelho and Martin Dietzfelbinger. 2009. Hash displace and compress. In ESA. 682--693.","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Daniel J Benjamin James O Berger Magnus Johannesson Brian A Nosek E-J Wagenmakers Richard Berk Kenneth A Bollen Bj\u00f6rn Brembs Lawrence Brown Colin Camerer et al. 2018. Redefine statistical significance. Nature human behaviour 2 1 (2018) 6--10.","DOI":"10.1038\/s41562-017-0189-z"},{"key":"e_1_2_2_20_1","unstructured":"Rajesh Bordawekar. 2014. Evaluation of parallel hashing techniques. In Nvidia GTC."},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Fabiano C Botelho Rasmus Pagh and Nivio Ziviani. 2007. Simple and space-efficient minimal perfect hash functions. In WADS. 139--150.","DOI":"10.1007\/978-3-540-73951-7_13"},{"key":"e_1_2_2_22_1","volume-title":"Dong Ping Zhang","author":"Breslow Alex D","year":"2016","unstructured":"Alex D Breslow, Dong Ping Zhang, Joseph L Greathouse, Nuwan Jayasena, and Dean M Tullsen. 2016. Horton Tables: Fast Hash Tables for In-Memory Data-Intensive Computing. In USENIX ATC. 281--294."},{"key":"e_1_2_2_23_1","volume-title":"Yee Jiun Song, and Venkat Venkataramani","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. 2013. TAO: Facebook's distributed data store for the social graph. In USENIX ATC. 49--60."},{"key":"e_1_2_2_24_1","volume-title":"EEPH: An Efficient Extendible Perfect Hashing for Hybrid PMem-DRAM. In ICDE. 1366--1378.","author":"Chen Qi","year":"2023","unstructured":"Qi Chen, Hao Hu, Cai Deng, Dingbang Liu, Shiyi Li, Bo Tang, Ting Yao, and Wen Xia. 2023. EEPH: An Efficient Extendible Perfect Hashing for Hybrid PMem-DRAM. In ICDE. 1366--1378."},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"S. Chen A. Ailamaki P.B. Gibbons and T.C. Mowry. 2004. Improving hash join performance through prefetching. In ICDE. 116--127.","DOI":"10.1109\/ICDE.2004.1319989"},{"key":"e_1_2_2_26_1","first-page":"1965","article-title":"Taobench: An end-to-end benchmark for social network workloads","volume":"15","author":"Cheng Audrey","year":"2022","unstructured":"Audrey Cheng, Xiao Shi, Aaron Kabcenell, Shilpa Lawande, Hamza Qadeer, Jason Chan, Harrison Tin, Ryan Zhao, Peter Bailis, Mahesh Balakrishnan, et al. 2022. Taobench: An end-to-end benchmark for social network workloads. PVLDB 15, 9 (2022), 1965--1977.","journal-title":"PVLDB"},{"key":"e_1_2_2_27_1","volume-title":"An optimal algorithm for generating minimal perfect hash functions. Information processing letters 43, 5","author":"Czech Zbigniew J","year":"1992","unstructured":"Zbigniew J Czech, George Havas, and Bohdan S Majewski. 1992. An optimal algorithm for generating minimal perfect hash functions. Information processing letters 43, 5 (1992), 257--264."},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Yangshen Deng Shiwen Chen Zhaoyang Hong and Bo Tang. 2024. How Does Software Prefetching Work on GPU Query Processing?. In DaMoN. Article 5 9 pages.","DOI":"10.1145\/3662010.3663445"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"e_1_2_2_30_1","unstructured":"Bin Fan David G Andersen and Michael Kaminsky. 2013. MemC3: Compact and concurrent MemCache with dumber caching and smarter hashing. In NSDI. 371--384."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1012889.1012894"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460872"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Tobias Groth Sven Groppe Thilo Pionteck Franz Valdiek and Martin Koppehel. 2022. Accelerated parallel hybrid GPU\/CPU hash table queries with string keys. In DEXA. 191--203.","DOI":"10.1007\/978-3-031-12426-6_15"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Bingsheng He Ke Yang Rui Fang Mian Lu Naga Govindaraju Qiong Luo and Pedro Sander. 2008. Relational joins on graphics processors. In SIGMOD. 511--524.","DOI":"10.1145\/1376616.1376670"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3625054.3625063"},{"key":"e_1_2_2_37_1","first-page":"1","article-title":"PHOBIC: Perfect Hashing With Optimized Bucket Sizes and Interleaved Coding","volume":"308","author":"Hermann Stefan","year":"2024","unstructured":"Stefan Hermann, Hans-Peter Lehmann, Giulio Ermanno Pibiri, Peter Sanders, and Stefan Walzer. 2024. PHOBIC: Perfect Hashing With Optimized Bucket Sizes and Interleaved Coding. In ESA, Vol. 308. 69:1--69:17.","journal-title":"ESA"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Sunpyo Hong and Hyesoon Kim. 2009. An analytical model for a GPU architecture with memory-level and thread-level parallelism awareness. In ISCA. 152--163.","DOI":"10.1145\/1555754.1555775"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Daniel J\u00fcnger Christian Hundt and Bertil Schmidt. 2018. WarpDrive: Massively parallel hashing on multi-GPU nodes. In IPDPS. 441--450.","DOI":"10.1109\/IPDPS.2018.00054"},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Daniel J\u00fcnger Robin Kobus Andr\u00e9 M\u00fcller Christian Hundt Kai Xu Weiguo Liu and Bertil Schmidt. 2020. WarpCore: A Library for fast Hash Tables on GPUs. In HiPC. 11--20.","DOI":"10.1109\/HiPC50609.2020.00015"},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Tim Kaldewey Guy Lohman Rene Mueller and Peter Volk. 2012. GPU Join Processing Revisited. In DaMoN. 55--62.","DOI":"10.1145\/2236584.2236592"},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Farzad Khorasani Mehmet E Belviranli Rajiv Gupta and Laxmi N Bhuyan. 2015. Stadium hashing: Scalable and flexible hashing on gpus. In PACT. 63--74.","DOI":"10.1109\/PACT.2015.13"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141926"},{"key":"e_1_2_2_44_1","first-page":"237","article-title":"Data-parallel hashing techniques for GPU architectures","volume":"31","author":"Lessley Brenton","year":"2019","unstructured":"Brenton Lessley and Hank Childs. 2019. Data-parallel hashing techniques for GPU architectures. TPDS 31, 1 (2019), 237--250.","journal-title":"TPDS"},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Xiaozhou Li David G Andersen Michael Kaminsky and Michael J Freedman. 2014. Algorithmic improvements for fast concurrent cuckoo hashing. In EuroSys. 1--14.","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Yuchen Li Qiwei Zhu Zheng Lyu Zhongdong Huang and Jianling Sun. 2021. DyCuckoo: dynamic hash tables on gpus. In ICDE. 744--755.","DOI":"10.1109\/ICDE51399.2021.00070"},{"key":"e_1_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Prabhakar Misra and Mainak Chaudhuri. 2012. Performance evaluation of concurrent lock-free data structures on GPUs. In ICPDS. 53--60.","DOI":"10.1109\/ICPADS.2012.18"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3134214"},{"key":"e_1_2_2_49_1","volume-title":"Introduction to the practice of statistics","author":"Moore David S","unstructured":"David S Moore and George P McCabe. 1989. Introduction to the practice of statistics. WH Freeman\/Times Books\/Henry Holt & Co."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_2_51_1","doi-asserted-by":"crossref","unstructured":"Anil Shanbhag Samuel Madden and Xiangyao Yu. 2020. A study of the fundamental performance characteristics of GPUs and CPUs for database analytics. In SIGMOD. 1617--1632.","DOI":"10.1145\/3318464.3380595"},{"key":"e_1_2_2_52_1","volume-title":"Operating System Concepts","author":"Silberschatz Abraham","unstructured":"Abraham Silberschatz, Greg Gagne, and Peter Baer Galbin. 2008. Operating System Concepts (8th ed.). Wiley. 741--742 pages.","edition":"8"},{"key":"e_1_2_2_53_1","first-page":"16","article-title":"Better performance at lower occupancy","volume":"10","author":"Volkov Vasily","year":"2010","unstructured":"Vasily Volkov. 2010. Better performance at lower occupancy. In Nvidia GTC, Vol. 10. 16.","journal-title":"Nvidia GTC"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467240"},{"key":"e_1_2_2_55_1","first-page":"1226","article-title":"Mega-KV: A case for gpus to maximize the throughput of in-memory key-value stores","volume":"8","author":"Zhang Kai","year":"2015","unstructured":"Kai Zhang, Kaibo Wang, Yuan Yuan, Lei Guo, Rubao Lee, and Xiaodong Zhang. 2015. Mega-KV: A case for gpus to maximize the throughput of in-memory key-value stores. PVLDB 8, 11 (2015), 1226--1237.","journal-title":"PVLDB"},{"key":"e_1_2_2_56_1","volume-title":"Prasanna","author":"Zhou Shijie","year":"2015","unstructured":"Shijie Zhou and Viktor K. Prasanna. 2015. Scalable GPU-Accelerated IPv6 Lookup Using Hierarchical Perfect Hashing. In GLOBECOM. 1--6."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:59:46Z","timestamp":1774983586000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725406"],"URL":"https:\/\/doi.org\/10.1145\/3725406","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}