{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T23:33:00Z","timestamp":1791070380364,"version":"4.1.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["5.41E+26"],"award-info":[{"award-number":["5.41E+26"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself, and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching.<\/jats:p>","DOI":"10.1145\/1618452.1618500","type":"journal-article","created":{"date-parts":[[2009,12,8]],"date-time":"2009-12-08T15:53:14Z","timestamp":1260287594000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":91,"title":["Real-time parallel hashing on the GPU"],"prefix":"10.1145","volume":"28","author":[{"given":"Dan A.","family":"Alcantara","sequence":"first","affiliation":[{"name":"University of California, Davis"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrei","family":"Sharf","sequence":"additional","affiliation":[{"name":"University of California, Davis"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fatemeh","family":"Abbasinejad","sequence":"additional","affiliation":[{"name":"University of California, Davis"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shubhabrata","family":"Sengupta","sequence":"additional","affiliation":[{"name":"University of California, Davis"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[{"name":"Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John D.","family":"Owens","sequence":"additional","affiliation":[{"name":"University of California, Davis"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nina","family":"Amenta","sequence":"additional","affiliation":[{"name":"University of California, Davis"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1995.1098"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.641606"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113384"},{"key":"e_1_2_1_5_1","volume-title":"IEEE International Conference on Shape Modeling and Applications, 171--178","author":"Bastos T.","unstructured":"Bastos , T. , and Celes , W . 2008. GPU-accelerated adaptively sampled distance fields . In IEEE International Conference on Shape Modeling and Applications, 171--178 . Bastos, T., and Celes, W. 2008. GPU-accelerated adaptively sampled distance fields. In IEEE International Conference on Shape Modeling and Applications, 171--178."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the National Conference on Communication, 533--537","author":"Bhosle U.","unstructured":"Bhosle , U. , Chaudhuri , S. , and Roy , S. D . 2002. The use of geometric hashing for automatic image mosaicing . In Proceedings of the National Conference on Communication, 533--537 . Bhosle, U., Chaudhuri, S., and Roy, S. D. 2002. The use of geometric hashing for automatic image mosaicing. In Proceedings of the National Conference on Communication, 533--537."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237269"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1230100.1230128"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00500-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/129617.129623"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Frieze A. Mitzenmacher M. and Melsted P. 2009. An analysis of random-walk cuckoo hashing. In submission.  Frieze A. Mitzenmacher M. and Melsted P. 2009. An analysis of random-walk cuckoo hashing. In submission.","DOI":"10.1007\/978-3-642-03685-9_37"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122501.1122507"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.641608"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 271--280","author":"Gil J.","unstructured":"Gil , J. , and Matias , Y . 1991. Fast hashing on a PRAM---designing by expectation . In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 271--280 . Gil, J., and Matias, Y. 1991. Fast hashing on a PRAM---designing by expectation. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 271--280."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794291580"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.641607"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566633"},{"key":"e_1_2_1_20_1","volume-title":"Second International Conference on Computer Vision (ICCV), 238--249","author":"Lamdan Y.","unstructured":"Lamdan , Y. , and Wolfson , H. J . 1988. Geometric hashing: A general and efficient model-based recognition scheme . In Second International Conference on Computer Vision (ICCV), 238--249 . Lamdan, Y., and Wolfson, H. J. 1988. Geometric hashing: A general and efficient model-based recognition scheme. In Second International Conference on Computer Vision (ICCV), 238--249."},{"key":"e_1_2_1_21_1","volume-title":"IEEE International Conference on Robotics and Automation","volume":"3","author":"Lamdan Y.","unstructured":"Lamdan , Y. , Schwartz , J. T. , and Wolfson , H. J . 1988. On recognition of 3-D objects from 2-D images . In IEEE International Conference on Robotics and Automation , vol. 3 , 1407--1413. Lamdan, Y., Schwartz, J. T., and Wolfson, H. J. 1988. On recognition of 3-D objects from 2-D images. In IEEE International Conference on Robotics and Automation, vol. 3, 1407--1413."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.62047"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141926"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122501.1122505"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming, 729--743","author":"Matias Y.","unstructured":"Matias , Y. , and Vishkin , U . 1990. On parallel hashing and integer sorting . In Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming, 729--743 . Matias, Y., and Vishkin, U. 1990. On parallel hashing and integer sorting. In Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming, 729--743."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103453"},{"key":"e_1_2_1_27_1","volume-title":"Tech. Rep. MSR-TR-2007-95, Microsoft.","author":"Nehab D.","year":"2007","unstructured":"Nehab , D. , and Hoppe , H . 2007 . Texel programs for random-access antialiased vector graphics. Tech. Rep. MSR-TR-2007-95, Microsoft. Nehab, D., and Hoppe, H. 2007. Texel programs for random-access antialiased vector graphics. Tech. Rep. MSR-TR-2007-95, Microsoft."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.88.23.10495"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Pagh R. and \n      Rodler F. F\n  . \n  2001\n  . Cuckoo hashing. In 9th Annual European Symposium on Algorithms Springer vol. \n  2161\n   of \n  Lecture Notes in Computer Science 121--133.   Pagh R. and Rodler F. F. 2001. Cuckoo hashing. In 9th Annual European Symposium on Algorithms Springer vol. 2161 of Lecture Notes in Computer Science 121--133.","DOI":"10.1007\/3-540-44676-1_10"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1342250.1342281"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161005"},{"key":"e_1_2_1_32_1","first-page":"97","article-title":"Scan primitives for GPU computing","volume":"2007","author":"Sengupta S.","year":"2007","unstructured":"Sengupta , S. , Harris , M. , Zhang , Y. , and Owens , J. D. 2007 . Scan primitives for GPU computing . In Graphics Hardware 2007 , 97 -- 106 . Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware 2007, 97--106.","journal-title":"Graphics Hardware"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360634"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_2_1_35_1","volume-title":"Tech. Rep. MSR-TR-2008-53, Microsoft Research, 1 Apr.","author":"Zhou K.","year":"2008","unstructured":"Zhou , K. , Gong , M. , Huang , X. , and Guo , B . 2008 . Highly parallel surface reconstruction. Tech. Rep. MSR-TR-2008-53, Microsoft Research, 1 Apr. Zhou, K., Gong, M., Huang, X., and Guo, B. 2008. Highly parallel surface reconstruction. Tech. Rep. MSR-TR-2008-53, Microsoft Research, 1 Apr."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409079"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360635"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1618452.1618500","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1618452.1618500","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1618452.1618500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:23:23Z","timestamp":1750235003000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1618452.1618500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1618452.1618500"],"URL":"https:\/\/doi.org\/10.1145\/1618452.1618500","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2009-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}