Query Processing Techniques For Location Based Services In Road Network

Due to the rapid development of wireless communication technology and unceasing promotion of smart mobile devices,location-based services has been extensively applied to various aspects of people's daily life.More and more diverse query demands come with it.Therefore,several query problems location based services are investigated in this dissertation.At first,the optimal location query in the network,an efficient algorithm is required to help users identify an optimal location where is located in the road segments and categories of facility specified by users,satisfying that the sum of the distances between the desired location and its nearest facilities is minimal.In addition,the optimal path query is studied.Given the starting and ending position,as well as the score function measuring the popularity of the scenery spots,the optimal path query is to figure out an optimal path,which maximizes the function score and satisfying the budget cost.Query demands in different scenarios result in query semantic expressing complexity and diversity.However,the above-mentioned personalized queries under the context of location has not been addressed before.Therefore,it is now imperative to explore the new algorithms to address the above problems,by combining the application scenarios and constraints.Based on the analysis and summary of the state-of-the-art query processing approaches in the Euclidean space and the road network,effective solutions are designed in this dissertation,for the three kinds of query location based services as follows:(?)keyword-aware optimal location query,(?)keyword-aware Point-of-interest query and(?)constraint-based optimal path planning.The contributions are summarized as below:(1)We propose an efficient algorithm for the keyword-aware optimal location query.Given the road segments and categories of the facilities specified by users.The goal is to help users identify an optimal location such that the sum of the distances between the desired location and its nearest facilities is minimal.In detail,each user-specified edge is divided into several segments using the object points on it.An important property for this structure is that the distance sum from a segment to the target objects is a lower-bound determined by its end points.With the help of this property,the query of continuous space can be transformed into the discrete space,and the global optimal location can be obtained from the local optimal locations in whole segments.Moreover,in order to reduce the unnecessary computation of distance,the edge filtering strategy and keyword filtering strategy are explored to develop an efficient algorithm.(2)For queries over objects with multiple types,we propose a novel interesting object searching technique based on keyword-matching,so as to select the object from the target object set interested by users.The goal is the largest distance between the target object and its nearest facilities is minimal.To tackle this problem,we partition the road network into multiple Voronoi Polygon(NVP)based on objects(called generating objects)in each type of object set;then pre-compute the shortest distance between generating object and the boundary point in given NVP,as well as count other types of objects there are and then building the index;query the NVP with respect to the interested type and pruning invalid objects based on types of keywords not included in this NVP and the corresponding lower bound of distances.(3)We propose the approaches for the constraint-based optimal path planning,which is to help users find the path,satisfying the budget cost and maximizing the popularity function score.However,the constraint-based optimal path query is an NP-hardness problem.For smaller scale road network,we propose an exact algorithm planning optimal path query.In detail,two pruning strategies,i.e.,cost-based lower bound and benefit-based upper bound,are employed to prune the invalid paths.On the other hand,two approximate algorithms are proposed for larger scale road network.One is heuristic algorithm,the other is an approximation algorithm with provable approximation bounds.(4)We design and implement the popularity optimal path planning system.Based on algorithms proposed above,an optimal path planning system is designed and implemented.The starting and ending position are specified by the user,as well as a cost function,this system is to figure out an optimal path with the highest scoring sum of popularity function score quickly and effectively.In summary,this dissertation propose three query processing technologies for location based services in road network.The methods proposed in this thesis can effectively deal with the above queries based on theoretical analysis and experimental.