Алгоритм репрезентативного сэмплинга для систем баз данных на основе фрагментного параллелизма

Дмитрий Дмитриевич Янцен, Михаил Леонидович Цымблер, Владимир Юльевич Гудков

Аннотация


Сэмплинг является популярным подходом к обработке сверхбольших баз данных в широком спектре приложений, связанных с интеллектуальным анализом данных, построениемгистограмм, приблизительное исполнение запросов и др. Использование сэмпла вместо оригинальной базы данных может уменьшить точность результатов, но компенсируется сокращением времени выполнения обработки. Репрезентативный сэмплинг позволяет сохранить в сэмпле определенные характеристики базы данных. Однако существующие алгоритмы репрезентативного сэмплинга не могут быть применены для параллельных систем баз данных, поскольку не учитывают характеристики данных, распределяемых по вычислительным узламкластерной системы. В данной статье предлагается алгоритм репрезентативного сэмплингадля параллельных реляционных систем баз данных на основе фрагментного параллелизма.Приведены результаты вычислительных экспериментов над предложенным алгоритмом, показавшие адекватное сохранение репрезентативности свойств базы данных, распределенной поузлам кластерной системы.


Ключевые слова


реляционные базы данных, параллельные системы баз данных, репрезентативный сэмплинг

Полный текст:

PDF

Литература


Костенецкий, П.С. Технологии параллельных систем баз данных для иерархических многопроцессорных сред. / П.С. Костенецкий, А.В. Лепихов, Л.Б. Соколинский // Автоматика и телемеханика. — 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