• Login
    View Item 
    •   Athenaeum Home
    • University of Georgia Theses and Dissertations
    • University of Georgia Theses and Dissertations
    • View Item
    •   Athenaeum Home
    • University of Georgia Theses and Dissertations
    • University of Georgia Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Parallel algorithms for subgraph pattern matching

    Thumbnail
    Date
    2014-08
    Author
    Jain, Ayushi
    Metadata
    Show full item record
    Abstract
    Due 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.
    URI
    http://purl.galileo.usg.edu/uga_etd/jain_ayushi_201408_ms
    http://hdl.handle.net/10724/30923
    Collections
    • University of Georgia Theses and Dissertations

    About Athenaeum | Contact Us | Send Feedback
     

     

    Browse

    All of AthenaeumCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    About Athenaeum | Contact Us | Send Feedback