Balanced allocation through random walk

DOI10.1016/J.IPL.2017.11.010MaRDI QIDQ1685024zbMATH OpenOpenAlexFDO

Authors Samantha Petti, Alan Frieze

Publication date 13 December 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.04945

zbMATH Keywords

random walkonline algorithmscuckoo hashingbalanced allocation

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Sums of independent random variables; random walks (60G50)

Abstract: We consider the allocation problem in which $mleq(1-epsilon)dn$ items are to be allocated to $n$ bins with capacity $d$. The items $x_1,x_2,ldots,x_m$ arrive sequentially and when item $x_i$ arrives it is given two possible bin locations $p_i=h_1(x_i),q_i=h_2(x_i)$ via hash functions $h_1,h_2$. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided $epsilon=Omegaleft(sqrtfraclogddight).$

Recommendations

• Balanced Allocations
• Automata, Languages and Programming
• Balanced allocations (extended abstract)

Cites work

• An analysis of random-walk cuckoo hashing
• Balanced allocation and dictionaries with tightly packed constant size bins
• Cuckoo hashing
• On the insertion time of cuckoo hashing
• On the insertion time of random walk cuckoo hashing
• Space efficient hash tables with worst case constant access time
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The random graph threshold for \(k\)-orientiability and a fast algorithm for optimal multiple-choice allocation

Cited in

(3)

• Balanced allocation and dictionaries with tightly packed constant size bins
• Automata, Languages and Programming
• Derandomized Balanced Allocation

This page was built for publication: Balanced allocation through random walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1685024)