Towards Efficient Framework for Time-Aware Spatial Keyword Queries on Road Networks

摘要

The spatial keyword query takes as inputs a query location and a set of query keywords and returns the answer objects by considering both their spatial distances to the query location and textual similarity with the query keywords. However, temporal information plays an important role in the spatial keyword query (where there is, to our knowledge, no prior work considering temporal information of the objects), since objects are not always valid. For instance, visitors may plan their trips according to the opening hours of attractions. Moreover, in real-life applications, objects are located on a predefined road network, and the spatial proximity of two objects is measured by the shortest path distance or travelling time between them. In this article, we study the problem of time-aware spatial keyword (TSK) query, which assumes that objects are located on the road network, and finds the k objects satisfying users' spatio-temporal description and textual constraint. We first present the pruning strategy and algorithm based on an existing index. Then, we design an efficient index structure called TG index and propose several algorithms using the TG index that can prune the search space with both spatio-temporal and textual information simultaneously. Further, we show that the TG index technique can also be applied to improve the performance of time-travel text search and spatial keyword query. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness and efficiency of the presented index and algorithms.