Optimizing incremental maintenance of minimal bisimulation of cyclic graphs

Jintian Deng*, Koon Kau CHOI, Jianliang XU, Sourav S. Bhowmick

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings
Number of pages15
EditionPART 1
Publication statusPublished - 2011
Event16th International Conference on Database Systems for Advanced Applications, DASFAA 2011 - Hong Kong, China
Duration: 22 Apr 201125 Apr 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6587 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Conference on Database Systems for Advanced Applications, DASFAA 2011
CityHong Kong

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Optimizing incremental maintenance of minimal bisimulation of cyclic graphs'. Together they form a unique fingerprint.

Cite this