Spatial query processing and data mining methods for location based services
Shashi Shekhar, Jin Soung Yoo · 2007
Mobile devices such as cell-phones and PDAs are increasingly being used with the advance of location sensing, wireless networks and mobile computing. They enable the deployment of location-based and context-aware services. This thesis is concerned with exploring spatial query processing and data mining methods for supporting location-based services. The first part defines the In-Route Nearest Neighbor (IRNN) problem, and proposes query processing methods. An IRNN is defined as an interest object via which the detour from the original route on the way to the destination is smallest. It is of interest to a user with a strong preference for a specific route. The IRNN search presents challenges due to its expensive road distance function and complex query object which considers a predefined route, the current location and the travel direction. This work explores both Euclidean geometric and graph-theoretical computation structures to restrict the search region. The remaining part of the thesis explores data mining methods which are useful to extract interest knowledge for supporting location-based services. First, co-location pattern mining methods are described. A co-location represents the presence of two or more spatial events located at significantly close distances from each other. A mobile service provider may be interested in service patterns frequently requested in a neighboring area for location-based advertisements and recommendations. Co-location pattern mining involves computational challenges since spatial objects are embedded in a continuous space and share a variety of spatial relationships. This work explores efficient co-location mining methods without compromising the correctness and completeness of the results. The second area of data mining presented here focuses on discovering co-located event sets whose spatial prevalence variations are similar with a reference sequence of interest. For example, mobile service providers may be interested in the effect on service requests by the variation of their advertisements. Mining co-evolving spatial event patterns is computationally challenging due to usually large number of temporal points, the need for a composite interest measure of spatial prevalence values over time and similarity search. This work defines the co-evolving spatial event pattern and explores the mining algorithm.