Balanced allocation and dictionaries with tightly packed constant size bins
| Autor: | Martin Dietzfelbinger, Christoph Weidling |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Random graph
Data structures General Computer Science Randomized algorithms Hash function Random function Storage space Bin Theoretical Computer Science Combinatorics Cuckoo hashing Balanced allocation Dictionaries Hashing Ball (bearing) Probability distribution Constant (mathematics) Random graphs Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 380(1-2):47-68 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2007.02.054 |
| Popis: | We study a particular aspect of the balanced allocation paradigm (also known as the “two-choices paradigm”): constant sized bins, packed as tightly as possible. Let d≥1 be fixed, and assume there are m bins of capacity d each. To each of n≤dm balls two possible bins are assigned at random. How close can dm/n=1+ε be to 1 so that with high probability each ball can be put into one of the two bins assigned to it without any bin overflowing? We show that ε>(2/e)d−1 is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for ε>βd, for some constant β |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect