Optimal ball recycling

Michael A. Bender, Jake Christensen, Alex Conway, Martin Farach-Colton, Rob Johnson, Meng-Tsung Tsai

Research output: Contribution to conferencePaper

2 Scopus citations

Abstract

Balls-and-bins games have been a successful tool for modeling load balancing problems. In this paper, we study a new scenario, which we call the ball-recycling game, defined as follows: Throw m balls into n bins i.i.d. according to a given probability distribution p. Then, at each time step, pick a non-empty bin and recycle its balls: take the balls from the selected bin and re-throw them according to p. This balls-and-bins game closely models memory-access heuristics in databases. The goal is to have a bin-picking method that maximizes the recycling rate, defined to be the expected number of balls recycled per step in the stationary distribution. We study two natural strategies for ball recycling: Fullest Bin, which greedily picks the bin with the maximum number of balls, and Random Ball, which picks a ball at random and recycles its bin. We show that for general p, Random Ball is Θ(1)-optimal, whereas Fullest Bin can be pessimal. However, when p = u, the uniform distribution, Fullest Bin is optimal to within an additive constant.

Original languageEnglish
Pages2527-2546
Number of pages20
DOIs
StatePublished - 1 Jan 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: 6 Jan 20199 Jan 2019

Conference

Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
CountryUnited States
CitySan Diego
Period6/01/199/01/19

Fingerprint Dive into the research topics of 'Optimal ball recycling'. Together they form a unique fingerprint.

  • Cite this

    Bender, M. A., Christensen, J., Conway, A., Farach-Colton, M., Johnson, R., & Tsai, M-T. (2019). Optimal ball recycling. 2527-2546. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States. https://doi.org/10.1137/1.9781611975482.155