Efficient processing of keyword queries over graph databases for finding effective answers

• We define a new measure of relevance of a node in the graph to a keyword query.
• We propose an extended answer structure for a top-k query over graph databases.
• We propose an inverted list index and search algorithm to find top-k answer trees.
• We enhanced the basic method for more efficient and scalable processing the query.
• Experiments show that the proposed method can find effective top-k answers efficiently.

In this paper, we study on effective and efficient processing of keyword-based queries over graph databases. To produce more relevant answers to a query than the previous approaches, we suggest a new answer tree structure which has no constraint on the number of keyword nodes chosen for each keyword in the query. For efficient search of answer trees on the large graph databases, we design an inverted list index to pre-compute and store connectivity and relevance information of nodes to keyword terms in the graph. We propose a query processing algorithm which aggregates from the pre-constructed inverted lists the best keyword nodes and root nodes to find top-k answer trees most relevant to the given query. We also enhance the method by extending the structure of the inverted list and adopting a relevance lookup table, which enables more accurate estimation of the relevance scores of candidate root nodes and efficient search of top-k answer trees. Performance evaluation by experiments with real graph datasets shows that the proposed method can find more effective top-k answers than the previous approaches and provides acceptable and scalable execution performance for various types of keyword queries on large graph databases.