@ARTICLE{Augustyn_Dariusz_R._Asymptotically_2012,
 author={Augustyn, Dariusz R.},
 volume={vol. 24},
 number={No 1},
 journal={Theoretical and Applied Informatics},
 pages={3-22},
 howpublished={online},
 year={2012},
 publisher={Committee of Informatics of Polish Academy of Science},
 publisher={Institute of Theoretical and Applied Informatics of Polish Academy of Science},
 abstract={The problem of query selectivity estimation for database queries is critical for efficientquery execution by database management systems. A query execution method strongly depends on earlyestimated size of a query result. This estimation determines a data access method used later during thequery execution. The selectivity parameter is a fraction of table rows that satisfy a single-table querycondition. For a selection condition of a range query where an attribute has a continuous domain, theselectivity is equivalent to a definite integral form probability density function (PDF) of attribute valuesdistribution. For a compound selection condition based on many attributes we need a multidimensionalspace-efficient non-parametric estimator of multivariate PDF of attribute values distribution. A knownapproach based on Discrete Cosine Transform (DCT) spectrum as an representation of multidimensionalPDF is considered. The energy compaction property of DCT lets omit a region of spectrum coefficientswith small absolute values without significant losing an accuracy of selectivity estimation. An area ofrelevant spectrum coefficients is called a sampling zone. Results of experiments from previous worksshows that applying the reciprocal shape of the sampling zone gives the least selectivity estimation errorsubject to a predetermined size of the zone. The main result of this work is a theoretical confirmation of onlyexperimental results from previous works. The paper presents the proof of the theorem that the reciprocalshape of the sampling zone is asymptotically error-optimal. The proof is based on calculus of variationsand the isoperimetric problem.},
 type={Artykuły / Articles},
 title={Asymptotically error-optimal shape of sampling zone for query selectivity estimation method based on discrete cosine transform},
 URL={http://journals.pan.pl/Content/93680/mainfile.pdf},
 keywords={query selectivity estimation, probability density function, discrete cosine transform, calculus of variations, isoperimetric problem},
}