Show simple item record

dc.contributor.authorPienta, Robert
dc.contributor.authorTamersoy, Acar
dc.contributor.authorTong, Hanghang
dc.contributor.authorChau, Duen Horng (Polo)
dc.date.accessioned2013-11-04T15:29:04Z
dc.date.available2013-11-04T15:29:04Z
dc.date.issued2013
dc.identifier.urihttp://hdl.handle.net/1853/49341
dc.descriptionResearch area: Graph analysisen_US
dc.description.abstractGiven a large graph with millions of nodes and edges, say a social graph where both the nodes and edges can have multiple different kinds of attributes (e.g., job titles, tie strengths), how do we quickly find matches for subgraphs of interest (e.g., a ring of businessmen with strong ties)? We propose MAGE, Multiple Attribute Graph Engine, a subgraph matching framework that pushes the envelope of graph matching capabilities and performance, through several major innovations: (i) with line graph transformation, MAGE works for graphs with both node and edge attributes and return both exact as well as near matches — other techniques often support only node attributes and return only exact matches; (ii) MAGE supports a plethora of queries, including multiple attributes for each node or edge, wild-cards as attribute values (i.e., match any permissible value), and continuous attributes via multiple discretization strategies; (iii) MAGE leverages a novel technique based on memory mapping to compute random walk with restart probabilities, which provides a speedup of more than 2 orders of magnitude on large graphs. We evaluated MAGE’s effectiveness and scalability with real and synthetic graphs with up to 2.3 million edges. Experimental results on the DBLP authorship graph and the Rotten Tomatoes movie graph illustrate the effectiveness and exploratory functionality of our contributions to graph querying. By devising query-centric innovations, our work improves the ease with which a user can explore their graph data.en_US
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCSE Technical Reports ; GT-CSE-13-08en_US
dc.subjectGraph miningen_US
dc.subjectGraph queryingen_US
dc.subjectGraph searchen_US
dc.titleMage: Expressive Pattern Matching in Richly-Attributed Graphsen_US
dc.typeTechnical Reporten_US
dc.contributor.corporatenameGeorgia Institute of Technology. College of Computingen_US
dc.contributor.corporatenameGeorgia Institute of Technology. School of Computational Science and Engineeringen_US
dc.contributor.corporatenameCity University of New York. Department of Computer Scienceen_US
dc.embargo.termsnullen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record