|
|
|
@inproceedings{DBLP:conf/vldb/FaloutsosMS96,
author = {Christos Faloutsos and
Yossi Matias and
Abraham Silberschatz},
editor = {T. M. Vijayaraman and
Alejandro P. Buchmann and
C. Mohan and
Nandlal L. Sarda},
title = {Modeling Skewed Distribution Using Multifractals and the `80-20'
Law},
booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
publisher = {Morgan Kaufmann},
year = {1996},
isbn = {1-55860-382-4},
pages = {307-317},
ee = {db/conf/vldb/FaloutsosMS96.html},
crossref = {DBLP:conf/vldb/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
The focus of this paper is on the characterization of the skewness of an attribute-value distribution and on the extrapolations for interesting parameters. More specifically, given a vector with the highest h multiplicities mvec = (m1, m2, ..., mh), and some frequency moments Fq =\sum miq , (e.g., q=0, 2), we provide effective schemes for obtaining estimates about either its statistics or subsets/supersets of the relation.
We assume an 80/20 law, and specifically, a p/(1-p) law. This law gives a distribution which is commonly known in the fractals literature as `multifractal'. We show how to estimate p from the given information (first few multiplicities and a few moments), and present the results of our experimentations on real data. Our results demonstrate that schemes based on our multifractal assumption consistently outperforms those schemes based on the uniformity assumption, which are commonly used in current DBMSs. Moreover, our schemes can be used to provide estimates for supersets of a relation, which the uniformity assumption based schemes can not not provide at all.
Copyright © 1996 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
