Representative sampling algorithm for database systems based on the partitioned parallelism

Dmitry D. Yantsen, Mikhail L. Zymbler, Vladimir Yu. Gudkov

Abstract


Sampling is a popular approach to very large databases processing in a wide range of applications, e.g. data mining, histograms construction, query execution cost estimation, etc. Use of either the sample instead of the original database can reduce the accuracy of the results, but offset by a reduction of time executing processing. Representative sampling allows you to save the sample of certain characteristics of the database. However, existing algorithms for representative sampling can not be used for pas-parallel database systems because it does not take into account the characteristics of the data distribution fissionable by the compute nodes of the cluster system. In this paper we propose al-representative sampling algorithm for parallel relational database systems based on the slice of parallelism. The results of computational experiments on the proposed algorithm, showing adequate maintenance of representativity database properties distributed across the nodes of a cluster system. 


Keywords


relational databases, parallel database systems, representative sampling

References


Костенецкий, П.С. Технологии параллельных систем баз данных для иерархических многопроцессорных сред. / П.С. Костенецкий, А.В. Лепихов, Л.Б. Соколинский // Автоматика и телемеханика. — 2007. — № 5. — C. 112–125.

Пан, К.С. Разработка параллельной СУБД на основе последовательной СУБДPostgreSQL с открытым исходным кодом. / К.С. Пан, М.Л. Цымблер // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». — 2012.— № 18(277). — Вып. 12. — С. 112–120.

Соколинский, Л.Б. Обзор архитектур параллельных систем баз данных. / Л.Б. Соколинский // Программирование. — 2004. — № 6. — С. 49–63.

Янцен, Д.Д. Алгоритм репрезентативного сэмплинга для параллельных систем баз данных. / Д.Д. Янцен, М.Л. Цымблер // Параллельные вычислительные технологии (ПаВТ'2014): труды международной научной конференции (1–3 апреля 2014 г., г. Ростов-на-Дону). — Челябинск: Издательский центр ЮУрГУ, 2014. —С. 381.

Acharya, S. Join Synopses for Approximate Query Answering. / S. Acharya, P.B. Gibbons,V. Poosala, S. Ramaswamy // SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1–3, 1999, Philadelphia, Pennsylvania, USA. — ACM, 1999. — P. 275–286.

Agarwal, S. Blink and It's Done: Interactive Queries on Very Large Data. / S. Agarwal, A. Panda, B. Mozafari, A.P. Iyer, S. Madden, I. Stoica // Proceedings of the VLDB Endowment. — 2011. — Vol. 5, No. 1. — P. 1902–1905.

Bisbal, J. A Formal Framework for Database Sampling. / J. Bisbal, J. Grimson, D.A. Bell // Information & Software Technology. — 2005. — Vol. 47, No. 1. — P. 819–828.

Buda, T.S. Generation of Test Databases using Sampling Methods. / T.S. Buda // International Symposium on Software Testing and Analysis, ISSTA'13, Lugano, Switzerland, July 15–20, 2013. — ACM, 2013. — P. 366–369.

Buda, T.S. VFDS: Very Fast Database Sampling System. / T.S. Buda, T. Cerqueus, M. Kristiansen, J. Murphy // Proceedings of the IEEE 14th International Conference on Information Reuse & Integration, IRI 2013, San Francisco, CA, USA, August 14– 16, 2013. — IEEE, 2013. — P. 153–160.

Buda, T.S. CoDS: A Representative Sampling Method for Relational Databases. / T.S. Buda, T. Cerqueus, J. Murphy, M. Kristiansen // Database and Expert Systems Applications – 24th International Conference, DEXA 2013, Prague, Czech Republic, August 26–29, 2013. Proceedings, Part I. — Springer, 2013. Lecture Notes in Computer Science. — Vol. 8055. — P. 342–356.

Chakaravarthy, V.T. Analysis of Sampling Techniques for Association Rule Mining. / V.T. Chakaravarthy, V. Pandit, Y. Sabharwal // Database Theory – ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23–25, 2009, Proceedings. — ACM, 2009. — P. 276–283.

