TY - GEN
T1 - NOVA
T2 - 15th International Conference on Database Systems for Advanced Applications, DASFAA 2010
AU - Zhu, Ke
AU - Zhang, Ying
AU - Lin, Xuemin
AU - Zhu, Gaoping
AU - Wang, Wei
PY - 2010
Y1 - 2010
N2 - Considerable efforts have been spent in studying subgraph problem. Traditional subgraph containment query is to retrieve all database graphs which contain the query graph g. A variation to that is to find all occurrences of a particular pattern(the query) in a large database graph. We call it subgraph matching problem. The state of art solution to this problem is GADDI. In this paper, we will propose a more efficient index and algorithm to answer subgraph matching problem. The index is based on the label distribution of neighbourhood vertices and it is structured as a multi-dimensional vector signature. A novel algorithm is also proposed to further speed up the isomorphic enumeration process. This algorithm attempts to maximize the computational sharing. It also attempts to predict some enumeration state is impossible to lead to a final answer by eagerly pruning strategy. We have performed extensive experiments to demonstrate the efficiency and the effectiveness of our technique.
AB - Considerable efforts have been spent in studying subgraph problem. Traditional subgraph containment query is to retrieve all database graphs which contain the query graph g. A variation to that is to find all occurrences of a particular pattern(the query) in a large database graph. We call it subgraph matching problem. The state of art solution to this problem is GADDI. In this paper, we will propose a more efficient index and algorithm to answer subgraph matching problem. The index is based on the label distribution of neighbourhood vertices and it is structured as a multi-dimensional vector signature. A novel algorithm is also proposed to further speed up the isomorphic enumeration process. This algorithm attempts to maximize the computational sharing. It also attempts to predict some enumeration state is impossible to lead to a final answer by eagerly pruning strategy. We have performed extensive experiments to demonstrate the efficiency and the effectiveness of our technique.
UR - https://openalex.org/W1479848599
UR - https://www.scopus.com/pages/publications/77957896367
U2 - 10.1007/978-3-642-12026-8_13
DO - 10.1007/978-3-642-12026-8_13
M3 - Conference Paper published in a book
AN - SCOPUS:77957896367
SN - 3642120253
SN - 9783642120251
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 140
EP - 154
BT - Database Systems for Advanced Applications - 15th International Conference, DASFAA 2010, Proceedings
Y2 - 1 April 2010 through 4 April 2010
ER -