Stable and low associative left-right hashing

• Autorzy: Tripathi Rajeev Ranjan Kumar , Singh Pradeep Kumar , Singh Sarvpal

Identyfikatory

DOI

10.7494/csci.2025.26.2.6361

• Języki publikacji: EN

Abstrakty

EN

Hashing is indispens able for efficient search operations, captivating the interest of numerous researchers. Among the diverse array of techniques, Cuckoo Hashing has emerged as particularly effective across a wide range of applications. Nonetheless, Cuckoo Hashing encounters significant challenges, including highinsertion latency, inefficient memory usage, and high data migration costs. The concept of Combinatorial Hashing has inspired this research. Our proposed scheme enhances Combinatorial Hashing and introduces an innovative collision resolution technique called Left-Right Random Probing based on Random Probing. This paper introduces two performance indicators, the degree of dexterity and table reference count per key. This paper identifies and quantifies the switching cost as a new challenge in Cuckoo Hashing. The space complexity and insertion latency of proposed scheme is1.7 times and 1.5 times better than Cuckoo Hashing respectively. Proposed scheme is1.35 times faster than Cuckoo Hashing and its time complexity is nearly same as Cuckoo Hashing.

Słowa kluczowe

EN

Cuckoo Hashing; combinatorial hashing; switching cost; degree of dexterity; random probing

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2025
• Tom: T. 26 (2)
• Strony: 149--187
• Opis fizyczny: Bibliogr. 64 poz., rys., tab., wykr.

Twórcy

autor

Tripathi Rajeev Ranjan Kumar

• Madan Mohan Malaviya University of Technology, Department of Computer Scienceand Engineering, Gorakhpur, Uttar Pradesh, India

autor

Singh Pradeep Kumar

• Madan Mohan Malaviya University of Technology, Department of Computer Scienceand Engineering, Gorakhpur, Uttar Pradesh, India

autor

Singh Sarvpal

• Madan Mohan Malaviya University of Technology, Department of Information Technologyand Computer Application, Gorakhpur, Uttar Pradesh, India,

Bibliografia

