Подход к разбиению сверхбольших графов с помощью параллельных СУБД

Константин Сергеевич Пан

Аннотация


Разбиение графов на подграфы представляет собой интересную задачу интеллек-туального анализа графов, которая находит свое применение в ряде теоретических и практических задач (раскраска графа, проектирование БИС и ПЛИС, конечно-элементное моделирование и др.). Существующие последовательные и параллельные алгоритмы предполагают возможность размещения графов и промежуточных данных обработки в оперативной памяти и неприменимы для случая сверхбольших графов. Представлен подход к обработке сверхбольших графов на основе использования па-раллельной реляционной СУБД PargreSQL, разработанной на базе свободной СУБД PostgreSQL.

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


интеллектуальный анализ, разбиение графов, параллельные СУБД.

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

PDF

Литература


Ordonez, C. Bayesian Classifiers Programmed in SQL / C. Ordonez, S.K. Pitchaimalai // IEEE Transactions on Knowledge and Data Engineering. – 2010. – Vol. 22, № 1. – P. 139–144.

Ordonez, C. Integrating K-Means Clustering with a Relational DBMS Using SQL / C. Ordonez // IEEE Transactions on Knowledge and Data Engineering. – 2006. – Vol. 18, № 2. – P. 188–201.

Пан, К.С. Параллельный алгоритм решения задачи анализа рыночной корзины на процессорах Cell / К.С. Пан, М.Л. Цымблер // Вестник ЮУрГУ. Серия «Ма тематическое моделирование и программирование». – 2010. – № 16(192). Вып. 5. – С. 48–57.

Kernighan, B.W. An Efficient Heuristic Procedure for Partitioning Graphs / B.W. Kernighan, S. Lin // The Bell system technical journal. – 1970. – Vol. 49, № 1. – P. 291–307.

Aggarwal, C.C. Managing and Mining Graph Data. / C.C. Aggarwal, H. Wang // Advances in Database Systems. – Springer, 2010. – Vol. 40. – 608 p. 6. Miniakhmetov, R.M. Integrating Fuzzy c-Means Clustering with PostgreSQL / R.M. Miniakhmetov // Труды Института системного программирования РАН. – 2011. – Т. 21. – С. 263–276.

Миниахметов, Р.М. Интеграция алгоритма кластеризации Fuzzy c-Means в PostgreSQL / Р.М. Миниахметов, М.Л. Цымблер // Вычислительные методы и программирование: Новые вычислительные технологии (Электронный научный журнал). – 2012. – Т. 13. – С. 46–52.

Chakravarthy, S. DB-FSG: An SQL-Based Approach for Frequent Subgraph Mining / S. Chakravarthy, S. Pradhan // Proceedings of the 19th International Conference on Database and Expert Systems Applications DEXA 2008 (Turin, Italy, September 1–5). – Springer, 2008. – P. 684–692.

Srihari, S. A Framework for SQL-Based Mining of Large Graphs on Relational Databases / S. Srihari, S. Chandrashekar, S. Parthasarathy // Advances in knowledge discovery and data mining. Lecture Notes in Computer Science. – 2010. – Vol. 6119. – P. 160–167.

Sokolinsky, L.B. Survey of Architectures of Parallel Database Systems / L.B. Sokolinsky // Programming and Computer Software – 2004. – Vol. 30. No. 6 – P. 337–346.

Лепихов, А.В. Обработка запросов в СУБД для кластерных систем / А.В. Лепихов, Л.Б. Соколинский // Программирование. – 2010. – № 4. – С. 25–39.

Lepikhov, A.V. Query Evaluation Techniques for Cluster Database Systems / A.V. Lepikhov, L.B. Sokolinsky // Proceedings of the 14th East European Conference on Advances in Databases and Information Systems (ADBIS 2010, Novi Sad, Serbia, September 20-24). Lecture Notes in Computer Science. – Springer, 2010. – Vol. 6295.– P. 351–362.

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




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