document: Distributed graph pattern matching Graph simulation has been adopted for pattern matching to reduce the complexity and capture the need of novel applications . With 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 , captured by a message-passing model , for graph simulation . We also identify three complexity measures : visit times , makespan and data shipment , for analyzing the distributed algorithms , and show that these measures are essentially controversial with each other . ( 3 ) We propose distributed algorithms and optimization techniques that 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 .
doc_bio_tags: O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O B I O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O B I O O O O O O O O B I O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O B I O O O O O O O O B I O O O O B I O O O O O O O O O O O O O O O O O O O O O O