• [1] Awad M.A., Ashkiani S., Porumbescu S.D., Farach-Colton M., Owens J.D.: Analyzing and implementing GPU hash tables. In: 2023 Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 33–50, SIAM, 2023. doi: 10.1137/1.9781611977578.ch3.
• [2] Balkesen C., Teubner J., Alonso G., Ozsu M.T.: Main-memory hash joins onmulti-core CPUs: Tuning to the underlying hardware. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 362–373, IEEE Computer Society, Los Alamitos, CA, USA, 2013. doi: 10.1109/ICDE.2013.6544839.
• [3] Bender M.A., Conway A., Farach-Colton M., Kuszmaul W., Tagliavini G.: Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once, Journal of the ACM, vol. 70(6), 2023. doi: 10.1145/3625817.
• [4] Bender M.A., Farach-Colton M., Kuszmaul J., Kuszmaul W.: Modern Hashing Made Simple. In: 2024 Symposium on Simplicity in Algorithms (SOSA), pp. 363–373, SIAM, 2024. doi: 10.1137/1.9781611977936.33.
• [5] Bender M.A., Farach-Colton M., Kuszmaul J., Kuszmaul W., Liu M.: On the optimal time/space trade off for hash tables. In: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1284–1297, Association for Computing Machinery, New York, NY, USA, 2022. doi: 10.1145/3519935.3519969.
• [6] Bozsolik T.: Random numbers, 2019. doi: 10.34740/KAGGLE/DSV/816507.
• [7] Brouwer A.E.: An associative block design ABD (8, 5), SIAM Journal on Computing, vol. 28(6), pp. 1970–1971, 1999. doi: 10.1137/s0097539797316622.
• [8] Carter J.L., Wegman M.N.: Universal classes of hash functions, Journal of Computer and System Sciences, vol. 18(2), pp. 143–154, 1979. doi: 10.1016/0022-0000(79)90044-8.
• [9] Celis P., Larson P.A., Munro J.I.: Robin hood hashing. In: 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pp. 281–288, 1985.doi: 10.1109/SFCS.1985.48.
• [10] Chen W.C., Vitter J.S.: Analysis of new variants of coalesced hashing, ACMTransactions on Database Systems, vol. 9(4), pp. 616–645, 1984. doi: 10.1145/1994.2205.
• [11] Chen Z., He X., Sun J., Chen H., He L.: Concurrent hash tables on multicore machines: Comparison, evaluation and implications, Future Generation Computer Systems, vol. 82, pp. 127–141, 2018. doi: https://doi.org/10.1016/j.future.2017.12.054.
• [12] Devroye L., Morin P.: Cuckoo hashing: Further analysis, Information Processing Letters, vol. 86(4), pp. 215–219, 2003. doi: https://doi.org/10.1016/S0020-0190(02)00500-8.
• [13] Dolev S., Lahiani L., Haviv Y.: Unique permutation hashing, Theoretical Computer Science, vol. 475, pp. 59–65, 2013. doi: 10.1016/j.tcs.2012.12.047.
• [14] Flajolet P., Poblete P., Viola A.: On the analysis of linear probing hashing, Algorithmica, vol. 22(4), pp. 490–515, 1998. doi: 10.1007/pl00009236.
• [15] Frieze A., Johansson T.: On the insertion time of random walk cuckoo hashing, Random Structures and Algorithms, vol. 54(4), pp. 721–729, 2019. doi: 10.1002/rsa.20808.
• [16] Gao J., Tao X., Cai S.: Towards more efficient local search algorithms for constrained clustering, Information Sciences, vol. 621, pp. 287–307, 2023. doi: 10.1016/j.ins.2022.11.107.
• [17] Gonnet G.H.: Expected length of the longest probe sequence in hash code searching, Journal of the ACM, vol. 28(2), p. 289–304, 1981. doi: 10.1145/322248.322254.
• [18] Greene D.H., Knuth D.E.: Mathematics for the Analysis of Algorithms, Springer Science & Business Media, 2007.
• [19] Halatsis C., Philokyprou G.: Pseudochaining in hash tables, Communications of the ACM, vol. 21(7), p. 554–557, 1978. doi: 10.1145/359545.359560.
• [20] Han Z., Li Y., Li J.: A novel routing algorithm for IoT cloud based on hashoffset tree, Future Generation Computer Systems, vol. 86, pp. 456–463, 2018.doi: 10.1016/j.future.2018.02.047.
• [21] Janson S.: Asymptotic distribution for the cost of linear probing hashing, Random Structures and Algorithms, vol. 19(3-4), pp. 438–471, 2001. doi: 10.1002/rsa.10009.
• [22] Janson S., Viola A.: A unified approach to linear probing hashing with buckets, Algorithmica, vol. 75(4), pp. 724–781, 2016. doi: 10.1007/s00453-015-0111-x.
• [23] Jensen M.S., Pagh R.: Optimality in external memory hashing, Algorithmica, vol. 52(3), pp. 403–411, 2008. doi: 10.1007/s00453-007-9155-x.
• [24] Jiang J., Yan Y., Zhang M., Yin B., Jiang Y., Yang T., Li X., Wang T.: Shifting hash table: An efficient hash table with delicate summary. In: 2019 IEEE Globecom Workshops (GC Wkshps), IEEE, 2019. doi: 10.1109/gcwkshps45667.2019.9024392.
• [25] Karp R.M., Luby M., Heide auf der F.M.: Efficient PRAM simulation ona distributed memory machine, Algorithmica, vol. 16(4), pp. 517–542, 1996.doi: 10.1007/bf01940878.
• [26] Knott G.D., Torre de la P.: Hash table collision resolution with direct chaining, Journal of Algorithms, vol. 10(1), pp. 20–34, 1989. doi: 10.1016/0196-6774(89)90021-7.
• [27] K ̈oppl D., Puglisi S.J., Raman R.: Fast and simple compact hashing via bucketing, Algorithmica, vol. 84(9), pp. 2735–2766, 2022. doi: 10.1007/s00453-022-00996-y.
• [28] Kurpicz F., Lehmann H.P., Sanders P.: PaCHash: packed and compressed hashtables, pp. 162–175. doi: 10.1137/1.9781611977561.ch14.
• [29] Larson P.: Analysis of uniform hashing, Journal of the ACM, vol. 30(4), pp. 805–819, 1983. doi: 10.1145/2157.322407.
• [30] Lehmann H.P., Sanders P., Walzer S.: SicHash – small irregular cuckoo tables for perfect hashing. In: 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pp. 176–189, SIAM, 2023.doi: 10.1137/1.9781611977561.ch15.
• [31] Lehmann H.P., Sanders P., Walzer S.: Shock Hash: Towards optimal-space minimal perfect hashing beyond brute-force. In: 2024 Proceedings of the Symposiumon Algorithm Engineering and Experiments (ALENEX), pp. 194–206, SIAM, 2024. doi: 10.1137/1.9781611977929.15.
• [32] Li Y., Zhu Q., Lyu Z., Huang Z., Sun J.: DyCuckoo: Dynamic hash tables on GPUs. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 744–755, 2021. doi: 10.1109/ICDE51399.2021.00070.
• [33] Lopez-Valdivieso J., Cumplido R.: Design and implementation of hardware-software architecture based on hashes for SPHINCS+, ACM Transactions on Reconfigurable Technology and Systems, vol. 17(4), 54, 2024. doi: 10.1145/3653459.
• [34] Luo W.:Hashing via finite field,Information Sciences, vol. 176(17), pp. 2553–2566, 2006. doi: 10.1016/j.ins.2005.12.001.
• [35] Ma Z., Sha E.H.M., Zhuge Q., Jiang W., Zhang R., Gu S.: Towards the design of efficient hash-based indexing scheme for growing databases on non-volatile memory, Future Generation Computer Systems, vol. 105, pp. 1–12, 2020.doi: 10.1016/j.future.2019.07.035.
• [36] Majewski B.S., Wormald N.C., Havas G., Czech Z.J.: A family of perfect has hing methods, The Computer Journal, vol. 39(6), pp. 547–554, 1996. doi: 10.1093/comjnl/39.6.547.
• [37] Manohar S., Vignesh M., Prabhu G.M.: Sensitive data transaction using RDSin AWS, Advances in Science and Technology, vol. 124, pp. 782–788, 2023.doi: 10.4028/p-3z1665.
• [38] Minaud B., Papamanthou C.: Generalized cuckoo hashing with a stash, revisited, Information Processing Letters, vol. 181, 106356, 2023. doi: 10.1016/j.ipl.2022.106356.
• [39] Mitzenmacher M.: Some open questions related to Cuckoo Hashing. In: A. Fiat, P. Sanders (eds.), Algorithms – ESA 2009, Springer, Berlin–Heidelberg, 2009.doi: 10.1007/978-3-642-04128-01.
• [40] Morris R.: Scatter storage techniques, Communications of the ACM, vol. 11(1), pp. 38–44, 1968. doi: 10.1145/362851.362882.
• [41] Mugher R.A., Alhammadi N.A.M.: Performance evaluation of quadratic probing and random probing algorithms in modeling hashing technique, Journal of Soft Computing and Data Mining, vol. 3(2), pp. 52–59, 2022. doi: 10.30880/jscdm.2022.03.02.006.
• [42] Narayanan V., Detweiler D., Huang T., Burtsev A.: DRAMHiT: A hash table architected for the speed of DRAM. In: EuroSys ’23: Proceedings of the Eighteenth European Conference on Computer Systems, pp. 817–834, Association for Computing Machinery, New York, NY, USA, 2023. doi: 10.1145/3552326.3587457.
• [43] Oussous A., Benjelloun F.Z., Ait Lahcen A., Belfkih S.: Big Data technologies: A survey, Journal of King Saud University – Computer and Information Sciences, vol. 30(4), pp. 431–448, 2018. doi: 10.1016/j.jksuci.2017.06.001.
• [44] Pagh R., Rodler F.F.: Cuckoo hashing. In: F.M. Heide auf der (ed.), Algorithms– ESA 2001, pp. 121–133, Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.doi: 10.1007/3-540-44676-1.
• [45] Pagh R., Rodler F.F.: Cuckoo hashing, Journal of Algorithms, vol. 51(2), pp. 122–144, 2004. doi: 10.1016/j.jalgor.2003.12.002.
• [46] Patrascu M., Thorup M.: The power of simple tabulation hashing, Journal of the ACM, vol. 59(3), 2012. doi: 10.1145/2220357.2220361.
• [47] Pontarelli S., Reviriego P., Mitzenmacher M.: EMOMA: Exact match inone memory access, IEEE Transactions on Knowledge and Data Engineering, vol. 30(11), pp. 2120–2133, 2018. doi: 10.1109/tkde.2018.2818716.
• [48] Porat E., Shalem B.: A cuckoo hashing variant with improved memory utilization and insertion time. In: J.A. Storer, M.W. Marcellin (eds.), 2012 Data Compression Conference, Snowbird, UT, USA, April 10–12, 2012, pp. 347–356, IEEE Computer Society, 2012. doi: 10.1109/DCC.2012.41.
• [49] Rajwar K., Deep K., Das S.: An exhaustive review of the metaheuristic algorithms for search and optimization: taxonomy, applications, and open challenges, Artificial Intelligence Review, vol. 56, pp. 13187–13257, 2023. doi: 10.1007/s10462-023-10470-y.
• [50] Ramakrishna M.: Analysis of random probing hashing, Information Processing Letters, vol. 31(2), pp. 83–90, 1989. doi: 10.1016/0020-0190(89)90073-2.
• [51] Ramakrishna M.V.: Hashing practice: analysis of hashing and universal hashing, ACM SIGMOD Record, vol. 17(3), pp. 191–199, 1988. doi: 10.1145/50202.50223.
• [52] Regassa D., Sung D., Kim S., Yeom H.Y., Son Y.: EHS: An efficient hashing scheme for persistent memory. In: SAC ’23: Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing, pp. 301–304, Association for Computing Machinery, New York, NY, USA, 2023.doi: 10.1145/3555776.3577850.
• [53] Rivest R.L.: On hash-coding algorithms for partial-match retrieval. In: 15th Annual Symposium on Switching and Automata Theory (swat 1974), pp. 95–103, IEEE, 1974. doi: 10.1109/swat.1974.17.
• [54] Sanders P.: Hashing with linear probing and referential integrity, 2018. doi: 10.48550/arXiv.1808.04602.
• [55] Shahbazi N., Sintos S., Asudeh A.: FairHash: A fair and memory/time-efficienth ashmap, Proceedings of the ACM on Management of Data, vol. 2(3), 136, 2024.doi: 10.1145/3654939.
• [56] Shi S., Qian C.: Ludo hashing: Compact, fast, and dynamic key-value lookups for practical network systems, Proceedings of the ACM on Measurement and Analysisof Computing Systems, vol. 4(2), pp. 1–32, 2020. doi: 10.1145/3392140.
• [57] Sprugnoli R.: Perfect hashing functions: a single probe retrieving method for static sets, Communications of the ACM, vol. 20(11), pp. 841–850, 1977.doi: 10.1145/359863.359887.
• [58] Sun Y., Hua Y., Chen Z., Guo Y.: Mitigating asymmetric read and write costs in cuckoo hashing for storage systems. In: 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 329–344, USENIX Association, Renton, WA, 2019. https://www.usenix.org/conference/atc19/presentation/sun.
• [59] Sun Y., Hua Y., Feng D., Yang L., Zuo P., Cao S., Guo Y.: A collision-mitigation cuckoo hashing scheme for large-scale storage systems, IEEE Transactions on Parallel and Distributed Systems, vol. 28(3), pp. 619–632, 2017. doi: 10.1109/TPDS.2016.2594763.
• [60] Thorup M.: Fast and powerful hashing using tabulation, Communications of the ACM, vol. 60(7), p. 94–101, 2017. doi: 10.1145/3068772.
• [61] Walzer S.: Load thresholds for cuckoo hashing with overlapping blocks, ACM Transactions on Algorithms, vol. 19(3), 24, 2023. doi: 10.1145/3589558.
• [62] Wiederhold G.: Database design, vol. 1077, McGraw-Hill New York, 1983.
• [63] Wu X., Zhu X., Wu M.: The evolution of search: Three computing paradigms, ACM Transactions on Management Information Systems (TMIS), vol. 13(2), 20, 2022. doi: 10.1145/3495214.
• [64] Yang Q., Huang H., Zhang J., Gao H., Liu P.: A collaborative cuckoo search algorithm with modified operation mode, Engineering Applications of Artificial Intelligence, vol. 121, 106006, 2023. doi: 10.1016/j.engappai.2023.106006.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).