TY - GEN
T1 - Subgraph search over massive disk resident graphs
AU - Peng, Peng
AU - Zou, Lei
AU - Chen, Lei
AU - Lin, Xuemin
AU - Zhao, Dongyan
PY - 2011
Y1 - 2011
N2 - Due to the wide applications, subgraph queries have attracted lots of attentions in database community. In this paper, we focus on subgraph queries over a large graph G. Different from existing feature-based approaches, we propose a bitmap structure based on edges to index the graph. At run time, we decompose Q into a set of adjacent edge pairs (AEP). We develop edge join (EJ) algorithms to address AEP subqueries. The bitmap index can reduce both I/O and CPU cost. More importantly, the bitmap index has the linear space complexity instead of the exponential complexity in feature-based approaches, which confirms its good scalability. Extensive experiments show that our method outperforms existing ones in both online and offline performances significantly.
AB - Due to the wide applications, subgraph queries have attracted lots of attentions in database community. In this paper, we focus on subgraph queries over a large graph G. Different from existing feature-based approaches, we propose a bitmap structure based on edges to index the graph. At run time, we decompose Q into a set of adjacent edge pairs (AEP). We develop edge join (EJ) algorithms to address AEP subqueries. The bitmap index can reduce both I/O and CPU cost. More importantly, the bitmap index has the linear space complexity instead of the exponential complexity in feature-based approaches, which confirms its good scalability. Extensive experiments show that our method outperforms existing ones in both online and offline performances significantly.
UR - https://openalex.org/W1908699674
UR - https://www.scopus.com/pages/publications/79961180634
U2 - 10.1007/978-3-642-22351-8_19
DO - 10.1007/978-3-642-22351-8_19
M3 - Conference Paper published in a book
SN - 9783642223501
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 312
EP - 321
BT - Scientific and Statistical Database Management - 23rd International Conference, SSDBM 2011, Proceedings
T2 - 23rd International Conference on Scientific and Statistical Database Management, SSDBM 2011
Y2 - 20 July 2011 through 22 July 2011
ER -