Szacowanie selektywności zapytań oparte na transformacie Hougha i metodzie PCA

• Autorzy: Augustyn D. , Kostrzewa D.

Warianty tytułu

EN

Query selectivity estimation based on Hough transform and PCA method

• Języki publikacji: PL

Abstrakty

PL

Oszacowanie selektywności zapytania jest istotnym elementem procesu uzyskiwania optymalnego planu wykonania tego zapytania. Wyznaczenie selektywności wymaga użycia nieparametrycznego estymatora rozkładu wartości atrybutu, na ogół histogramu. Wykorzystanie wielowymiarowego histogramu jako reprezentacji łącznego rozkładu wielowymiarowego jest nieekonomiczne z powodu zajętości pamięciowej takiej reprezentacji. W artykule zaproponowano nową metodę, nazwaną HPCA, oszczędną pod względem zajętości, gdzie rozkład dwuwymiarowy w przybliżeniu może być reprezentowany w postaci zbioru histogramów jednowymiarowych. Metoda HPCA opiera się na transformacji Hougha i metodzie analizy składowych głównych. Dzięki HPCA można uzyskiwać dokładniejsze oszacowania selektywności zapytań niż te, otrzymane przy wykorzystaniu standardowych 2-wymiarowych histogramów.

EN

Query selectivity estimation is an important element of obtaining optimal query execution plan. Selectivity estimation requires a nonparametric estimator of attribute values distribution – commonly a histogram. Using a multidimensional histogram as a representation of a joint multidimensional distribution of attributes values is not space-efficient. The paper introduces a new space-efficient method called HPCA, where a 2-dimesional distribution may be represented by a set of 1-dimensional histograms. HPCA is based on Hough transform and principal component analysis method. Using HPCA commonly gives more accurate selectivity estimation than standard methods based on a 2-dimensional histogram.

Słowa kluczowe

PL

optymalizacja zadań; selektywność zapytań; histogram; transformacja Hougha; redukcja wymiarowości; PCA

EN

query optimization; selectivity estimation; histograms; Hough transform; dimensionality reduction; PCA

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2012
• Tom: Vol. 33, nr 2A
• Strony: 211--227
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Augustyn D.

autor

Kostrzewa D.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska,

Bibliografia

• 1. Possala V., Ioannidis Y. E.: Selectivity Estimation without the Attribute Value Independence Assumption. Proc. of the 23rd Int. Conf. on Very Large Databases, The VLDB Journal, Athens 1997.
• 2. Gunopulos D., Kollios G., Tsotras V. J.: Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes. ACM SIGMOD 2000, Dallas 2000.
• 3. Lee J., Deok-Hwan K., Chin-Wan Ch.: Multi-dimensional Selectivity Estimation Using Compressed Histogram Estimation Information. Proc. of ACM SIGMOD Int. Conf. on Management of Data. ACM, Philadelphia 1999.
• 4. Chakrabarti K., Garofalakis M., Rastogi R., Shim K.: Approximate Query Processing Using Wavelets. VLDB Journal, Vol. 10, No. 2-3, Springer-Verlag, New York 2001.
• 5. Getoor L., Taskar B., Koller D.: Selectivity estimation using probabilistic modes. Proc. of ACM SIGMOD Int. Conf. on Management of Data. ACM, New York 2001.
• 6. Augustyn D. R.: Applying advanced methods of query selectivity estimation in Oracle DBMS. Advances in Soft Computing. Man-Machine Interactions. Springer-Verlag, Berlin - Heidelberg 2009, s. 585-593.
• 7. Augustyn D. R.: Zastosowanie sieci Bayesa w szacowaniu selektywności zapytań w optymalizatorze zapytań serwera bazy danych Oracle. Studia Informatica, Vol. 32, No. 1A (94), Wydawnictwo Politechniki Śląskiej, Gliwice 2011, s. 25-42.
• 8. Oracle 10g. Using extensible optimizer (2010), http://download.oracle.com/docs/ cd/B14117 01/appdev.l01/bl0800/dciextopt.htm.
• 9. Oracle® Database SQL Reference. Analyze (2011), http://download.oracle.com/docs/ cd/B19306_01/server.102/b14200/statements_4005 .htm.
• 10. Augustyn D. R.: Metoda analizy głównych składowych w szacowaniu selektywności zapytań. Studia Informatica, Vol. 32, No. 2A(96), Wydawnictwo Politechniki Śląskiej, Gliwice2011,s.21-36.
• 11. Döller M.: The MPEG-7 Multimedia DataBase System (MPEG-7 MMDB). Dissertation: 117-125 University Klagenfurt, Austria 2004.
• 12. Hough P. V. C.: Method and means for recognizing complex patterns. United States Patent Office, U.S. Patent 3,069,654, 1962.
• 13. Xu L., Oja E.: Randomized Hough Transform (RHT): Basic Mechanisms, Algorithms, and Computational Complexities. CVGIP: Image Understanding, Vol. 57, No. 2, 1993, s. 131-154.
• 14. Ballard D. H.: Generalizing the Hough Transform to Detect Arbitrary Shapes. IEEE Pattern Recognition, Vol. 13, No. 2, Great Britain 1981, s. 111-122.
• 15. Hinds S. C., Fisher J. L., D'Amato D. P.: A Document Skew Detection Method Using Run-Length Encoding and the Hough Transform. Proceedings of 10th International Conference on Pattern Recognition (ICPR), Atlantic City, NJ, USA 1990, s. 464-468.
• 16. Chmielewski L.: Nakładanie obrazów metodą transformaty Hougha. Prace XIII Krajowej Konferencji Biocybernetyka i Inżynieria Biomedyczna KBIB 2003, t. 2, Gdańsk 2003, s. 830-835.
• 17. Illingworth J., Kittler J.: A Survey of the Hough Transform. Computer Vision, Graphics, and Image Processing, Vol. 44, Elsevier 1988, s. 87-116.
• 18. Tukey J.: Exploratory Data Analysis. Addison-Wesley Menlo Park, CA, USA 1977.
• 19. Jolliffe I. T.: Principal Component Analysis, Second Edition. Springer-Verlag, New York - Berlin - Heidelberg 2002.
• 20. Hough transform - MATLAB (2012), http://www.mathworks.conVhelp/toolbox/ images/ref7hough.html.
• 21. Identify peaks in Hough transform - MATLAB (2012), http://www.mathworks.com/ help/toolbox/images/ref/houghpeaks.html.
• 22. 2-D median filtering - MATLAB (2012), http://www.mathworks.com/help/ toolbox/images/ref/medfilt2.html.
• 23. Principal component analysis (PCA) on data - MATLAB (2012), http://www.math-works.com/help/toolbox/stats/princomp.html.
• 24. k-means clustering (2012), http://en.wikipedia.org/wiki/K-means_clustering.