From tweets to urban data sets, there has been an explosion in the volume of textual data that is associated with both temporal and spatial components. Search queries and aggregation queries over these data are computationally expensive. At the same time, exploratory analyses require fast response times so that users can effectively make observations, draw generalizations and generate hypotheses. The challenge of scaling the evaluation of spatio-temporal queries over textual data requires us to rethink how we design algorithms and indexing strategies.

Previous approaches to this problem have focused on the spatial aspect. Some used separate indices for space and text, thus incurring the overhead of storing separate indices and joining their results. Others proposed a combined index that either inserts terms into a spatial structure or adds a spatial structure to an inverted index. These benefit queries with highly-selective constraints that match the primary index structure but have limited effectiveness and pruning power otherwise. For aggregation queries, previous techniques have relied on result pre-computation in order to speed up query processing. This leads to two key limitations: pre-computing the results takes a long time and storing them may require a prohibitively large amount of memory.

In this dissertation, we propose new methods to support interactive evaluation of search and aggregation queries. We propose a new indexing strategy that, by uniformly handling text, space and time in a single structure, is able to efficiently evaluate search queries that combine keywords with spatial and temporal constraints. We present a detailed experimental evaluation using real data sets which shows that not only our index attains substantially lower query processing times, but it can also be constructed in a fraction of the time required by state-of-the-art approaches. To support interactive aggregation queries, we propose KdCloud, which evaluates top-k tag-cloud queries on the fly, without requiring pre-computation. Through a carefully-designed data structure and efficient algorithms that leverage GPUs, these queries are processed at interactive rates even for large datasets. We present a detailed experimental evaluation using real datasets and queries, and show that in addition to fast response times, KdCloud indices have a small memory footprint and can be efficiently constructed.