Graph Optimisation and Big Data
The main goal of the project was identifying problems related to the Big Data challenge in terms of graph models, proving theorems related to these parameters (chromatic number, independence number, etc.), designing (highly parallel optimization) graph algorithms for solving these models, and implementing them in parallel computing environments. The project consisted of theoretic and application oriented parts: the applications posed the most important practical problems (typically somewhat simpler than the problem in full generality) and the theoretical research tried to find theorems that could be applied in the particular question to develop a supercomputer effective procedure. The theoretical research was carried out mainly by the expert participants in Rényi Institute, the algorithm designs by the application oriented participants from universities of Szeged, Pécs and Ljubljana, and Jožef Stefan Institute, but the cooperation was the main strength of the project.
During the project lifetime, a “two-phase” methodology of research was implemented. In the first phase the considered graph-theoretic problems listed in the research plan were investigated on the mathematical level by the Hungarian researchers, while the main task of the Slovenian partners was to analyze these problems with respect to efficient data structures, computational paradigms and parallelization. In the second phase a more intensive cooperation has been reached, and the research results have been integrated in order to realize new generation algorithmic solutions for graph based Big Data sets. In this second phase the Slovenian partners have developed new methodology in Big data handling with respect to the focused problems and by feedback of these results, the algorithmic and discrete mathematics research represented by the Hungarian side needed to find sophisticated modeling and algorithmic solutions. Especially during this second phase the international partnership worked in close interaction. Both phases lasted for approximately one and half year. To support the cooperation between the project partners several study trips were realized. During these trips the computational methodology developed by the Slovenian partner and the mathematical and algorithmic results of the Hungarian partner were integrated through intensive common work. Apart from these individual trips two workshops were also organized during the project lifetime. The first workshop in 2016 was devoted to presenting the preliminary results and to plan the detailed common research work, while the workshop in 2018 was devoted to finalizing the common research activity. These workshops were also open for other researchers as well as for students, thus seizing the opportunity for the training of young scholars. Also, some new algorithmic approaches were realized in computer programs as a result of the common research efforts. These computer programs were implemented in the last year, and we expect to continue their development after the project has ended.
The considered main work packages in which the cooperative research results are integrated were the following: - Graph and network modeling and their relationship with big data (led by HU) - New computational paradigms for graph analytics and big data (led by SLO) - New auxiliary algorithms based on graph analytics and big data sets (led by HU) - Parallelization of the new algorithms (led by SLO) The outcome of this cooperation is the development of new structural, modeling and algorithmic results in graph theory and computer science.
Main web page of the project.
Partners
Faculty of Computer and Information Science (FCI)
Jozef Stefan Institute (JSI)
P-Lab team
Funding
