Document Type : Original Research Paper


1 Department of Computer Engineering, University of Sistan and Baluchestan, Zahedan, Iran

2 Computer Engineering Department, Iran University of Science and Technology (IUST), Tehran, Iran

3 University of Sistan and Baluchestan, Zahedan, Iran


Abstract—Keyword Search is known as a user-friendly alternative for structured languages to retrieve information from graph-structured data. Efficient retrieving of relevant answers to a keyword query and effective ranking of these answers according to their relevance are two main challenges in the keyword search over graph-structured data. In this paper, a novel scoring function is proposed, which utilizes both the textual and structural features of answers in order to produce a more accurate order of answers. In addition, a query processing algorithm is developed based on information spreading technique to enumerate answers in approximate order. This algorithm is further improved by allowing a skewed development toward more promising paths and enables a more efficient processing of keyword queries. Performance evaluation through extensive experiments on a standard benchmark of three real-world datasets shows the effectiveness and efficiency of the proposed algorithms.

Index Terms—Information retrieval, Database, Keyword search, Relevant answers, Information spreading.


Main Subjects