TY - JOUR
T1 - Adding regular expressions to graph reachability and pattern queries
AU - Fan, Wenfei
AU - Li, Jianzhong
AU - Ma, Shuai
AU - Tang, Nan
AU - Wu, Yinghui
PY - 2012
Y1 - 2012
N2 - It is increasingly common to find graphs in which edges bear different types, indicating a variety of relationships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, expressing the connectivity in a data graph via edges of various types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible information than their traditional counterparts.Better still, their increased expressive power does not come with extra complexity. Indeed, (1) we investigate their containment and minimization problems, and show that these fundamental problems are in quadratic time for reachability queries and are in cubic time for pattern queries. (2) We develop analgorithm for answering reachability queries, in quadratic time as for their traditional counterpart. (3) We provide two cubictime algorithms for evaluating graph pattern queries based on extended graph simulation, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. (4) Theeffectiveness, efficiency and scalability of these algorithms are experimentally verified using real-life data and synthetic data.
AB - It is increasingly common to find graphs in which edges bear different types, indicating a variety of relationships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, expressing the connectivity in a data graph via edges of various types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible information than their traditional counterparts.Better still, their increased expressive power does not come with extra complexity. Indeed, (1) we investigate their containment and minimization problems, and show that these fundamental problems are in quadratic time for reachability queries and are in cubic time for pattern queries. (2) We develop analgorithm for answering reachability queries, in quadratic time as for their traditional counterpart. (3) We provide two cubictime algorithms for evaluating graph pattern queries based on extended graph simulation, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. (4) Theeffectiveness, efficiency and scalability of these algorithms are experimentally verified using real-life data and synthetic data.
U2 - 10.1007/s11704-012-1312-y
DO - 10.1007/s11704-012-1312-y
M3 - Article
VL - 6
SP - 313
EP - 338
JO - Frontiers of Computer Science
JF - Frontiers of Computer Science
SN - 2095-2228
IS - 3
ER -