  Many applications need to process massive streams of spatio-textual data in
real-time against continuous spatio-textual queries. For example, in
location-aware ad targeting publish/subscribe systems, it is required to
disseminate millions of ads and promotions to millions of users based on the
locations and textual profiles of users. In this paper, we study indexing of
continuous spatio-textual queries. There exist several related spatio-textual
indexes that typically integrate a spatial index with a textual index. However,
these indexes usually have a high demand for main-memory and assume that the
entire vocabulary of keywords is known in advance. Also, these indexes do not
successfully capture the variations in the frequencies of keywords across
different spatial regions and treat frequent and infrequent keywords in the
same way. Moreover, existing indexes do not adapt to the changes in workload
over space and time. For example, some keywords may be trending at certain
times in certain locations and this may change as time passes. This affects the
indexing and searching performance of existing indexes significantly. In this
paper, we introduce FAST, a Frequency-Aware Spatio-Textual index for continuous
spatio-textual queries. FAST is a main-memory index that requires up to one
third of the memory needed by the state-of-the-art index. FAST does not assume
prior knowledge of the entire vocabulary of indexed objects. FAST adaptively
accounts for the difference in the frequencies of keywords within their
corresponding spatial regions to automatically choose the best indexing
approach that optimizes the insertion and search times. Extensive experimental
evaluation using real and synthetic datasets demonstrates that FAST is up to 3x
faster in search time and 5x faster in insertion time than the state-of-the-art
indexes.

Databases