Afficher la notice abrégée

On Power-Law Distributed Balls in Bins and its Applications to View Size Estimation

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorATSONIOS, Ioannis
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorHANUSSE, Nicolas
hal.structure.identifierMachine Learning and Optimisation [TAO]
hal.structure.identifierLaboratoire de Recherche en Informatique [LRI]
dc.contributor.authorKIM, Yusik
dc.date.accessioned2024-04-15T09:46:59Z
dc.date.available2024-04-15T09:46:59Z
dc.date.created2011
dc.date.issued2011-12
dc.date.conference2011-12
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198055
dc.description.abstractEnThe 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$.
dc.language.isoen
dc.subject.enPower Law
dc.subject.enView Size Estimation
dc.subject.enBalls into Bins
dc.title.enOn Power-Law Distributed Balls in Bins and its Applications to View Size Estimation
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleISAAC
bordeaux.countryJP
bordeaux.conference.cityYokohama
bordeaux.peerReviewedoui
hal.identifierinria-00618785
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00618785v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2011-12&rft.au=ATSONIOS,%20Ioannis&BEAUMONT,%20Olivier&HANUSSE,%20Nicolas&KIM,%20Yusik&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée