Spatio temporal keyword search for nearest neighbor queries

Abstract

The widespread availability and the technological advancements of geopositioning devices enable users to generate a huge volume of geo-tagged objects everyday. These objects include points of interest (e.g., restaurants), photos, and buying/selling items. To describe such an object, which is commonly referred as a spatial objet, users often use textual information or keywords along with the geographic location of the entity. Based on these geo-tagged objects, a large variety of location based services has been emerged. For example, a user often issues a query like \ nd the Italian restaurant nearest to my location" to a location based service provider (LSP), and the LSP returns the Italian hotel that is nearest to the user’s location as an answer. Due to the popularity of keyword search, this field leads much work on querying spatial keyword (SK) search. However, there are many new applications which require incorporating time along with location and textual information, e.g., \ nd the Italian restaurant nearest to my location which opens at 10pm today". We term this type of query as an spatio-temporal keyword (STK) query. A straightforward way of answering STK queries using existing spatial keyword search technique requires retrieving objects that are not temporally relevant to the query time. To solve this issue, in this paper, we introduce a new index structure that hierarchically organizes time along with location and keywords, and develop an efficient algorithm for processing STK queries. We also extend our work to handle time uncertainty. An extensive experimental study shows the efficiency and effectiveness of our proposed techniques.