Indexing Geolocated Time Series Data Full text

Georgios Chatzigeorgakidis, Dimitrios Skoutas, Kostas Patroumpas, Spiros Athanasiou, Spiros Skiadopoulos
25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017)
Abstract. Time series associated with specific locations, such as visitor check-ins or sensor readings, have increased in size and popularity in several domains. Although several works have focused on efficient time series similarity search, there has been limited attention to the inherent challenge that geolocated time series introduce for hybrid queries on both spatial proximity and time series similarity. To efficiently process such queries, we propose a hybrid index, called TSR-tree, which extends the R-tree by introducing appropriate bounds for the time series indexed at each node. This reduces node accesses during query evaluation by simultaneously pruning the search space in the spatial domain and the time series domain while traversing the index. We also present an optimized version, the BTSR-tree, which uses tighter bounds by bundling together similar time series in each node. We describe how these indices can be used to efficiently evaluate different variants of hybrid queries combining spatial and time series filtering or ranking. Finally, we experimentally evaluate our work using real-world datasets from diverse domains, demonstrating a speed-up of 1.5 to 5 times in hybrid query workloads against the baseline R-tree method.