TY - GEN
T1 - Optimizing incremental maintenance of minimal bisimulation of cyclic graphs
AU - Deng, Jintian
AU - CHOI, Koon Kau
AU - XU, Jianliang
AU - Bhowmick, Sourav S.
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - Graph-structured databases have numerous recent applications including the Semantic Web, biological databases and XML, among many others. In this paper, we study the maintenance problem of a popular structural index, namely bisimulation, of a possibly cyclic data graph. In comparison, previous work mainly focuses on acyclic graphs. In the context of database applications, it is natural to compute minimal bisimulation with merging algorithms. First, we propose a maintenance algorithm for a minimal bisimulation of a cyclic graph, in the style of merging. Second, to prune the computation on non-bisimilar SCCs, we propose a feature-based optimization. The features are designed to be constructed and used more efficiently than bisimulation minimization. Third, we conduct an experimental study that verifies the effectiveness and efficiency of our algorithm. Our features-based optimization pruned 50% (on average) unnecessary bisimulation computation. Our experiment verifies that we extend the current state-of-the-art with a capability on handling cyclic graphs in maintenance of minimal bisimulation.
AB - Graph-structured databases have numerous recent applications including the Semantic Web, biological databases and XML, among many others. In this paper, we study the maintenance problem of a popular structural index, namely bisimulation, of a possibly cyclic data graph. In comparison, previous work mainly focuses on acyclic graphs. In the context of database applications, it is natural to compute minimal bisimulation with merging algorithms. First, we propose a maintenance algorithm for a minimal bisimulation of a cyclic graph, in the style of merging. Second, to prune the computation on non-bisimilar SCCs, we propose a feature-based optimization. The features are designed to be constructed and used more efficiently than bisimulation minimization. Third, we conduct an experimental study that verifies the effectiveness and efficiency of our algorithm. Our features-based optimization pruned 50% (on average) unnecessary bisimulation computation. Our experiment verifies that we extend the current state-of-the-art with a capability on handling cyclic graphs in maintenance of minimal bisimulation.
UR - http://www.scopus.com/inward/record.url?scp=79955077468&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-20149-3_39
DO - 10.1007/978-3-642-20149-3_39
M3 - Conference contribution
AN - SCOPUS:79955077468
SN - 9783642201486
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 543
EP - 557
BT - Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings
T2 - 16th International Conference on Database Systems for Advanced Applications, DASFAA 2011
Y2 - 22 April 2011 through 25 April 2011
ER -