To read this content please select one of the options below:

Efficient keyword search on graph data for finding diverse and relevant answers

Chang-Sup Park (Department of Computer Science, Dongduk Women's University, Seoul, Korea)

International Journal of Web Information Systems

ISSN: 1744-0084

Article publication date: 12 May 2023

Issue publication date: 12 July 2023




This paper studies a keyword search over graph-structured data used in various fields such as semantic web, linked open data and social networks. This study aims to propose an efficient keyword search algorithm on graph data to find top-k answers that are most relevant to the query and have diverse content nodes for the input keywords.


Based on an aggregative measure of diversity of an answer set, this study proposes an approach to searching the top-k diverse answers to a query on graph data, which finds a set of most relevant answer trees whose average dissimilarity should be no lower than a given threshold. This study defines a diversity constraint that must be satisfied for a subset of answer trees to be included in the solution. Then, an enumeration algorithm and a heuristic search algorithm are proposed to find an optimal solution efficiently based on the diversity constraint and an A* heuristic. This study also provides strategies for improving the performance of the heuristic search method.


The results of experiments using a real data set demonstrate that the proposed search algorithm can find top-k diverse and relevant answers to a query on large-scale graph data efficiently and outperforms the previous methods.


This study proposes a new keyword search method for graph data that finds an optimal solution with diverse and relevant answers to the query. It can provide users with query results that satisfy their various information needs on large graph data.



This work was supported by the Dongduk Women's University grant.


Park, C.-S. (2023), "Efficient keyword search on graph data for finding diverse and relevant answers", International Journal of Web Information Systems, Vol. 19 No. 1, pp. 19-41.



Emerald Publishing Limited

Copyright © 2023, Emerald Publishing Limited

Related articles