Keyword Search Algorithm, On The Map

In recent ten years, keyword search technique is a popular topic in database, information retrieval and data ming areas.Recently, keyword search on graph-structured data attracts much attention due to better applicability. Different from the traditional keyword search algorithms, the search algorithms on graph return the subgraphs of the original graph each of which contains all the query keywords.Current algorithms are based on the minimal steiner tree, which employ the backward search and forward search strategy to get the subgraphs. However, such kind of algorithms has three main drawbacks, which cause the results lack of semantic information. First,they don't consider the matching degree between graph nodes and query keywords during searching; second,they don't take the structural information into account which is implied in the graph structure; third, tree-structured subgraphs can't convey enough semantic information.In this paper, two novel algorithms are introduced,which employ the vector space model and random walk model to address the drawbacks above and make the results more semantical.The first algorithm is based on random walk with restart model,which modifies the model to support vector space model. This algorithm firstly searches for the central node of the query keywords,and then searches for the keyword nodes through this central node to construct the subgraph. The second algorithm is based on the probabilistic model, which designs a scoring function considering both the vector space model and random walk with restart model.This algorithm firstly searches for the matching keyword nodes of the query keywords, and then bridges these keyword nodes through the central node of them to construct the subgraph. The experimental results show that the presented approaches are effective and efficient.