ABHK11
Summary
Atsonios, Ioannis, Beaumont, Olivier, Hanusse, Nicolas and Kim, Yusik (2011) On Power-Law Distributed Balls in Bins and its Applications to View Size Estimation. In 22nd International Symposium on Algorithms and Computation (ISAAC). Yokohama, Japon, dec. Springer, pages 504-513. ((URL)) (PDF)
Abstract
The view size estimation plays an important role in query optimization. It has been observed that many data follow a power law distribution. In this paper, we consider the balls in bins problem where we place balls into {$N$} bins when the bin selection probabilities follow a power law distribution. As a generalization to the coupon collector's problem, we address the problem of determining the expected number of balls that need to be thrown in order to have at least one ball in each of the {$N$} bins. We prove that {$\Theta(\frac{N^\alpha \ln N}{c\_N^{\alpha}})$} balls are needed to achieve this where {$\alpha$} is the parameter of the power law distribution and {$c\_N^{\alpha}=\frac{\alpha-1}{\alpha-N^{\alpha-1}}$} for {$\alpha \neq 1$} and {$c\_N^{\alpha}=\frac{1}{\ln N}$} for {$\alpha=1$}. Next, when fixing the number of balls that are thrown to {$T$}, we provide closed form upper and lower bounds on the expected number of bins that have at least one occupant. For {$n$} large and {$\alpha>1$}, we prove that our bounds are tight up to a constant factor of {$\left(\frac{\alpha}{\alpha-1}\right)^{1-\frac{1}{\alpha}} \leq e^{1/e} \simeq 1.4$}.
Bibtex entry
@INPROCEEDINGS { ABHK11,
TITLE = { {On Power-Law Distributed Balls in Bins and its Applications to View Size Estimation} },
AUTHOR = { Atsonios, Ioannis and Beaumont, Olivier and Hanusse, Nicolas and Kim, Yusik },
ABSTRACT = { The view size estimation plays an important role in query optimization. It has been observed that many data follow a power law distribution. In this paper, we consider the balls in bins problem where we place balls into {$N$} bins when the bin selection probabilities follow a power law distribution. As a generalization to the coupon collector's problem, we address the problem of determining the expected number of balls that need to be thrown in order to have at least one ball in each of the {$N$} bins. We prove that {$\Theta(\frac{N^\alpha \ln N}{c\_N^{\alpha}})$} balls are needed to achieve this where {$\alpha$} is the parameter of the power law distribution and {$c\_N^{\alpha}=\frac{\alpha-1}{\alpha-N^{\alpha-1}}$} for {$\alpha \neq 1$} and {$c\_N^{\alpha}=\frac{1}{\ln N}$} for {$\alpha=1$}. Next, when fixing the number of balls that are thrown to {$T$}, we provide closed form upper and lower bounds on the expected number of bins that have at least one occupant. For {$n$} large and {$\alpha>1$}, we prove that our bounds are tight up to a constant factor of {$\left(\frac{\alpha}{\alpha-1}\right)^{1-\frac{1}{\alpha}} \leq e^{1/e} \simeq 1.4$}. },
KEYWORDS = { Power Law; View Size Estimation; Balls into Bins },
BOOKTITLE = { 22nd International Symposium on Algorithms and Computation (ISAAC) },
ADDRESS = { Yokohama, Japon },
AUDIENCE = { internationale },
PAGES = { 504-513 },
URL = { http://dx.doi.org/10.1007/978-3-642-25591-5_52 },
YEAR = { 2011 },
MONTH = { dec },
PUBLISHER = { Springer },
SERIES = { Lecture Notes in Computer Science },
VOLUME = { 7074 },
PDF = { http://hal.inria.fr/inria-00618785/PDF/isaac.pdf },
}