Show simple item record

dc.contributor.authorJain, Ayushi
dc.description.abstractDue to the growing importance of Big Data, graphs are becoming huge in size and are rapidly getting too large for conventional computer approaches. Graph Pattern Matching is often defined in terms of subgraph isomorphism, an NP-Complete problem. Most existing graph pattern matching algorithms are very compute intensive. Unfortunately, for such massive graphs, sequential approaches are almost unfeasible. Therefore, parallel computing resources are required to meet their computational and memory requirements. The paper presents a novel parallel subgraph pattern matching algorithm, known as ParDualIso based on Akka. Since, the sequential implementation of ParDualIso known as DualIso adapts Dual Simulation as the pruning technique, so we also present the parallel implementation of Dual Simulation, referred as ParDualSim. The runtimes of the algorithms are tested against their sequential counter-parts on massive graphs of 10 million vertices and 250 million edges.
dc.subjectsubgraph isomorphism
dc.subjectparallel algorithms
dc.subjectdual simulation
dc.titleParallel algorithms for subgraph pattern matching
dc.description.departmentComputer Science
dc.description.majorComputer Science
dc.description.advisorJohn A. Miller
dc.description.committeeJohn A. Miller
dc.description.committeeLakshmish Ramaswamy
dc.description.committeeKrzysztof J. Kochut

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record