Research On Keyword Search On Graph Based On Content And Structure

With the development of the information retrieval technology, keyword search technology has been paid close attention to in the academic circles. It has been widely studied in recent years on the database, information retrieval, data mining and other fields. With the explosive growth of the data on the web and the generation of huge graph data collections,keyword query in graph has attracted much attention in recent years.Keyword search algorithm is looking for the subgraphs on the data graph. The subgraphs which returned by the algorithm should contain all or part of the query keywords, while the traditional keyword search algorithm is just to find a list of documents related to the query. A lot of researches about keyword search on graphs are mainly to find the minimum spanning trees which contain all or part of the keywords. In recent years, it has been shown that finding the subgraphs rather than trees is more useful for users, and subgraphs can also provide more detail information. However, the works about the keyword search on graphs only consider distance relationship between each node when searching, and ignore the similarity between node and query. When displaying the results, existing algorithms cannot well present the nearest relationships between any two keyword nodes.Based on the problems above, the keyword search on graphs based on the content and structure (KSGCS) method is proposed in this paper, we present new method for computing the similarity between the node and the query, and also put forward the node searching algorithm to return the results which related to query and which nodes closely in structure for users. In this paper, firstly we improve the accuracy of the similarity of each node with the query keywords by improving language model. And we use each keyword node as the initial search node to find an optimal solution. In this way, we can guarantee that every keyword node can appear in the results. Secondly, we sort these results according to the mechanism,and choose the top-k results to display. In addition, we adopt the latent Steiner graph to display the results, which can display the most nearest relationships between each keyword node clearly. Finally, we use two different data sets to construct two graphs, and in order to evaluate the search results, we use different evaluation methods. The result of experiments shows that the KSGCS method we proposed can return faster and better results for users which can satisfy the user's query demand better.