{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:38:59Z","timestamp":1760150339834,"version":"build-2065373602"},"reference-count":99,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T00:00:00Z","timestamp":1698451200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"publisher","award":["A3456"],"award-info":[{"award-number":["A3456"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Linear probing continues to be one of the best practical hashing algorithms due to its good average performance, efficiency, and simplicity of implementation. However, the worst-case performance of linear probing seems to degrade with high load factors due to a primary-clustering tendency of one collision to cause more nearby collisions. It is known that the maximum cluster size produced by linear probing, and hence the length of the longest probe sequence needed to insert or search for a key in a hash table of size n, is \u03a9(logn), in probability. In this article, we introduce linear probing hashing schemes that employ two linear probe sequences to find empty cells for the keys. Our results show that two-way linear probing is a promising alternative to linear probing for hash tables. We show that two-way linear probing has an asymptotically almost surely O(loglogn) maximum cluster size when the load factor is constant. Matching lower bounds on the maximum cluster size produced by any two-way linear probing algorithm are obtained as well. Our analysis is based on a novel approach that uses the multiple-choice paradigm and witness trees.<\/jats:p>","DOI":"10.3390\/a16110500","type":"journal-article","created":{"date-parts":[[2023,10,30]],"date-time":"2023-10-30T09:27:28Z","timestamp":1698658048000},"page":"500","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Two-Way Linear Probing Revisited"],"prefix":"10.3390","volume":"16","author":[{"given":"Ketan","family":"Dalal","sequence":"first","affiliation":[{"name":"School of Computer Science, McGill University, Montreal, QC H3A 2K6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Devroye","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, Montreal, QC H3A 2K6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1109-106X","authenticated-orcid":false,"given":"Ebrahim","family":"Malalla","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, Montreal, QC H3A 2K6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,10,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1147\/rd.12.0130","article-title":"Addressing for random-access storage","volume":"1","author":"Peterson","year":"1957","journal-title":"IBM J. Res. Dev."},{"key":"ref_2","unstructured":"Gonnet, G.H., and Baeza-Yates, R. (1991). Handbook of Algorithms and Data Structures, Addison-Wesley."},{"key":"ref_3","unstructured":"Knuth, D.E. (1973). The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"van Leeuwen, J. (1990). Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, MIT Press.","DOI":"10.1016\/B978-0-444-88071-0.50015-1"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1007\/s00453-015-0111-x","article-title":"A unified approach to linear probing hashing with buckets","volume":"75","author":"Janson","year":"2016","journal-title":"Algorithmica"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1137\/110827831","article-title":"Linear probing with 5-wise independence","volume":"53","author":"Pagh","year":"2011","journal-title":"SIAM Rev."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"96","DOI":"10.14778\/2850583.2850585","article-title":"A seven-dimensional analysis of hashing methods and its implications on query processing","volume":"9","author":"Richter","year":"2015","journal-title":"Porc. Vldb Endow."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1137\/100800774","article-title":"Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation","volume":"41","author":"Thorup","year":"2012","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0196-6774(87)90040-X","article-title":"Linear probing: The probable largest search time grows logarithmically with the number of records","volume":"8","author":"Pittel","year":"1987","journal-title":"J. Algorithms"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/S0097539795288490","article-title":"Balanced allocations","volume":"29","author":"Azar","year":"2000","journal-title":"SIAM J. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1145\/792538.792546","article-title":"How asymmetry helps load balancing","volume":"50","year":"2003","journal-title":"J. ACM"},{"key":"ref_12","unstructured":"Malalla, E. (2004). Two-Way Hashing with Separate Chaining and Linear Probing. [Ph.D. Thesis, School of Computer Science, McGill University]."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1137\/S0097539704443240","article-title":"Two-way chaining with reassignment","volume":"35","author":"Dalal","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1350","DOI":"10.1137\/S009753970444435X","article-title":"Balanced allocations: The heavily loaded case","volume":"35","author":"Berenbrink","year":"2006","journal-title":"SIAM J. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1080\/00207160802132871","article-title":"Two-way chaining for non-uniform distributions","volume":"87","author":"Malalla","year":"2010","journal-title":"Int. J. Comput. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/362851.362882","article-title":"Scatter storage techniques","volume":"11","author":"Morris","year":"1968","journal-title":"Commun. ACM"},{"key":"ref_17","unstructured":"De Balbine, G. (1969). Computational Analysis of the Random Components Induced by Binary Equivalence Relations. [Ph.D. Thesis, California Institute of Technology]."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1145\/321707.321722","article-title":"A note on the efficiency of hashing functions","volume":"19","author":"Ullman","year":"1972","journal-title":"J. ACM"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1145\/3828.3836","article-title":"Uniform hashing is optimal","volume":"32","author":"Yao","year":"1985","journal-title":"J. ACM"},{"key":"ref_20","unstructured":"Munro, J.I., and Celis, P. (1999, January 2\u20136). Techniques for collision resolution in hash tables with open addressing. Proceedings of the 1986 Fall Joint Computer Conference, Dallas, TX, USA."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0196-6774(89)90014-X","article-title":"Last-Come-First-Served hashing","volume":"10","author":"Poblete","year":"1989","journal-title":"J. Algorithms"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Celis, P. (1986). Robin Hood Hashing. [Ph.D. Thesis, Computer Science Department, University of Waterloo].","DOI":"10.1109\/SFCS.1985.48"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Celis, P., Larson, P., and Munro, J.I. (1985, January 21\u201323). Robin Hood hashing (preliminary report). Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.48"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1145\/2157.322407","article-title":"Analysis of uniform hashing","volume":"30","author":"Larson","year":"1983","journal-title":"J. ACM"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/77600.77619","article-title":"The cost distribution of clustering in random probing","volume":"37","author":"Broder","year":"1990","journal-title":"J. ACM"},{"key":"ref_26","unstructured":"Knuth, D.E. (2023, August 31). Notes on \u201cOpen\u201d Addressing. Available online: https:\/\/jeffe.cs.illinois.edu\/teaching\/datastructures\/2011\/notes\/knuth-OALP.pdf."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1137\/0114101","article-title":"An occupancy discipline and applications","volume":"14","author":"Konheim","year":"1966","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1145\/322203.322209","article-title":"A new approach to the analysis of linear probing schemes","volume":"27","author":"Mendelson","year":"1980","journal-title":"J. ACM"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1145\/322092.322096","article-title":"The analysis of hashing techniques that exhibit K-ary clustering","volume":"25","author":"Guibas","year":"1978","journal-title":"J. ACM"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01202791","article-title":"More analysis of double hashing","volume":"13","author":"Lueker","year":"1993","journal-title":"Combinatorica"},{"key":"ref_31","unstructured":"Schmidt, J.P., and Siegel, A. (1995). Double Hashing Is Computable and Randomizable with Universal Hash Functions, Computer Science Department, New York University. Submitted. A Full Version Is Available as Technical Report TR1995-686."},{"key":"ref_32","unstructured":"Siegel, A., and Schmidt, J.P. (1995). Closed Hashing Is Computable and Optimally Randomizable with Universal Hash Functions, Computer Science Department, New York University. Submitted. A Full Version Is Available as Technical Report TR1995-687."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/PL00009236","article-title":"On the analysis of linear probing hashing","volume":"22","author":"Flajolet","year":"1998","journal-title":"Algorithmica"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/PL00009240","article-title":"Linear probing and graphs, average-case analysis for algorithms","volume":"22","author":"Knuth","year":"1998","journal-title":"Algorithmica"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/PL00009208","article-title":"The analysis of linear probing hashing with buckets","volume":"21","author":"Viola","year":"1998","journal-title":"Algorithmica"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1002\/rsa.10009","article-title":"Asymptotic distribution for the cost of linear probing hashing","volume":"19","author":"Janson","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0022-0000(80)90028-8","article-title":"Open addressing hashing with unequal-probability keys","volume":"20","author":"Gonnet","year":"1980","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0269964800000577","article-title":"Hashing with linear probing, under non-uniform probabilities","volume":"2","author":"Aldous","year":"1988","journal-title":"Probab. Eng. Inform. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1145\/23005.42225","article-title":"Linear probing with a nonuniform address distribution","volume":"34","author":"Pflug","year":"1987","journal-title":"J. ACM"},{"key":"ref_40","first-page":"8","article-title":"Analyzing the LCFS linear probing hashing algorithm with the help of Maple","volume":"4","author":"Poblete","year":"1997","journal-title":"Maple Tech. Newlett."},{"key":"ref_41","unstructured":"Janson, S. (2003). Individual Displacements for Linear Probing Hashing with Different Insertion Policies, Department of Mathematics, Uppsala University. Technical Report No. 35."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/1103963.1103965","article-title":"Exact distributions of individual displacements in linear probing hashing","volume":"1","author":"Viola","year":"2005","journal-title":"ACM Trans. Algorithms"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1002\/rsa.10039","article-title":"Phase transition for parking blocks, Brownian excursion and coalescence","volume":"21","author":"Chassaing","year":"2002","journal-title":"Random Struct. Algorithms"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/322248.322254","article-title":"Expected length of the longest probe sequence in hash code searching","volume":"28","author":"Gonnet","year":"1981","journal-title":"J. ACM"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1137\/S0097539702403372","article-title":"On worst-case Robin Hood hashing","volume":"33","author":"Devroye","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1137\/0208038","article-title":"Efficient ordering of hash tables","volume":"8","author":"Gonnet","year":"1979","journal-title":"SIAM J. Comput."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/361952.361964","article-title":"Reducing the retrieval time of scatter storage techniques","volume":"16","author":"Brent","year":"1973","journal-title":"Commun. ACM"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1093\/comjnl\/23.2.188","article-title":"Fast lookup in hash tables with direct rehashing","volume":"23","author":"Madison","year":"1980","journal-title":"Comput. J."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1093\/comjnl\/20.2.137","article-title":"Scatter storage techniques: A uniform viewpoint and a method for reducing retrieval times","volume":"20","author":"Mallach","year":"1977","journal-title":"Comput. J."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/322063.322065","article-title":"Optimal arrangement of keys in a hash table","volume":"25","author":"Rivest","year":"1978","journal-title":"J. ACM"},{"key":"ref_51","unstructured":"Pagh, R., and Rodler, F.F. (2001). Algorithms\u2014ESA 2001, Proceedings of the 9th Annual European Symposium, Aarhus, Denmark, 28\u201331 August 2001, Springer. LNCS 2161."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0020-0190(02)00500-8","article-title":"Cuckoo hashing: Further analysis","volume":"86","author":"Devroye","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"\u00d6stlin, A., and Pagh, R. (2003, January 9\u201311). Uniform hashing in constant time and linear space. Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, USA.","DOI":"10.1145\/780542.780633"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., and Wolfel, P. (2003, January 9\u201311). Almost random graphs with simple hash functions. Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, USA.","DOI":"10.1145\/780542.780634"},{"key":"ref_55","unstructured":"Fotakis, D., Pagh, R., Sanders, P., and Spirakis, P. (2003). STACS 2003, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, 27 February\u20131 March 2003, Springer. LNCS 2607."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1002\/rsa.20426","article-title":"Sharp Load Thresholds for Cuckoo Hashing","volume":"41","author":"Fountoulakis","year":"2012","journal-title":"Random Struct. Algorithms"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Lehman, E., and Panigrahy, R. (2009, January 7\u20139). 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit. Proceedings of the 17th Annual European Symposium, Copenhagen, Denmark.","DOI":"10.1007\/978-3-642-04128-0_60"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","article-title":"Balanced allocation and dictionaries with tightly packed constant size bins","volume":"380","author":"Dietzfelbinger","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"2156","DOI":"10.1137\/100797503","article-title":"On the Insertion Time of Cuckoo Hashing","volume":"42","author":"Fountoulakis","year":"2013","journal-title":"SIAM J. Comput."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1002\/rsa.20427","article-title":"Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hash Tables","volume":"41","author":"Frieze","year":"2012","journal-title":"Random Struct. Algorithms"},{"key":"ref_61","unstructured":"Walzer, S. (2018, January 9\u201313). Load thresholds for cuckoo hashing with overlapping blocks. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/090770928","article-title":"An analysis of random-walk cuckoo hashing","volume":"40","author":"Frieze","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_63","unstructured":"Pagh, R. (1999). Algorithms and Data Structures, Proceedings of the 6th International Workshop, WADS\u201999, Vancouver, BC, Canada, 11\u201314 August 1999, Springer. LNCS 1663."},{"key":"ref_64","doi-asserted-by":"crossref","unstructured":"Pagh, R. (2001, January 6\u20138). On the cell probe complexity of membership and perfect hashing. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), Crete, Greece.","DOI":"10.1145\/380752.380836"},{"key":"ref_65","unstructured":"Dietzfelbinger, M., and auf der Heide, F.M. (1992). Data Structures and Efficient Algorithms, Springer. LNCS 594."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a sparse table with O(1) worst case access time","volume":"31","author":"Fredman","year":"1984","journal-title":"J. ACM"},{"key":"ref_67","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1137\/S0097539791194094","article-title":"Dynamic perfect hashing: Upper and lower bounds","volume":"23","author":"Dietzfelbinger","year":"1994","journal-title":"SIAM J. Comput."},{"key":"ref_68","unstructured":"Dietzfelbinger, M., and auf der Heide, F.M. (1990). Automata, Languages and Programming, Proceedings of the 17th International Colloquium, Warwick University, UK, 16\u201320 July 1990, Springer. LNCS 443."},{"key":"ref_69","unstructured":"Broder, A.Z., and Karlin, A. (2020, January 5\u20138). Multilevel adaptive hashing. Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, UT, USA."},{"key":"ref_70","unstructured":"Dietzfelbinger, M., Gil, J., Matias, Y., and Pippenger, N. (1992). Automata, Languages and Programming, Proceedings of the 19th International Colloquium, Wien, Austria, 13\u201317 July 1992, Springer. LNCS 623."},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Johnson, N.L., and Kotz, S. (1977). Urn Models and Their Application: An Approach to Modern Discrete Probability Theory, John Wiley.","DOI":"10.2307\/2530628"},{"key":"ref_72","unstructured":"Kolchin, V.F., Sevast\u2019yanov, B.A., and Chistyakov, V.P. (1978). Random Allocations, V. H. Winston & Sons."},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(85)90015-X","article-title":"The expected length of the longest probe sequence for bucket searching when the distribution is not uniform","volume":"6","author":"Devroye","year":"1985","journal-title":"J. Algorithms"},{"key":"ref_74","unstructured":"Raab, M., and Steger, A. (1998). Randomization and Approximation Techniques in Computer Science, Second International Workshop, RANDOM\u201998, Barcelona, Spain, 8\u201310 October 1998, Springer. LNCS 1518."},{"key":"ref_75","unstructured":"Mitzenmacher, M.D. (1996). The Power of Two Choices in Randomized Load Balancing. [Ph.D. Thesis, Computer Science Department, University of California at Berkeley]."},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF01940878","article-title":"Efficient PRAM simulation on a distributed memory machine","volume":"16","author":"Karp","year":"1996","journal-title":"Algorithmica"},{"key":"ref_77","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1109\/TSE.1986.6312961","article-title":"Adaptive load sharing in homogeneous distributed systems","volume":"12","author":"Eager","year":"1986","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_78","unstructured":"V\u00f6cking, B. (2001, January 27). Symmetric vs. asymmetric multiple-choice algorithms. Proceedings of the 2nd ARACNE Workshop, Aarhus, Denmark."},{"key":"ref_79","doi-asserted-by":"crossref","unstructured":"Adler, M., Berenbrink, P., and Schroeder, K. (1998, January 24\u201326). Analyzing an infinite parallel job allocation process. Proceedings of the 6th European Symposium on Algorithms, Venice, Italy.","DOI":"10.1007\/3-540-68530-8_35"},{"key":"ref_80","unstructured":"Adler, M., Chakrabarti, S., Mitzenmacher, M., and Rasmussen, L. (June, January 29). Parallel randomized load balancing. Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), Las Vegas, NV, USA."},{"key":"ref_81","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1002\/rsa.1011","article-title":"Randomized Allocation Processes","volume":"18","author":"Czumaj","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"ref_82","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Czumaj, A., Friedetzky, T., and Vvedenskaya, N.D. (2000, January 9\u201313). Infinite parallel job allocations. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Bar Harbor, ME, USA.","DOI":"10.1145\/341800.341813"},{"key":"ref_83","doi-asserted-by":"crossref","unstructured":"Stemann, V. (1996, January 24\u201326). Parallel balanced allocations. Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Padua, Italy.","DOI":"10.1145\/237502.237565"},{"key":"ref_84","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1017\/S0963548399003946","article-title":"Studying balanced allocations with differential equations","volume":"8","author":"Mitzenmacher","year":"1999","journal-title":"Comb. Probab. Comput."},{"key":"ref_85","doi-asserted-by":"crossref","unstructured":"Pardalos, P., Rajasekaran, S., and Rolim, J. (2000). Handbook of Randomized Computing, Kluwer Press.","DOI":"10.1007\/978-1-4615-0013-1"},{"key":"ref_86","unstructured":"Broder, A., and Mitzenmacher, M. (2000). Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), Department of Computer Science, Harvard University. Full Version Available as Technical Report TR\u201303\u201300."},{"key":"ref_87","unstructured":"Mitzenmacher, M., and V\u00f6cking, B. (1998, January 22\u201323). The asymptotics of Selecting the shortest of two, improved. Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA."},{"key":"ref_88","unstructured":"Wu, J., and Kobbelt, L. (2002, January 20\u201322). Fast mesh decimation by multiple-choice techniques. Proceedings of the Vision, Modeling, and Visualization, Erlangen, Germany."},{"key":"ref_89","unstructured":"Siegel, A. (November, January 30). On universal classes of extremely random constant time hash functions and their time-space tradeoff. Technical Report TR1995-684, Computer Science Department, New York University, 1995. A previous version appeared under the title \u201cOn universal classes of fast high performance hash functions, their time-space tradeoff and their applications\u201d. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Triangle Park, NC, USA."},{"key":"ref_90","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0304-3975(96)00032-1","article-title":"Exploiting storage redundancy to speed up randomized shared memory simulations","volume":"162","author":"Scheideler","year":"1996","journal-title":"Theor. Comput. Sci."},{"key":"ref_91","unstructured":"Schickinger, T., and Steger, A. (2000). SOFSEM 2000: Theory and Practice of Informatics, Proceedings of the 27th Annual Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, 25 November\u20132 December 2000, Springer. LNCS 1963."},{"key":"ref_92","doi-asserted-by":"crossref","unstructured":"Cole, R., Maggs, B.M., auf der Heide, F.M., Mitzenmacher, M., Richa, A.W., Schroeder, K., Sitaraman, R.K., and Voecking, B. (1998, January 4\u20136). Randomized protocols for low-congestion circuit routing in multistage interconnection networks. Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), El Paso, TX, USA.","DOI":"10.1145\/276698.276790"},{"key":"ref_93","unstructured":"Cole, R., Frieze, A., Maggs, B.M., Mitzenmacher, M., Richa, A.W., Sitaraman, R.K., and Upfal, E. (1998). Randomization and Approximation Techniques in Computer Science, Proceedings of the 2nd International Workshop, RANDOM\u201998, Barcelona, Spain, 8\u201310 October 1998, Springer. LNCS 1518."},{"key":"ref_94","doi-asserted-by":"crossref","unstructured":"Swain, S.N., and Subudhi, A. (2022, January 10\u201314). A novel RACH scheme for efficient access in 5G and Beyond betworks using hash function. Proceedings of the 2022 IEEE Future Networks World Forum (FNWF), Montreal, QC, Canada.","DOI":"10.1109\/FNWF55208.2022.00022"},{"key":"ref_95","doi-asserted-by":"crossref","first-page":"3548","DOI":"10.1109\/JSAC.2023.3310094","article-title":"TFL-DT: A trust evaluation scheme for federated learning in digital twin for mobile networks","volume":"41","author":"Guo","year":"2023","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_96","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF02883985","article-title":"Some inequalities relating to the partial sum of binomial probabilities","volume":"10","author":"Okamoto","year":"1958","journal-title":"Ann. Math. Stat."},{"key":"ref_97","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","article-title":"Balls and bins: A study in negative dependence","volume":"13","author":"Dubhashi","year":"1998","journal-title":"Random Struct. Algorithms"},{"key":"ref_98","doi-asserted-by":"crossref","first-page":"1466","DOI":"10.1214\/aoms\/1177698701","article-title":"Association of random variables, with applications","volume":"38","author":"Esary","year":"1967","journal-title":"Ann. Math. Stat."},{"key":"ref_99","first-page":"286","article-title":"Negative association of random variables, with applications","volume":"11","author":"Proschan","year":"1983","journal-title":"Ann. Stat."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/11\/500\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:13:20Z","timestamp":1760130800000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/11\/500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,28]]},"references-count":99,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2023,11]]}},"alternative-id":["a16110500"],"URL":"https:\/\/doi.org\/10.3390\/a16110500","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2023,10,28]]}}}