Approximate Indexing for Top-k Queries over Massive Spatio-textual Data Streams

The proliferation of smartphones and location-based social networks yield workloads where sets of points of interest are updated according to streaming spatio-textual objects and are queried simultaneously according to their spatial and textual attributes. While indexing is needed to enable efficient querying, the magnitude of updates in such settings call for new indexing techniques. Targeting such settings, we study the problem of approximate top-k spatio-textual object retrieval, the idea being to achieve improved query, update, and space performance by sacrificing query quality only slightly. Specifically, we propose an indexing technique for points of interests in streaming settings that integrates sketching along with a series of optimization techniques. An experimental study demonstrates that our technique achieves over 88% accuracy and 1–2 orders of magnitude lower query times and storage sizes than existing indexing techniques.