2018/10/05 by Dengwang Tang, Vijay Subramanian, Tang, Dengwang +1
Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1810.02722
openalex publication_date 2018/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the standard ball-in-bins experiment, a well-known scheme is to sample d bins independently and uniformly at random and put the ball into the least loaded bin. It can be shown that this scheme yields a maximum load of loglog n/log d+O(1) with high probability. Subsequent work analyzed the model when at each time, d bins are sampled through some correlated or non-uniform way. However, the case when the sampling for different balls are correlated are rarely investigated. In this paper we propose three schemes for the ball-in-bins allocation problem. We assume that there is an underlying k-regular graph connecting the bins. The three schemes are variants of power-of-d choices, except that the sampling of d bins at each time are based on the locations of d independently moving non-backtracking random walkers, with the positions of the random walkers being reset when certain events occurs. We show that under some conditions for the underlying graph that can be summarized as the graph having large enough girth, all three schemes can perform as well as power-of-d, so that the maximum load is bounded by loglog n/log d+O(1) with high probability.