Matches in ScholarlyData for { <https://w3id.org/scholarlydata/inproceedings/www2012/paper/743> ?p ?o. }
Showing items 1 to 14 of
14
with 100 items per page.
- 743 creator jinpeng-huai.
- 743 creator shuai-ma.
- 743 creator tianyu-wo.
- 743 creator yang-cao.
- 743 type InProceedings.
- 743 label "Distributed Graph Pattern Matching".
- 743 sameAs 743.
- 743 abstract "Graph pattern matching is often defined in terms of subgraph isomorphism, which is \NP-complete, and is often too restrictive to catch sensible matches in emerging applications. Graph simulation has been adopted for pattern matching to reduce the complexity and capture the need of novel applications. In light of the rapid development of the Web and social networks, data is typically distributed over multiple machines. Hence a natural question raised is how to evaluate graph simulation on distributed data. To our knowledge, no such distributed algorithms are in place yet. This paper settles this question by providing evaluation algorithms and optimizations for graph simulation in a distributed setting. (1) We study the impacts of components and data locality on the evaluation of graph simulation. (2) We give an analysis of a large class of distributed algorithms for graph simulation captured by a message-passing model. We also identify three complexity measures: visit times, makespan and data shipment, for the analyses of these distributed algorithms, and show that these measures are controversial with each other. (3) We propose distributed algorithms and optimization techniques which exploit the properties of graph simulation and the analyses of distributed algorithms. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using both real-life and synthetic data.".
- 743 hasAuthorList authorList.
- 743 isPartOf proceedings.
- 743 keyword "distributed evaluation".
- 743 keyword "graph pattern matching".
- 743 keyword "graph simulation".
- 743 title "Distributed Graph Pattern Matching".