Optimizing incremental maintenance of minimal bisimulation of cyclic graphs

Jintian Deng; Byron Choi; Jianliang Xu; Sourav S. Bhowmick

doi:10.1007/978-3-642-20149-3_39

Optimizing incremental maintenance of minimal bisimulation of cyclic graphs

Jintian Deng^*, Byron Choi, Jianliang Xu, Sourav S. Bhowmick

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

1 Citation (Scopus)

Abstract

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 language	English
Title of host publication	Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings
Pages	543-557
Number of pages	15
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-20149-3_39
Publication status	Published - 2011
Event	16th International Conference on Database Systems for Advanced Applications, DASFAA 2011 - , Hong Kong Duration: 22 Apr 2011 → 25 Apr 2011 https://link.springer.com/book/10.1007/978-3-642-20244-5

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6587 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Database Systems for Advanced Applications, DASFAA 2011
Country/Territory	Hong Kong
Period	22/04/11 → 25/04/11
Internet address	https://link.springer.com/book/10.1007/978-3-642-20244-5

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-20149-3_39

Cite this

Deng, J., Choi, B., Xu, J., & Bhowmick, S. S. (2011). Optimizing incremental maintenance of minimal bisimulation of cyclic graphs. In Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings (PART 1 ed., pp. 543-557). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6587 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-20149-3_39

Deng, Jintian ; Choi, Byron ; Xu, Jianliang et al. / Optimizing incremental maintenance of minimal bisimulation of cyclic graphs. Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings. PART 1. ed. 2011. pp. 543-557 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{73273db1cb9b4288ac63e77f40df0148,

title = "Optimizing incremental maintenance of minimal bisimulation of cyclic graphs",

abstract = "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.",

author = "Jintian Deng and Byron Choi and Jianliang Xu and Bhowmick, {Sourav S.}",

note = "Copyright: Copyright 2011 Elsevier B.V., All rights reserved.; 16th International Conference on Database Systems for Advanced Applications, DASFAA 2011 ; Conference date: 22-04-2011 Through 25-04-2011",

year = "2011",

doi = "10.1007/978-3-642-20149-3_39",

language = "English",

isbn = "9783642201486",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "543--557",

booktitle = "Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings",

edition = "PART 1",

url = "https://link.springer.com/book/10.1007/978-3-642-20244-5",

}

Deng, J, Choi, B , Xu, J & Bhowmick, SS 2011, Optimizing incremental maintenance of minimal bisimulation of cyclic graphs. in Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6587 LNCS, pp. 543-557, 16th International Conference on Database Systems for Advanced Applications, DASFAA 2011, Hong Kong, 22/04/11. https://doi.org/10.1007/978-3-642-20149-3_39

Optimizing incremental maintenance of minimal bisimulation of cyclic graphs. / Deng, Jintian; Choi, Byron ; Xu, Jianliang et al.
Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings. PART 1. ed. 2011. p. 543-557 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6587 LNCS, No. PART 1).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Optimizing incremental maintenance of minimal bisimulation of cyclic graphs

AU - Deng, Jintian

AU - Choi, Byron

AU - Xu, Jianliang

AU - Bhowmick, Sourav S.

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 proceeding

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 -

Deng J, Choi B , Xu J, Bhowmick SS. Optimizing incremental maintenance of minimal bisimulation of cyclic graphs. In Database Systems for Advanced Applications - 16th International Conference, DASFAA 2011, Proceedings. PART 1 ed. 2011. p. 543-557. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-20149-3_39

Optimizing incremental maintenance of minimal bisimulation of cyclic graphs

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this