Multidimensional balanced allocations

ABSTRACT

We consider a multidimensional variant of the balls-and-bins problem, where balls correspond to random D-dimensional 0-1 vectors. This variant is motivated by a problem in load balancing documents for distributed search engines. We demonstrate the utility of the power of two choices in this domain.

REFERENCES

• 1: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced Allocations, SIAM Journal on Computing, v.29 n.1, p.180-200, Feb. 2000 [doi>10.1137/S0097539795288490]
• 2: Andrei Z. Broder , David Carmel , Michael Herscovici , Aya Soffer , Jason Zien, Efficient query evaluation using a two-level retrieval process, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956944]
• 3: Andrei Broder , Michael Mitzenmacher, Optimal plans for aggregation, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571852]
• 4: Mitzenmacher, M., Richa, A., and Sitaraman, R. The Power of Two Choices: A Survey of Techniques and Results. In Handbook of Randomized Computing, edited by P. Pardalos, S. Rajasekaran, J. Reif, and J. Rolim. Kluwer Academic Publishers, Norwell, MA, 2001, pp. 255--312.