Frequency-Aware Indexing for Spatio-Textual Data Streams

Several applications process continuous spatio-textual queries over massive streams of spatio-textual data in real-time, e.g., location-aware ad targeting systems. These queries exhibit several challenges. Besides the fact that the vocabulary of the keywords can be enormous, the frequencies of the keywords can vary across different spatial regions, and can also change over time. This makes the task of adaptively indexing the keywords according to changes in workload – over space and time – very challenging. This paper introduces FAST, a F requency- A ware S patio- T extual index for continuous spatio-textual queries. Unlike existing indexing techniques, FAST does not assume prior knowledge of the entire vocabulary, and adaptively accounts for the variance in the frequencies of keywords across spatial regions. FAST supports continuous spatio-textual range queries and is extended to FASTkNN to support continuous spatio-textual k-nearest neighbor queries. When FAST is compared against state-of-the-art indexes, extensive experimental evaluation using real and synthetic datasets demonstrates up to 3x improvement in performance of spatio-textual range queries as well as 4x improvement in performance of spatio-textual k-nearest neighbor queries. These performance improvements are achieved while using only one third of the memory required by state-of-the-art indexes.