Home // SOTICS 2012, The Second International Conference on Social Eco-Informatics // View article

An Efficient Computation of Reachability Labeling for Graph Pattern Matching

Authors:
Bhargavi Balla
Supreethi Kalyandurgam Pujari

Keywords: graph pattern; graph matching; 2-hop cluster; 2-hop labeling; 2-hop cover.

Abstract:
Due to the rapid growth of Internet, most of the data that is available in the Internet that is archived/ analyzed, is graph structured in nature as graphs form a powerful modeling tool. The problem of graph pattern matching is to find all the patterns that match a user-given graph pattern from a large directed graph. For faster access of paths in the large directed graph, transitive closure of the graph is compressed and maintained using 2-hop reachability labeling technique by assigning every node a 2-hop label. These 2-hop labels are computed using a geometry-based approach that will be useful in solving the graph pattern matching problem. In this paper, a geometry-based approach that computes the 2-hop reachability labeling is described. The experimental results show that the proposed approach efficiently computes the compressed transitive closure technique of reachability labeling.

Pages: 58 to 62

Copyright: Copyright (c) IARIA, 2012

Publication date: October 21, 2012

Published in: conference

ISSN: 2326-9294

ISBN: 978-1-61208-228-8

Location: Venice, Italy

Dates: from October 21, 2012 to October 26, 2012