Distributed Graph Pattern Matching

Shuai Ma, Yang Cao, Jinpeng Huai, Tianyu Wo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 21st International Conference on World Wide Web
Place of PublicationNew York, NY, USA
PublisherACM
Pages949-958
Number of pages10
ISBN (Print)978-1-4503-1229-5
DOIs
Publication statusPublished - 2012

Publication series

NameWWW '12
PublisherACM

Fingerprint Dive into the research topics of 'Distributed Graph Pattern Matching'. Together they form a unique fingerprint.

Cite this