Fast top-k search in knowledge graphs
2016 IEEE 32nd international conference on data engineering (ICDE), 2016•ieeexplore.ieee.org
Given a graph query Q posed on a knowledge graph G, top-k graph querying is to find k
matches in G with the highest ranking score according to a ranking function. Fast top-k
search in knowledge graphs is challenging as both graph traversal and similarity search are
expensive. Conventional top-k graph search is typically based on threshold algorithm (TA),
which can no long fit the demand in the new setting. This work proposes STAR, a top-k
knowledge graph search framework. It has two components:(a) a fast top-k algorithm for star …
matches in G with the highest ranking score according to a ranking function. Fast top-k
search in knowledge graphs is challenging as both graph traversal and similarity search are
expensive. Conventional top-k graph search is typically based on threshold algorithm (TA),
which can no long fit the demand in the new setting. This work proposes STAR, a top-k
knowledge graph search framework. It has two components:(a) a fast top-k algorithm for star …
Given a graph query Q posed on a knowledge graph G, top-k graph querying is to find k matches in G with the highest ranking score according to a ranking function. Fast top-k search in knowledge graphs is challenging as both graph traversal and similarity search are expensive. Conventional top-k graph search is typically based on threshold algorithm (TA), which can no long fit the demand in the new setting. This work proposes STAR, a top-k knowledge graph search framework. It has two components: (a) a fast top-k algorithm for star queries, and (b) an assembling algorithm for general graph queries. The assembling algorithm uses star query as a building block and iteratively sweeps the star match lists with a dynamically adjusted bound. For top-k star graph query where an edge can be matched to a path with bounded length d, we develop a message passing algorithm, achieving time complexity O(d 2 |E| + m d ) and space complexity linear to d|V| (assuming the size of Q and k is bounded by a constant), where m is the maximum node degree in G. STAR can further be leveraged to answer general graph queries by decomposing a query to multiple star queries and joining their results later. Learning-based techniques to optimize query decomposition are also developed. We experimentally verify that STAR is 5-10 times faster than the state-of-the-art TA-style graph search algorithm, and 10-100 times faster than a belief propagation approach.
ieeexplore.ieee.org
Showing the best result for this search. See all results