John C. Whittier successfully defends PhD thesis

On April 27 2018, J.C. Whittier successfully defended his PhD thesis titled “Towards an efficient, scalable stream query operator framework for representing and analyzing continuous spatio-temporal fields”. Congratulations, J.C.!

Towards an efficient, scalable stream query operator framework for representing and analyzing continuous spatio-temporal fields

John C. Whittier

Advisor: Dr. Silvia Nittel

Advancements in sensor technology have made it less expensive to deploy massive numbers of sensors to observe continuous geographic phenomena at high sample rates and stream live sensor observations. However, this has raised new challenges since sensor streams have pushed beyond the limits of traditional geo-sensor data management technology. Data stream engines (DSE) provide facilities for near real-time processing of streams, however, algorithms supporting representing and analyzing spatio-temporal phenomena are limited.

This dissertation investigates near real-time representation and analysis of continuous spatio-temporal phenomena observed by large numbers of mobile, asynchronous sensors using a DSE and introduces two stream query operator frameworks. The STI-QOP framework transforms sensor streams of an spatio-temporal phenomenon into a stream of spatio-temporal continuous representations of the phenomenon using a novel set of stream query operators to perform spatio-temporal inverse distance weighting (ST IDW) interpolation. A key component of the STI-QOP framework is the main-memory-based Sliding Window Spatio-Temporal Grid Index that allows to perform efficient spatio-temporal insertion and deletion of massive sensor data streams through Time Block-based partitioning of the 3D grid. This index supports fast search for relevant sample points during ST-IDW interpolation via space-time Isotrophic Time Cells. The Cylindrical Shell List Template and the Nested Shell List Template are introduced as reusable, shell-based templates for expansion of search in the Sliding Window Spatio-Temporal Grid Index. Shells are used by the parallel, stream-based ST-IDW algorithms ST Shell and ST k-Shell that interpolate individual grid cells. Secondly, the proposed STI-QOP framework evaluates value predicates over spatio-temporal streams of ST continuous phenomena and produces a stream of spatio-temporal snapshots of predicate result regions. The Region-Growing, Tile-based, and Phenomenon-Aware algorithms are proposed that reduce computational time and accurately produce predicate results regions based on seed points.

The performance of the proposed frameworks was assessed with regard to accuracy of results and throughput. The STI-QOP framework achieves a processing throughput of 100,000 tuples/s, able to process of 250,000 observations in 2.5 seconds with an NRMSE under 0.19 using a 500 x500 grid. The STP-QOP framework is able to processes over 250,000 observations in 0.2 seconds for a predicate result covering 28% of the observation area.