Advanced spatial queries with textual and social components

Abstract

The emerging new services for GPS and mobile users have developed applications that access and exploit spatial objects with new components (e.g. text and social network). Web objects, including blogs, tweets, photos and videos, are embedded into a map by the APIs of map service providers, where textual messages are associated with geographic information. Location-based social networking services, arising from Facebook and Foursquare, allow users to browse and share their traces of locations among the social networks. Among this class of applications, the highlight is that the retrieved spatial objects (e.g. points of interest and moving users) are featured with new components. Integrating such new components into the spatial query processing has produced large amounts of promising results. However, handling new components along with the retrieval of spatial objects increases the complexity of such joint query processing significantly. Thus, management over data from such multiple domains has been received considerable attention from database research community.

In this thesis, we introduce three interesting problems and study their sophisticated solutions for processing spatial objects with new components: (i) category-aware optimal route query (CORQ), (ii) social and spatial ranking query (SSRQ), and (iii) efficient notification of meeting point (ENMP) query. Our results for (i) and (ii) facilitate the retrieval of spatial objects from multiple domains while our solutions for (iii) provide effective tools for synchronous management of multiple moving users from a social network. Category-aware optimal route queries (CORQ) are generalized from the traveling salesman problem and enable users to retrieve shortest routes covering selected categories. Social and spatial ranking queries (SSRQ) are relevant to spatial object recommendations using social information and allow users to obtain the spatial objects that not only are near their locations but also impress them with high social influence. Efficient notification of meeting point (ENMP) queries are variants of aggregate nearest neighbor queries and provide real-time rearrangement for multiple moving users according to their locations.

Query processing in such multiple domains is complicated due to the mixture of domain information and their integration within one search. Naïve algorithms for these problems incur either numerous expensive evaluations or massive communication cost, which render them inapplicable to large datasets. Our main research purpose is to design efficient and effective solutions for the proposed problems, that avoid the aforementioned shortcomings of naïve algorithms.