{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T02:42:40Z","timestamp":1767926560417,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,6,19]],"date-time":"2023-06-19T00:00:00Z","timestamp":1687132800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2023,8,31]]},"abstract":"<jats:p>Hardware is often required to support fast search and high-throughput applications. Consequently, the performance of search algorithms is limited by storage bandwidth. Hence, the search algorithm must be optimized accordingly. We propose a CostCounter (CC) algorithm based on cuckoo hashing and an Improved CostCounter (ICC) algorithm. A better path can be selected when collisions occur using a cost counter to record the kick-out situation. Our simulation results indicate that the CC and ICC algorithms can achieve more significant performance improvements than Random Walk (RW), Breadth First Search (BFS), and MinCounter (MC). With two buckets and two slots per bucket, under the 95% memory load rate of the maximum load rate, CC and ICC are optimized on read-write times over 20% and 80% compared to MC and BFS, respectively. Furthermore, the CC and ICC algorithms achieve a slight improvement in storage efficiency compared with MC. In addition, we implement RW, MC, and the proposed algorithms using fine-grained locking to support a high throughput rate. From the test on field programmable gate arrays, we verify the simulation results and our algorithms optimize the maximum throughput over 23% compared to RW and 9% compared to MC under 95% of the memory capacity. The test results indicate that our CC and ICC algorithms can achieve better performance in terms of hardware bandwidth and memory load efficiency without incurring a significant resource cost.<\/jats:p>","DOI":"10.1145\/3596910","type":"journal-article","created":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T11:51:28Z","timestamp":1683892288000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["CostCounter: A Better Method for Collision Mitigation in Cuckoo Hashing"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7701-6129","authenticated-orcid":false,"given":"Haonan","family":"Wu","sequence":"first","affiliation":[{"name":"School of Communication &amp; Electronic Engineering, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8090-3036","authenticated-orcid":false,"given":"Shuxian","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Communication &amp; Electronic Engineering, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4288-2326","authenticated-orcid":false,"given":"Zhanfeng","family":"Jin","sequence":"additional","affiliation":[{"name":"School of Communication &amp; Electronic Engineering, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6167-3618","authenticated-orcid":false,"given":"Yuhang","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Communication &amp; Electronic Engineering, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9007-6196","authenticated-orcid":false,"given":"Ruyun","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Communication &amp; Electronic Engineering, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0415-4758","authenticated-orcid":false,"given":"Sijin","family":"Fan","sequence":"additional","affiliation":[{"name":"School of Communication &amp; Electronic Engineering, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9889-904X","authenticated-orcid":false,"given":"Ruili","family":"Chao","sequence":"additional","affiliation":[{"name":"School of Communication &amp; Electronic Engineering, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,19]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Akamai. 2020. 2020 State of the Internet\/Security: 2020\u2014A Year in Review. Retrieved June 23 2022 from https:\/\/www.akamai.com\/our-thinking\/the-state-of-the-internet\/state-of-the-internet-security-reports-2020."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/tnet.2012.2188643"},{"key":"e_1_3_1_4_2","first-page":"281","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201916)","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 Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201916). USENIX, 281\u2013294."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/surv.2011.072210.00075"},{"key":"e_1_3_1_6_2","unstructured":"Cisco. 2020. Cisco Annual Internet Report (2018\u20132023) White Paper. Retrieved June 23 2022 from https:\/\/www.cisco.com\/c\/en\/us\/solutions\/collateral\/executive-perspectives\/annual-internet-report\/white-paper-c11-741490.html?dtid=osscdc000283."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2017.03.009"},{"key":"e_1_3_1_8_2","first-page":"1","volume-title":"Proceedings of the 7th Whorkshop on Distributed Data and Structures","author":"Erlingsson U.","year":"2006","unstructured":"U. Erlingsson, M. Manasse, and F. Mcsherry. 2006. A cool and practical alternative to traditional hash tables. In Proceedings of the 7th Whorkshop on Distributed Data and Structures. 1\u20136."},{"key":"e_1_3_1_9_2","first-page":"371","volume-title":"Proceedings of the USENIX Conference on Networked Systems Design & Implementation (NSDI\u201913)","volume":"3","author":"Fan Bin","year":"2013","unstructured":"Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and concurrent memcache with dumber caching and smarter hashing. In Proceedings of the USENIX Conference on Networked Systems Design & Implementation (NSDI\u201913), Vol. 3. USENIX Association, 371\u2013384."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/090770928"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/103324"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/nem.1863"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629582"},{"issue":"8","key":"e_1_3_1_16_2","first-page":"80","article-title":"Cuckoo hash table based on smart placement strategy","volume":"47","author":"Jin Qi","year":"2020","unstructured":"Qi Jin, Junchang Wang, and Xiong Fu. 2020. Cuckoo hash table based on smart placement strategy. Comput. Sci. 47, 8 (2020), 80\u201386.","journal-title":"Comput. Sci."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ddecs.2014.6868793"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2019.102950"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/080728743"},{"key":"e_1_3_1_20_2","series-title":"Fundamental Algorithms","volume-title":"The Art of Computer Programming","author":"Knuth Donald E.","year":"1998","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming (2nd ed.). Fundamental Algorithms, Vol. 3. Pearson Education. (book)."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/mcom.2017.1700132"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/tpds.2017.2674664"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9297-0"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/mic.2016.55"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/tc.2015.2417524"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/lcomm.2019.2930508"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.03.008"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/tpds.2016.2594763"},{"key":"e_1_3_1_31_2","first-page":"553","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Sun Yuanyuan","year":"2017","unstructured":"Yuanyuan Sun, Yu Hua, Song Jiang, Qiuyu Li, Shunde Cao, and Pengfei Zuo. 2017. SmartCuckoo: A fast and cost-efficient hashing index scheme for cloud storage systems. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201917). USENIX, 553\u2013565."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ipdpsw.2015.149"},{"key":"e_1_3_1_33_2","volume-title":"Proceedings of the USENIX Annual Technical Conference","author":"Triplett J.","year":"2011","unstructured":"J. Triplett, P. E. Mckenney, and J. Walpole. 2011. Resizable, scalable, concurrent hash tables via relativistic programming. In Proceedings of the USENIX Annual Technical Conference. 11."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/tvlsi.2017.2753843"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/access.2019.2927863"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3322096"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596910","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3596910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:47Z","timestamp":1750182527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596910"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,19]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1145\/3596910"],"URL":"https:\/\/doi.org\/10.1145\/3596910","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,19]]},"assertion":[{"value":"2022-06-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}