Venus: Scalable Real-Time Spatial Queries on Microblogs with Adaptive Load Shedding

Abstract

Microblogging services have become among the most popular services on the web in the last few years. This led to significant increase in data size, speed, and applications. This paper presents <i>Venus</i> ; a system that supports real-time spatial queries on microblogs. <i>Venus</i> supports its queries on a spatial boundary <inline-formula><tex-math notation="LaTeX">$R$</tex-math></inline-formula> and a temporal boundary <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> , from which only the top- <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> microblogs are returned in the query answer based on a spatio-temporal ranking function. Supporting such queries requires <i>Venus</i> to digest hundreds of millions of real-time microblogs in main-memory with high rates, yet, it provides low query responses and efficient memory utilization. To this end, <i>Venus</i> employs: (1) an efficient in-memory spatio-temporal index that digests high rates of incoming microblogs in real time, (2) a scalable query processor that prune the search space, <inline-formula><tex-math notation="LaTeX">$R$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> , effectively to provide low query latency on millions of items in real time, and (3) a group of memory optimization techniques that provide system administrators with different options to save significant memory resources while keeping the query accuracy almost perfect. <i>Venus</i> memory optimization techniques make use of the local arrival rates of microblogs to smartly shed microblogs that are old enough not to contribute to any query answer. In addition, <i>Venus</i> can adaptively, in real time, adjust its load shedding based on both the spatial distribution and the parameters of incoming query loads. All <i>Venus</i> components can accommodate different spatial and temporal ranking functions that are able to capture the importance of each dimension differently depending on the applications requirements. Extensive experimental results based on real Twitter data and actual locations of Bing search queries show that <i>Venus</i> supports high arrival rates of up to 64 K microblogs/second and average query latency of 4 msec.