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

Татьяна Юрьевна Лымарь, Татьяна Сергеевна Мантрова, Наталья Юрьевна Староверова

Аннотация


Статья посвящена вопросам разработки алгоритмов фрактального анализа реляционных баз данных. Дается обзор и сравнительный анализ известных приложений теории фракталов к обработке данных. Предложен новый алгоритм фрактального поиска в реляционной базе данных, позволяющий обнаруживать повторяющиеся группы данных. Приведена общая схема алгоритма. Рассмотрена реализация для СУБД Oracle. Представлена реализация с использованием модели распределенных вычислений MapReduce. Приводятся примеры использования разработанного алгоритма для сжатия и анализа содержимого базы данных

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


реляционные базы данных, теория фракталов, фрактальный анализ баз данных, сжатие данных

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

PDF

Литература


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 с.




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