Querying subgraph sets with g-tries

• Type: Article in International Conference Proceedings Book
• Date: 2012

Authors

Ribeiro, P (Author) FCUP; Silva, F (Author) FCUP

Conference proceedings International

Title: Proceedings of the 2nd ACM SIGMOD Workshop on Databases and Social Networks, DBSocial 2012

Pages: 25-30

Proceedings of the 2nd ACM SIGMOD Workshop on Databases and Social Networks, DBSocial 2012, Scottsdale, AZ, USA, May 20, 2012

Indexing

ISI Web of Knowledge

Scopus - 17 Citations

Other information

Authenticus ID: P-008-525

DOI: 10.1145/2304536.2304541

Abstract (EN): In this paper we present an universal methodology for finding all the occurrences of a given set of subgraphs in one single larger graph. Past approaches would either enumerate all possible subgraphs of a certain size or query a single subgraph. We use g-tries, a data structure specialized in dealing with subgraph sets. G-Tries store the topological information on a tree that exposes common substructure. Using a specialized canonical form and symmetry breaking conditions, a single non-redundant search of the entire set of subgraphs is possible. We give results of applying g-tries querying to different social networks, showing that we can efficiently find the occurrences of a set containing subgraphs of multiple sizes, outperforming previous methods. Copyright 2012 ACM.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 6