Balanced Allocation Through Random Walk

2017/08/16 by Frieze, Alan, Petti, Samantha · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1708.04945

Abstract

We consider the allocation problem in which m ≤ (1-ε) dn items are to be allocated to n bins with capacity d. The items x₁,x₂,…,x_m arrive sequentially and when item x_i arrives it is given two possible bin locations p_i=h₁(x_i),q_i=h₂(x_i) via hash functions h₁,h₂. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided ε= Ω(√( ( log d)/(d)) ).

Cited by

• Fast Insertion for Bucketized Cuckoo Hashing

Related

• Balanced Allocation on Graphs: A Random Walk Approach
• Balanced Allocation on Graphs
• Balanced Allocation with Random Walk Based Sampling
• Perfectly Balanced Allocation With Estimated Average Using Expected Constant Retries
• Unbalanced Allocations