Query Optimization for Distributed Spatio-Temporal Sensing Data Processing

Abstract

The unprecedented development of Internet of Things (IoT) technology produces humongous amounts of spatio-temporal sensing data with various geometry types. However, processing such datasets is often challenging due to high-dimensional sensor data geometry characteristics, complex anomalistic spatial regions, unique query patterns, and so on. Timely and efficient spatio-temporal querying significantly improves the accuracy and intelligence of processing sensing data. Most existing query algorithms show their lack of supporting spatio-temporal queries and irregular spatial areas. In this paper, we propose two spatio-temporal query optimization algorithms based on SpatialHadoop to improve the efficiency of query spatio-temporal sensing data: (1) spatio-temporal polygon range query (STPRQ), which aims to find all records from a polygonal location in a time interval; (2) spatio-temporal k nearest neighbors query (STkNNQ), which directly searches the query point’s k closest neighbors. To optimize the STkNNQ algorithm, we further propose an adaptive iterative range optimization algorithm (AIRO), which can optimize the iterative range of the algorithm according to the query time range and avoid querying irrelevant data partitions. Finally, extensive experiments based on trajectory datasets demonstrate that our proposed query algorithms can significantly improve query performance over baseline algorithms and shorten response time by 81% and 35.6%, respectively.

Keywords

• spatio-temporal sensing data
• spatio-temporal data processing
• spatio-temporal index
• polygon range query algorithm
• <i>k</i> nearest neighbor query algorithm
• query optimization