Stream Kriging: Incremental and recursive ordinary Kriging over spatiotemporal data streams

• Published in: Computers & geosciences 2016-05, Vol.90, p.134-143
• Main Authors: Zhong, Xu, Kealy, Allison, Duckham, Matt
• Format: Article
• Language: English
• Subjects: Incremental ordinary Kriging; Online algorithms; Recursive ordinary Kriging; Spatial interpolation; Spatiotemporal stream processing
• ISSN: 0098-3004; 1873-7803
• DOI: 10.1016/j.cageo.2016.03.004

Ordinary Kriging is widely used for geospatial interpolation and estimation. Due to the O(n3) time complexity of solving the system of linear equations, ordinary Kriging for a large set of source points is computationally intensive. Conducting real-time Kriging interpolation over continuously varying spatiotemporal data streams can therefore be especially challenging. This paper develops and tests two new strategies for improving the performance of an ordinary Kriging interpolator adapted to a stream-processing environment. These strategies rely on the expectation that, over time, source data points will frequently refer to the same spatial locations (for example, where static sensor nodes are generating repeated observations of a dynamic field). First, an incremental strategy improves efficiency in cases where a relatively small proportion of previously processed spatial locations are absent from the source points at any given iteration. Second, a recursive strategy improves efficiency in cases where there is substantial set overlap between the sets of spatial locations of source points at the current and previous iterations. These two strategies are evaluated in terms of their computational efficiency in comparison to ordinary Kriging algorithm. The results show that these two strategies can reduce the time taken to perform the interpolation by up to 90%, and approach average-case time complexity of O(n2) when most but not all source points refer to the same locations over time. By combining the approaches developed in this paper with existing heuristic ordinary Kriging algorithms, the conclusions indicate how further efficiency gains could potentially be accrued. The work ultimately contributes to the development of online ordinary Kriging interpolation algorithms, capable of real-time spatial interpolation with large streaming data sets. •Developed an incremental ordinary Kriging algorithm over spatiotemporal data streams.•Developed a recursive ordinary Kriging algorithm over spatiotemporal data streams.•Evaluated our algorithms on a commercial, off-the-shelf stream processing platform.•Discussed the extensions to general applications and further efficiency gains.