Name
Title | ||
|---|---|---|
Semantic Guided and Response Times Bounded Top-k Similarity Search over Knowledge Graphs |
Abstract | ||
|---|---|---|
Recently, graph query is widely adopted for querying knowledge graphs. Given a query graph G
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub>
, the graph query finds subgraphs in a knowledge graph G that exactly or approximately match G
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub>
. We face two challenges on graph query: (1) the structural gap between G
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub>
and the predefined schema in G causes mismatch with query graph, (2) users cannot view the answers until the graph query terminates, leading to a longer system response time (SRT). In this paper, we propose a semantic-guided and response-time-bounded graph query to return the top-k answers effectively and efficiently. We leverage a knowledge graph embedding model to build the semantic graph SG
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub>
, and we define the path semantic similarity (pss) over SG
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub>
as the metric to evaluate the answer's quality. Then, we propose an A* semantic search on SG
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub>
to find the top-k answers with the greatest pss via a heuristic pss estimation. Furthermore, we make an approximate optimization on A* semantic search to allow users to trade off the effectiveness for SRT within a user- specific time bound. Extensive experiments over real datasets confirm the effectiveness and efficiency of our solution. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/ICDE48307.2020.00045 | 2020 IEEE 36th International Conference on Data Engineering (ICDE) |
Keywords | DocType | ISSN |
semantic graph,path semantic similarity,A* semantic search,query graph,knowledge graph,response times bounded top-k similarity search,subgraphs,structural gap,system response time,top-k answers,heuristic pss estimation,response-time-bounded graph query,semantic-guided graph query | Conference | 1063-6382 |
ISBN | Citations | PageRank |
978-1-7281-2904-4 | 1 | 0.35 |
References | Authors | |
39 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wang Yuxiang | 1 | 1 | 0.35 |
| Arijit Khan | 2 | 526 | 33.55 |
| Tianxing Wu | 3 | 18 | 3.75 |
| Jin Jiahui | 4 | 88 | 16.84 |
| Yan Haijiang | 5 | 1 | 0.35 |