| Recent decades have witnessed the fast revolution of the mobile internet. The mobile terminal, such as smartphone, tablet computer, etc., has been widely used by millions of users all over the world everyday. Among all types of application on mobile terminal, the application with top-k query based on geographic information(Location-Based Services)is one of the most commonly used. Given the location of an user with mobile phone or i Pad, and a list of keywords, the system will return the top-k textual relevant objects which are also most close to user’s location. There are many research works that addressed this special query in recent years. However, these works have two drawbacks. The fisrt one is the ine?ciency in query processing. The second one is the huge overhead of index storage. Hence, they cannot support very large datasets. To overcome these shortcomings of existing works, this thesis proposes novel solutions in supporting top-k type-ahead keyword search for Euclidean space, the top-k query processing for road networks, and the top-k keyword query for road networks respectively. The major contributions of the thesis include:1) Top-K type-ahead keyword search for Euclidean space: Traditional spatial keyword search requires users to provide complete keywords before they can get the answers.However, in pratical use, such a way is tedious and susceptible to errors. To alleviate this problem, the type-ahead keyword search is introduced, i.e. the system returns the relevant answers on-the-fly when user types letter-by-letter. The thesis presents a novel index called PR-Tree, to support such type-ahead search with good e?ciency and scalability. The PR-Tree’s construction considers both spacial and textual information, thus it can easily do spacial and textual pruning on query time. We discuss how to support both single prefix query and multiple keywords query. Experimental studies show that PR-Tree has achieved a better performance compared with the state-of-the-art methods.2) Top-K query with scalable index for road networks: Though the spatial queries for Euclidean space can provide user with useful information on map, however, in daily life,either to walk or drive, people primarily stay on road, since it is impossible to fly over from one place to another. Therefore, the spatial queries for road network are more practical and useful. There are two challenges to transit the techiques for Euclidean space to handle the problems for the road networks. The first one is how to compute the graph distance on the road, and the second one is how to retrieve the top-k answers in real time. The thesis proposes an elegant index, named G-Tree. G-Tree is a balanced tree structure, which is constructed by recursively partitioning the network into sub-networks. To calculate the shortest-path distance, we propose an assembly-based method, to compute any pairs of two nodes with the dynamic programming algorithm. Based on those distances, an e?cient search algorithm to get the top-k answers is designed. Compared with the state-of-the-art methods, G-Tree is faster in query processing time by nearly 2 to 3 orders of magnitudes.3) Top-K keyword search for road network: In daily use, user may not only consider the space proximity between the query location and the objects, but also concern on the textual relevancy between the given keywords and the textual description of the objects.Thus, it is natural to extend the keyword search to the basic top-k query on road network.To support this type of queries, based on the G-Tree index, in this paper, an additional textual inverted list is added on each G-Tree node for building a new index, called IGTree, to support this query. The inverted list maintains the textual upper bound for a given keyword. Based on the best-first traversal algorithm, IG-Tree can effectively do top-k pruning and support very large dataset easily.
|
PDF Full Text Request