Research On Spatial Pattern Matching For Spatial Data

With the popularity of mobile terminals,such as mobile phones,tablets,etc.,and the widespread use of location sensors,positioning and navigation systems,a large amount of spatial data with geographic location information has been generated as long as huge demand for location-based services.Location-based services,such as the navi-gation service provided by Baidu Map and the service of searching the closest restaurant provided by Dianping has brought convenience to the users.How to use spatial query technology to store and analyze massive spatial data,and ultimately support users' in-creasingly personalized and diverse query requirements,and how to implement efficient spatial keyword query are very important.Common spatial keyword queries are divided into range queries and nearest neigh-bor queries.Although these two types of queries have brought a lot of conveniences,there is still a problem with these two types of queries:the user intent cannot be ac-curately captured.For example,the existing spatial keyword query algorithm cannot handle the demand of setting relationships between different objects,nor can it handle the demand of setting different distance intervals between any two objects.To solve the problem,this paper focuses on how to process spatial pattern match queries.The main work of this paper is as follows:(1)We improve the existing query models that we use a spatial pattern to model the query restrictions.Notice that a spatial pattern is a graph,where each vertex corre-sponds to an object with a keyword attached,and each edge is augmented with a spatial distance relationship.For the same paper,this paper uses the existing spatial query mCK algorithm and the SPM algorithm designed in this paper to find the matches.Comparing these matches,we can see that the spatial pattern can capture and meet the user's needs more accurately.(2)The algorithms for graph pattern matching problem is adapted to perform spa-tial pattern matching.And the MSJ algorithm is designed based on the idea of multi way join.MSJ simplifies the distance relationships in the pattern using dynamic pro-gramming and further optimizes by using pruning strategy.Experiments have shown that the MSJ algorithm is more efficient.(3)Considering that when the spatial pattern specified by the user is loose,there are too many matches are returned that it can be a burden for users to choose,this paper designs an evaluation function to evaluate the quality of different matches,and a fast sorting algorithm IncMatch is proposed.IncMatch is an incremental-search algorithm and can return the best matches without finding all matches.(4)Considering that when the pattern is so restricting that none matches can be found,this paper introduces the concept of maximal feasible sub-pattern to evaluate the matching degree.This paper also proposes two algorithms,APM algorithm,and MPM algorithm,based on Aporiori and MARGIN respectively to find maximal feasible sub-patterns and then find best partial matches.