Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Subgraph Search over Massive Disk Resident Graphs
verfasst von : Peng Peng, Lei Zou, Lei Chen, Xuemin Lin, Dongyan Zhao
Erschienen in: Scientific and Statistical Database Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
a
djacent
e
dge
p
airs (AEP). We develop
e
dge
j
oin (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.