Font Size: a A A

Research On Aggregate Keyword Routing Query In Spatial Databases

Posted on:2014-10-24Degree:MasterType:Thesis
Country:ChinaCandidate:K J ChenFull Text:PDF
GTID:2298330434466161Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
In the past ten years, due to the proliferation of the smart device with GPS and quick development of the mobile network, location base service(LBS) becomes part of people’s life. And the web is attached with the spatial property. Thus, spatial query becomes more popular with the development of the mobile network. People can use the smart device to acquire what they want through many location based social network website, such as finding a nearest restaurant with free wifi. People input keyword "wifi""restaurant" to meet his need.There two types of the spatial keyword search query:the boolean keyword query and the top-k query. The top-k query requires the point of intest associated with textual description where the boolean requires keyword. It is hard to join spatial distance and keyword score together. So most existing work focus on the boolean keyword query.Consider the situation that existting work seldom focus on the spatial keyword search with multiple query point, this paper advances a new type of spatial keyword search query in Euclidean space, we call it Aggregate Keyword Routing (AKR) query. The AKR query serves for the people who wants to get together and returns trip plan. Our main contribution can be summarized as follows:1. We formulate a new type of usefule spatial keyword query that considers multiple query points. To the best of our knowledge, it has not been investigate befor.2. We formally prove that the aggregate keyword routing problem is NP-hard.3. We devise an exact algorithm to answer the AKR query based on ellipse prune, and also improve the algorithm of the ellipse range query.4. Focus on the multi-keyword routing query, we use the dynamic programming method to improve the existing algorithm.5.We propose two efficient approximate algorithms for the situation that the number of query points and keywords is very large. We also extend the approximate algorithms to improve the approximation ratio.6. We use real data set to experimentally study the efficiency of our algorithms. Our experiments show that Centre Based Assignment Algorithm outperforms in running time and Tree Expanding Algorithm Extension has the best approximation ratio.
Keywords/Search Tags:Spatial Keyword Search, Ellipse Pruning, Aggregate Nearest Neighbor
PDF Full Text Request
Related items