Research On LBS Oriented Nearest Neighbor And Reverse Nearest Neighbor Spatial Keyword Query

With the increasing development of geo-location services and the Internet, there are large numbers of textual objects with information of geographical position springing up in web. The utilization of these objects in location based services is so wide that the spatial keyword query becomes quite important. Consequently, the study of spatial keyword query which takes into account both locations and textual descriptions of the objects has drawn much attention from the commercial organizations and research communities.This paper focuses on two significant query problems, that is, top-k spatial keyword query and ranked reverse spatial keyword query. The former one is to find out all the objects that is one of k-nearest neighbors of query q. The latter one can return a set of data points for which the query q is one of its k-nearest neighbors. These two types of query are researched and solutions for different specific query problems are put forward in this paper. The main research work is as follows:(1) This paper analyzes the related works and background significance of spatial keyword query in LBS, pointing out the advantages and disadvantages of previous work. The work above provides a theoretical basis for following research.(2) For the problem of the spatial keyword query on road networks, we first propose a heuristic structure index called IH-Tree through improving existing overlay network approach and using inverted index to accelerate query processing. Furthermore, we also propose a hybrid index named SG-Tree. The idea of SG-Tree is to create a signature for each node in G-Tree, improving query efficiency tremendously.(3) In this paper, we define a novel query problem, a Ranked Reverse Spatial Keyword Nearest Neighbors Query called Ranked-RSKNN, which can return top t most affected answers in terms of both textual and spatial relevance. Two novel solutions of SIS and Inv SR-Tree are proposed to solve the Ranked-RSKNN query, and we also show the advantages and disadvantages of these two solutions.In this paper, extensive experiments are conducted on different real-world and synthetic datasets to evaluate the efficiency and reliability of our proposed algorithms. Multiple measurements are used in our experiments.