{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:01:37Z","timestamp":1767927697360,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T00:00:00Z","timestamp":1623888000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T00:00:00Z","timestamp":1623888000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"the National Key R&D Program of China","award":["2018YFB1003400"],"award-info":[{"award-number":["2018YFB1003400"]}]},{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U1811261"],"award-info":[{"award-number":["U1811261"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61872070"],"award-info":[{"award-number":["61872070"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Fundamental Research Funds for the Central Universities","award":["N180716010"],"award-info":[{"award-number":["N180716010"]}]},{"DOI":"10.13039\/501100018617","name":"Liao Ning Revitalization Talents Program","doi-asserted-by":"crossref","award":["XLYC1807158"],"award-info":[{"award-number":["XLYC1807158"]}],"id":[{"id":"10.13039\/501100018617","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Hyperspace hashing which is often applied to NoSQL data-bases builds indexes by mapping objects with multiple attributes to a multidimensional space. It can accelerate processing queries of some secondary attributes in addition to just primary keys. In recent years, the rich computing resources of GPU provide opportunities for implementing high-performance HyperSpace Hash. In this study, we construct a fully concurrent dynamic hyperspace hash table for GPU. By using atomic operations instead of locking, we make our approach highly parallel and lock-free. We propose a special concurrency control strategy that ensures wait-free read operations. Our data structure is designed considering GPU specific hardware characteristics. We also propose a warp-level pre-combinations data sharing strategy to obtain high parallel acceleration. Experiments on an Nvidia RTX2080Ti GPU suggest that GHSH performs about 20-100X faster than its counterpart on CPU. Specifically, GHSH performs updates with up to 396\u00a0M updates\/s and processes search queries with up to 995\u00a0M queries\/s. Compared to other GPU hashes that cannot conduct queries on non-key attributes, GHSH demonstrates comparable building and retrieval performance.<\/jats:p>","DOI":"10.1007\/s41019-021-00161-5","type":"journal-article","created":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T12:02:31Z","timestamp":1623931351000},"page":"265-279","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["GPU-Based Dynamic Hyperspace Hash with Full Concurrency"],"prefix":"10.1007","volume":"6","author":[{"given":"Zhuo","family":"Ren","sequence":"first","affiliation":[]},{"given":"Yu","family":"Gu","sequence":"additional","affiliation":[]},{"given":"Chuanwen","family":"Li","sequence":"additional","affiliation":[]},{"given":"FangFang","family":"Li","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Yu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"161_CR1","doi-asserted-by":"crossref","unstructured":"Escriva R, Wong B, G\u00fcn Sirer E (2012) Hyperdex: a distributed, searchable key-value store. In: PrACM SIGCOMM. ACM, pp 25\u201336","DOI":"10.1145\/2377677.2377681"},{"key":"161_CR2","unstructured":"D\u2019silva JV (2017) Roger Ruiz-Carrillo, and Cong Yu. Two rings to rule them all. In: DOLAP, Secondary indexing techniques for key-value stores"},{"key":"161_CR3","unstructured":"Pedro H, Matheus N, de\u00a0Almeida Eduardo\u00a0C (2018) Cracking kd-tree: the first multidimensional adaptive indexing (position paper). In: EDDY"},{"issue":"2","key":"161_CR4","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/2656864.2656866","volume":"14","author":"N Diegues","year":"2014","unstructured":"Diegues N, Orazov M, Paiva J, Rodrigues L, Romano P (2014) Optimizing hyperspace hashing via analytical modelling and adaptation. ACM SIGAPP Appl Comput Rev 14(2):23\u201335","journal-title":"ACM SIGAPP Appl Comput Rev"},{"key":"161_CR5","unstructured":"Guide Design (2013) Cuda c programming guide. In: NVIDIA"},{"key":"161_CR6","volume-title":"OpenCL programming guide","author":"A Munshi","year":"2011","unstructured":"Munshi A, Gaster B, Mattson TG, Ginsburg D (2011) OpenCL programming guide. Pearson Education, New York"},{"key":"161_CR7","unstructured":"Abdul QM, Shiwen C (2018) A comparative study of secondary indexing techniques in lsm-based nosql database. In: SIGMOD. pp 551\u2013566"},{"key":"161_CR8","unstructured":"Kneale Samuel\u00a0G (1958) Dynamic programming: by richard bellman. 342 pages, 6 $$\\times$$[formula omitted] in Princeton. Princeton university press, 1957. price, \\$6.75. J Franklin Inst 265(2):157\u2013158"},{"issue":"5","key":"161_CR9","first-page":"154","volume":"28","author":"A Alcantara Dan","year":"2009","unstructured":"Alcantara Dan A, Andrei S, Fatemeh A, Shubhabrata S, Michael M, Owens John D (2009) Amenta Nina Real-time parallel hashing on the gpu. ACM Trans Graph (TOG) 28(5):154","journal-title":"ACM Trans Graph (TOG)"},{"key":"161_CR10","volume-title":"Cuda data parallel primitives library","author":"M Harris","year":"2007","unstructured":"Harris M, Owens J, Sengupta S, Zhang Y, Davidson A (2007) Cuda data parallel primitives library. Cudpp, New York"},{"key":"161_CR11","doi-asserted-by":"crossref","unstructured":"Ismael G, Sylvain L, Samuel H, Anass L (2011) Coherent parallel hashing. In: TOG, vol. 30. ACM, pp 161","DOI":"10.1145\/2070781.2024195"},{"key":"161_CR12","unstructured":"Farzad K, Mehmet\u00a0BE, Rajiv G (2015) Stadium hashing: scalable and flexible hashing on gpus. In: PACT. IEEE, pp 63\u201374"},{"key":"161_CR13","unstructured":"Prabhakar M, Mainak C (2012) Performance evaluation of concurrent lock-free data structures on gpus. In: ICPADS. IEEE, pp 53\u201360"},{"key":"161_CR14","unstructured":"Saman A, Martin F-C, John\u00a0OD (2018) A dynamic hash table for the gpu. In: IPDPS. IEEE, pp 419\u2013429"},{"key":"161_CR15","doi-asserted-by":"crossref","unstructured":"Daniel C, Bapi C, Philippas T (2012) Understanding the performance of concurrent data structures on graphics processors. In: Euro-Par. Springer, pp 883\u2013894","DOI":"10.1007\/978-3-642-32820-6_87"},{"issue":"1","key":"161_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s41019-019-0088-6","volume":"4","author":"A Maksudul","year":"2019","unstructured":"Maksudul A, Kalyan PS, Peter S (2019) Novel parallel algorithms for fast multi-gpu-based generation of massive scale-free networks. Data Sci Eng 4(1):61\u201375","journal-title":"Data Sci Eng"},{"issue":"8","key":"161_CR17","first-page":"449","volume":"52","author":"N Moscovici","year":"2017","unstructured":"Moscovici N, Cohen N, Petrank E (2017) Poster: a gpu-friendly skiplist algorithm. PPOPP 52(8):449\u2013450","journal-title":"PPOPP"},{"key":"161_CR18","unstructured":"Pawan H, Narayanan PJ (2007) Accelerating large graph algorithms on the gpu using cuda. In: HPCS. Springer, pp 197\u2013208"},{"issue":"6","key":"161_CR19","first-page":"1543","volume":"25","author":"J Zhong","year":"2013","unstructured":"Zhong J, He B (2013) Medusa: simplified graph processing on gpus. TPDS 25(6):1543\u20131552","journal-title":"TPDS"},{"issue":"2","key":"161_CR20","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2717511","volume":"1","author":"D Merrill","year":"2015","unstructured":"Merrill D, Garland M, Grimshaw A (2015) High-performance and scalable gpu graph traversal. TOPC 1(2):14","journal-title":"TOPC"},{"key":"161_CR21","doi-asserted-by":"crossref","unstructured":"Brandon T, Brennan S, Jason S, Joseph\u00a0MM, David C (2020) Increasing the efficiency of gpu bitmap index query processing. In: International conference on database systems for advanced applications. Springer, pp 339\u2013355","DOI":"10.1007\/978-3-030-59419-0_21"},{"key":"161_CR22","unstructured":"Harish D, Juliana F (2020) A gpu-friendly geometric data model and algebra for spatial queries. In: Proceedings of the 2020 ACM SIGMOD international conference on management of data. pp 1875\u20131885"},{"key":"161_CR23","unstructured":"Chandra R, Dagum L, Kohr D, Maydan D, McDonald J (2001) Parallel programming in OpenMP. Morgan kaufmann, Ramesh Menon"},{"key":"161_CR24","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-030-60290-1_32","volume-title":"Web and big data","author":"Z Ren","year":"2020","unstructured":"Ren Z, Gu Y, Li C, Li F, Yu G (2020) Ghsh: dynamic hyperspace hashing on gpu. In: Wang X, Zhang R, Lee Y-K, Sun L, Moon Y-S (eds) Web and big data. Springer, Cham, pp 409\u2013424"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-021-00161-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-021-00161-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-021-00161-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T08:01:15Z","timestamp":1627632075000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-021-00161-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,17]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["161"],"URL":"https:\/\/doi.org\/10.1007\/s41019-021-00161-5","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,17]]},"assertion":[{"value":"19 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}