Incremental χ-shape

Conventional offline spatial algorithms may become bottlenecks for real-time analysis of high-volume and high-velocity spatial data streams. RISER is developing efficient on-line spatial analysis algorithms to process spatial data streams in real-time. Incremental calculation is an effective method to improve computational efficiency and is therefore widely applied in stream processing. For example, Peter and Matt proposed an incremental ordinary Kriging spatial interpolation algorithm which can efficiently interpolate the data from fixed sensor networks.

Peter and Matt are now working on the incremental calculation of the characteristic shape (χ-shape) algorithm. The χ-shape algorithm is an important component of our firefront tracking algorithm. The incremental χ-shape algorithm aims to process a dynamic set of points more efficiently, where both point deletion and insertion can happen. For example, in stream processing, data tuples within a sliding window form such dynamic points set. The figure below demonstrate an example of the changes in the χ-shape resulted from a point insertion (the red circle dot). Two critical features of the χ-shape algorithm: regular-polygon constraint and ordered edge removal make the incremental calculation challenging. Peter successfully addressed this challenge using a dynamic data structure. The algorithm is under efficiency evaluation, and we expect to publish it soon.


Tagged with:
Posted in Activites