Efficient Processing of Spatial Keyword Queries

Abstract

Massive amount of data that are geo-tagged and associated with text information are being generated at an unprecedented scale in many emerging applications such as location based services and social networks. Due to their importance, a large body of work has focused on efficiently computing various spatial keyword queries. In this thesis, we investigate three important problems on spatial keyword search: 1) Top-k Boolean spatial keyword query, 2) Diversified spatial keyword search query on road network, and 3) Top-k temporal spatial keyword. We aim to provide efficient solutions for these queries under various setting. Below is a brief description of our contributions.

To facilitate the top-k spatial keyword query, we propose a novel index structure, namely IL-Quadtree, to organize the spatio-textual objects. An efficient algorithm is developed to support the top k spatial keyword search by taking advantage of the IL-Quadtree. We further propose a classification based method to enhance the effectiveness of the signature of linear quadtree. We show that IL-Quadtree can also efficiently extend to support spatial keyword batch query, the direction-aware top k spatial keyword search, and spatial keyword ranking query. Comprehensive experiments on real and synthetic datasets demonstrate the effectiveness and efficiency of our methods.

We are the first to study the diversified spatial keyword search on road network. We develop an efficient signature-based inverted indexing technique as well as an efficient incremental network expansion algorithm for spatial keyword search on road networks. An effective incremental diversified spatial keyword search algorithm is proposed based on the spatial keyword pruning and diversity based pruning techniques. The experimental results also demonstrate that the proposed approach is effectiveness and efficiency.

We are the first to study the top-k temporal spatial keyword query which considers three important constraints during the search including time, spatial proximity and textual relevance. We develop a novel index structure, namely SSG-tree, to efficiently insert/delete spatio-temporal web objects with high rates. Base on SSG-tree an efficient algorithm is developed to support top-k temporal spatial keyword query. A novel signature, namely combination signature, is presented by further improve the performance of SSG-tree by reducing combination error.