Fractal search algorithm in relational databases
DOI:
https://doi.org/10.14529/cmse140404Keywords:
relational databases, the theory of fractals, fractal analysis of databases, data compressionAbstract
The article deals with the development of algorithms of fractal analysis of relational databases. An overview and comparative analysis of the known applications of the theory of fractals in data processing is provided. A new algorithm of fractal search in a relational database, which allows detecting duplicate data group, is presented. Implementation of the proposed algorithm for the Oracle DBMS is considered. An implementation using distributed computing MapReduce paradigm is described. Examples of using the developed algorithm to compress and analyze the contents of the database are presented. The results of computational experiments are given.
References
Adibi, J. Fractals and Self-similarity in Data Mining: Issue and Approaches — KDD-2002 Workshop Report. — 2002. / J. Adibi, C. Faloutsos. URL: http://www.sigkdd.org/ sites/default/files/issues/4-2-2002-12/adibi.pdf (дата обращения: 1.08.2014).
Barbara D. Fractal Mining — Self Similarity-based Clustering and its Applications // Data Mining and Knowledge Discovery Handbook. — Springer. — 2010. — P. 573–589. 3. Ferreira Cordeiro, R.L. Clustering very large multi-dimensional datasets with MapReduce / R.L. Ferreira Cordeiro, C. Traina Jr, A.J. Traina, J. López, U. Kang, C. Faloutsos // Proceedings of the 17th International Conference on Knowledge Discovery and Data Mining (KDD '11). — 2011. — P. 690–698.
Lämmel, R. Google’s MapReduce programming model / R. Lämmel // Science of computer programming. — 2008. — 70(1). — P. 1–30.
Peres, S.M. A fractal fuzzy approach to clustering tendency analysis / S.M. Peres, M. L. de Andrade Netto // Advances in Artificial Intelligence–SBIA 2004. – Springer Berlin Heidelberg. — 2004. — P. 395–404.
Sousa, E. A fast and effective method to find correlations among attributes in databases / E. Sousa, C. Traina, A. Traina // Data Mining and Knowledge Discovery. — 2007. — 14(3). — P. 367–407.
Stonebraker, M. MapReduce and parallel DBMSs: friends or foes? / M. Stonebraker // Communications of the ACM. — 2010. — P. 64–71.
Traina Jr, C. Fast feature selection using fractal dimension/ C. Traina Jr, A. Traina, L. Wu, C. Faloutsos // Journal of Information and Data Management. — 2010. —Vol. 1, No. 1. — P. 3–16.
White, T. Hadoop: The definitive guide. / T. White — O'Reilly Media/Yahoo Press — 2012. — 688 p.
Yan, G. The practical method of fractal dimensionality reduction based on Z-ordering technique / G. Yan, Z. Li, L. Yuan // Advanced Data Mining and Applications. — 2006. — P. 542–549.
Zmeškal, O. Fractal analysis of image structures. / O. Zmeškal, M. Veselý, M. Nežádal, M. Buchníček // Harmonic and Fractal Image Analysis. — 2001. — P. 3–5.
Дейт, К.Дж. Введение в системы баз данных, 8-е издание. / К.Дж. Дейт — М.: Издательский дом «Вильямс», 2006. — 1328 с.
Кайт, Т. Oracle для профессионалов. Архитектура, методики программирования и основные особенности версий 9i, 10g и 11g. / Т. Кайт — М.: Издательский дом «Вильямс», 2013. — 848 с.
Лымарь, Т.Ю. Фрактальный поиск в базе данных с применением модели распределен ных вычислений / Т.Ю. Лымарь, Т.С. Мантрова // Параллельные вычислительные технологии (ПаВТ'2014): Труды международной научной конференции (1–3 апреля 2014 г., г. Ростов-на-Дону). — Челябинск: Издательский центр ЮУрГУ, 2014. — С. 369.
Лымарь, Т.Ю. Параллельный алгоритм фрактального поиска в базе данных / Т.Ю. Лымарь, Н.Ю. Староверова // Параллельные вычислительные технологии (ПаВТ’2011): Труды международной научной конференции (Москва, 28 марта – 1 апреля 2011 г.). — Челябинск: Издательский центр ЮУрГУ, 2011. — С. 703.
Мандельброт, Б. Фрактальная геометрия природы. / Б. Мандельброт — Москва: Институт компьютерных исследований, 2002. — 656 с.
Официальный Портал Росреестра. URL: http://rosreestr.ru (дата обращения: 07.05.2014).
Официальный сайт ФГУП ФКЦ «Земля». URL: http://www.fccland.ru (дата обращения: 07.05.2014).
Уэлстид, С. Фракталы и вейвлеты для сжатия изображений в действии. / С. Уэлстид — М.: Издательство Триумф, 2003. — 320 с.
