A Model-based Keyword Search Approach for Detecting Top-k Effective Answers
Asieh Ghanbarpour, Hassan Naderi · The Computer Journal · 2018
Keyword search (KWS) has been known as an attractive query processor in retrieving information from various types of data which could be modeled as a graph. An answer in response to a keyword query is a set of cohesively connected structures which shows how the data containing query keywords are interconnected in the graph. Finding answers to a given query efficiently and ranking the retrieved answers in an effective way are still two challenging problems in KWS domain. In this paper, we first propose a novel scoring function to optimize the accuracy of ranking the answers. This function is defined based on a carefully designed model called SARM which is an integrated model of the content and structure of an answer. We then develop a two-level KWS approach to support the efficient retrieval of top-k answers to a given query. This approach is based on pruning the search space to concentrate the search on the promising regions. The efficiency of this approach is improved by estimating the boundary scores of the answers in the regions. Extensive experiments conducted on a standard evaluation framework with three real-world datasets confirm the efficiency and effectiveness of the proposed approach.