Chaudhuri, S. Effective Use of Block–Level Sampling in Statistics Estimation. / S. Chaudhuri, G. Das, U. Srivastava // Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13–18, 2004. — ACM, 2004. — P. 287–298.

Gemulla, R. Linked Bernoulli Synopses: Sampling along Foreign Keys. / R. Gemulla, P. Rösch, W. Lehner // Scientific and Statistical Database Management, 20th International Conference, SSDBM 2008, Hong Kong, China, July 9–11, 2008, Proceedings. — Springer, 2008. Lecture Notes in Computer Science. — P. 6–23.

Goethals, B. Mining Interesting Sets and Rules in Relational Databases. / B. Goethals, W.L. Page, M. Mampaey // Proceedings of the 2010 ACM Symposium on Applied Computing (SAC), Sierre, Switzerland, March 22–26, 2010. — ACM, 2010. — P. 997– 1001.

Gryz, J. Query Sampling in DB2 Universal Database. / J. Gryz, J. Guo, L. Liu, C. Zuzarte // Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13–18, 2004. — ACM, 2004. — P. 839–843.

Guide to the Financial Data Set of the PKDD'99 Discovery Challenge. — URL: http://lisp.vse.cz/pkdd99/Challenge/berka.htm (дата обращения: 24.05.2014).

Haas, P.J. A Bi-Level Bernoulli Scheme for Database Sampling. / P.J. Haas, C. Koenig // Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13–18, 2004. — ACM, 2004. — P. 275–286.

Ioannidis, Y.E. Histogram-Based Approximation of Set-Valued Query-Answer. / Y.E. Ioannidis, V. Poosala // VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7–10, 1999, Edinburgh, Scotland, UK. — Morgan Kaufmann 1999. — P. 174–185.

John, G.H. Static Versus Dynamic Sampling for Data Mining. / G.H. John, P. Langley // Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD–96), Portland, Oregon, USA. — AAAI Press, 1996. — P. 367–370.

Lakshmi, M.S. Effectiveness of Parallel Joins. / M.S. Lakshmi, P.S. Yu // IEEE Transactions on Knowledge and Data Engineering. — 1990. — Vol. 2, No. 4. —P. 410–424.

Olken, F. Random Sampling from Database Files: A Survey. / F. Olken, D. Rotem // Statistical and Scientific Database Management, 5th International Conference SSDBM, Charlotte, NC, USA, April 3–5, 1990, Proceedings. — Springer, 1990. Lecture Notes in Computer Science. — P. 92–111.

Oracle Database SQL Language Reference. — URL: http://docs.oracle.com/cd/E11882_01/server.112/e41084/statements_10002.htm (accessed: 24.05.2014).

Palmer, C.R. Density Biased Sampling: an Improved Method for Data mining and Clustering. / C.R. Palmer, C. Faloutsos // Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, May 16–18, 2000, Dallas, Texas, USA. — ACM, 2000. — P. 82–92.

Pan, C.S. Taming Elephants, or How to Embed Parallelism into PostgreSQL. / C.S. Pan, M.L. Zymbler // Database and Expert Systems Applications – 24th International Conference, DEXA 2013, Prague, Czech Republic, August 26–29, 2013. Proceedings, Part I. — Springer, 2013. Lecture Notes in Computer Science. — Vol. 8055. — P. 153– 164.

Parthasarathy, S. Efficient Progressive Sampling for Association Rules. / S. Parthasarathy // Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2002), 9–12 December 2002, Maebashi City, Japan. — IEEE, 2002. — P. 354– 361.

Wu, X. Privacy Preserving Database Generation for Database Application Testing. / X. Wu, Y. Wang, S. Guo, Y. Zheng // Fundamenta Informaticae. — 2007. — Vol. 78, No. 1. — P. 595–612.

Yin, X. Efficient Classification across Multiple Database Relations: A CrossMine Approach. / X. Yin, J. Han, J. Yang, P.S. Yu // IEEE Transactions on Knowledge and Data Engineering. — 2006. — Vol. 18, No. 1. — P. 770–783.




DOI: http://dx.doi.org/10.14529/cmse140402