Large Scale Graph Representations for Subgraph Census

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2016

Autores

Paredes, P (Autor) Outra; Pedro Ribeiro (Autor) FCUP

Ata de Conferência Internacional

Título: Advances in Network Science - 12th International Conference and School, NetSci-X 2016, Wroclaw, Poland, January 11-13, 2016, Proceedings

Páginas: 186-194

12th International Conference and School on Advances in Network Science, NetSci-X 2016

11 January 2016 through 13 January 2016

Indexação

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00K-3R4

DOI: 10.1007/978-3-319-28361-6_16

Abstract (EN): A Subgraph Census (determining the frequency of smaller subgraphs in a network) is an important computational task at the heart of several graph mining algorithms. Here we focus on the g-tries, an efficient state-of-the art data structure. Its algorithm makes extensive use of the graph primitive that checks if a certain edge exists. The original implementation used adjacency matrices in order to make this operation as fast as possible, as is the case with most past approaches. This representation is very expensive in memory usage, limiting the applicability. In this paper we study a number of possible approaches that scale linearly with the number of edges. We make an extensive empirical study of these alternatives in order to find an efficient hybrid approach that combines the best representations. We achieve a performance that is less than 50% slower than the adjacency matrix on average (almost 3 times more efficient than a naive binary search implementation), while being memory efficient and tunable for different memory restrictions. © Springer-Verlag Berlin Heidelberg 2016.

Idioma: Inglês

Tipo (Avaliação Docente): Científica