Journal Title
Title of Journal: World Wide Web
|
Abbravation: World Wide Web
|
|
|
|
|
Authors: Peng Peng Lei Zou Lei Chen Xuemin Lin Dongyan Zhao
Publish Date: 2015/01/25
Volume: 19, Issue: 3, Pages: 417-448
Abstract
Due to its wide applications subgraph query has attracted lots of attentions in database community In this paper we focus on subgraph query over a single large graph G ie finding all embeddings of query Q in G Different from existing featurebased approaches we map all edges into a twodimensional space R 2 and propose a bitmap structure to index R 2 At run time we find a set of adjacent edge pairs AEP or starstyle patterns SSP to cover Q We develop edge join EJ algorithms to address both AEP and SSP subqueries Based on the bitmap index our method can optimize I/O and CPU cost More importantly our index has the linear space complexity instead of exponential complexity in featurebased approaches which indicates that our index can scale well with respect to large data size Furthermore our index has light maintenance overhead which has not been considered in most of existing work Extensive experiments show that our method significantly outperforms existing ones in both online and offline processing with respect to query response time index building time index size and index maintenance overhead
Keywords:
.
|
Other Papers In This Journal:
|