Show simple item record

dc.contributor.authorJain, Ayushi
dc.date.accessioned2015-01-29T05:30:19Z
dc.date.available2015-01-29T05:30:19Z
dc.date.issued2014-08
dc.identifier.otherjain_ayushi_201408_ms
dc.identifier.urihttp://purl.galileo.usg.edu/uga_etd/jain_ayushi_201408_ms
dc.identifier.urihttp://hdl.handle.net/10724/30923
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.languageeng
dc.publisheruga
dc.rightspublic
dc.subjectsubgraph isomorphism
dc.subjectparallel algorithms
dc.subjectdual simulation
dc.subjectAkka
dc.titleParallel algorithms for subgraph pattern matching
dc.typeThesis
dc.description.degreeMS
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

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record