Benchmarking the continuous behavior of stream processing techniques on the problem of enumerating weakly connected components

Autor: Cassanmagnago Somoza, Sergi
Přispěvatelé: Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Pasarella Sanchez, Edelmira, Vidal, María-Esther
Jazyk: angličtina
Rok vydání: 2023
Předmět:
Popis: The problem of enumerating subgraphs satisfying some properties (e.g., patterns and mo- tifs) corresponds to listing such subgraphs. In general, because of the large/huge graphs re- lating objects in different domains (biology, mobile networks, social networks, genetics, etc.), waiting until achieving the whole enumeration of subgraphs satisfying some properties can be too expensive and unmanageable for some families of problems. Thus, the possibility of incrementally enumerating these subgraphs (i.e., a subgraph is returned as soon as they are identified) rises as a promising approach for some families of problems (e.g., network analysis and motif identification). In effect, following a search approach over the listed subgraphs allows stopping the enumeration when it is convenient. The implementation of incremental enumer- ation solutions suits well to stream processing paradigms and frameworks. In this work, as a proof of concept, we conduct a comparative study of the continuous behavior of two stream processing-based solutions for the problem of incrementally enumerating weakly connected components of (bounded) undirected graphs. One of these solutions is implemented using the Go programming language following the Dynamic Pipeline Paradigm, and the other solution is implemented on top of the DataSet API provided by the Apache Flink Framework. Finally, we analyze and report experiments against large graphs having up to 2, 746 connected compo- nents. Obtained results satisfy our expectations. To assess the incremental delivery of results, we measure the the diefficiency metrics, i.e., the continuous efficiency of the implementation of the algorithm for generating incremental results. El problema de l'enumeració dels subgrafs que satisfan determinades propietats (per exem- ple patrons i disenys) correspon a la mostra d'aquests subgrafs. En general, a causa dels grafs grans/enormes que relacionen objectes en diferents dominis (biologia, xarxes mòbils, xarxes socials, genètica, etc.), esperar fins a aconseguir l'enumeració sencera dels subgrafs que satisfacin certes propietats pot ser massa costós i immanejable per a algunes famílies de problemes. Per tant, la possibilitat d'enumerar incrementalment aquests subgrafs (es dir, enumerar els com- ponents a mesura que es calculen o s'identifiquen) sorgeix com una alternativa prometedora per a algunes famílies de problemes (per exemple, en l'an'alisi de xarxes i en l'identificació de patrons). En efecte, seguir un enfocament de cerca sobre els subgrafs enumerats permet aturar l'enumeració quan sigui convenient. La implementacióde solucions d'enumeració incremental s'adapta bé als frameworks i paradigmes de processament de fluxos de dades. En aquest tre- ball, com a prova de concepte, realitzem un estudi comparatiu del comportament continu de dues solucions basades en el processament de fluxos de dades per al problema de l'enumeració incremental de components d'ebilment connexes de grafs (acotats) no dirigits. Una d'aques- tes solucions s'implementa utilitzant el llenguatge de programació Go seguint el Paradigma de Dynamic Pipeline, i l'altra solució s'implementa sobre l'API de DataSet proporcionada per l'Apache Flink Framework. Finalment, analitzem i informem sobre experiments realitzats amb grafs grans que contenen fins a 2746 components connexes. Els resultats obtinguts satisfan les nostres expectatives. Per avaluar el lliurament incremental de resultats, mesurem les mètriques de dieficiència, es a dir, l'eficiència continua de la implementació de l'algorisme per generar resultats incrementals.
Databáze: OpenAIRE
Externí odkaz: