DocumentCode :
610362
Title :
Ontology-based subgraph querying
Author :
Yinghui Wu ; Shengqi Yang ; Xifeng Yan
Author_Institution :
Univ. of California Santa Barbara, Santa Barbara, CA, USA
fYear :
2013
fDate :
8-12 April 2013
Firstpage :
697
Lastpage :
708
Abstract :
Subgraph querying has been applied in a variety of emerging applications. Traditional subgraph querying based on subgraph isomorphism requires identical label matching, which is often too restrictive to capture the matches that are semantically close to the query graphs. This paper extends subgraph querying to identify semantically related matches by leveraging ontology information. (1) We introduce the ontology-based subgraph querying, which revises subgraph isomorphism by mapping a query to semantically related subgraphs in terms of a given ontology graph. We introduce a metric to measure the similarity of the matches. Based on the metric, we introduce an optimization problem to find top K best matches. (2) We provide a filtering-and-verification framework to identify (top-K) matches for ontology-based subgraph queries. The framework efficiently extracts a small subgraph of the data graph from an ontology index, and further computes the matches by only accessing the extracted subgraph. (3) In addition, we show that the ontology index can be efficiently updated upon the changes to the data graphs, enabling the framework to cope with dynamic data graphs. (4) We experimentally verify the effectiveness and efficiency of our framework using both synthetic and real life graphs, comparing with traditional subgraph querying methods.
Keywords :
formal verification; graph theory; ontologies (artificial intelligence); optimisation; pattern matching; query processing; dynamic data graphs; filtering-and-verification framework; identical label matching; match similarity; ontology index; ontology information; ontology-based subgraph querying; optimization problem; real life graphs; subgraph isomorphism-based subgraph querying; synthetic graphs; Data mining; Indexing; Measurement; Ontologies; Query processing; Semantics;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Engineering (ICDE), 2013 IEEE 29th International Conference on
Conference_Location :
Brisbane, QLD
ISSN :
1063-6382
Print_ISBN :
978-1-4673-4909-3
Electronic_ISBN :
1063-6382
Type :
conf
DOI :
10.1109/ICDE.2013.6544867
Filename :
6544867
Link To Document :
بازگشت