Article Preview
TopIntroduction
Smart cities development and management require real-time processing and analysis of citywide data. Many smart city applications require real-time integration, processing and analysis of spatial stream, for-instance, real-time road traffic analysis, people flow analysis, etc. To support real-time continuous processing of data streams, Continuous Queries (CQs) are used. CQs utilize windows to split the unbounded data streams into finite sets or windows. Precisely, stream tuples arrive continuously, however blocking operators, i.e., aggregation operators, join operator, etc. cannot generate results on an infinite stream. To cope with this problem, windows are used by stream processing engines (Apache Spark Foundation, 2017) (Apache Kafka Foundation, 2018). Windows contain a subset of data streams or in other words bounds the infinite data streams into smaller chunks based on specified criteria to enable the processing of stateful operators. There are mainly two types of windows supported by existing stream processing engines: 1) Time-based window: Groups tuples by time. E.g., Events/Tuples generated in last 24 hours, 2) Count-based window: Groups tuples by count. E.g., A window consisting of recent 1 million tuples. Depending upon how the events are assigned to windows, a window can be classified as sliding or tumbling. 1) Sliding window: A window which slides continuously as the new data arrives or as the time passes. A tuple in sliding window may belong to more than one window, 2) Tumbling window: Tuples are grouped in a single window based on time or count. A tuple in the tumbling window belongs to exactly one window. Besides, different stream processing engines (SPEs) have defined different assigners for different application, for instance, session windows, global windows, etc.
Since the spatial streams contain trajectories of moving objects, bounding the trajectories with respect to time and count is not logical and does not make sense. For instance, consider a moving object, where users are interested in finding the number of traffic signals it has encountered in last x meters. This cannot be done with the help either the count-based or time-based window. Thus, users need a window which can keep track of distance of a moving object and can answer such queries.
Example 1: Assume a mobile platform m scanning a road segment through 3D scanner and generating a stream of 3D spatial data. As the data stream arrives, the user is interested in detecting the different objects (people, cars, trees, etc.) in it and execute continuous queries on it by bounding the stream for a particular length of trajectory. Let the user would like to know the number of different objects detected in last x distance units. Since the speed of m is not uniform, using the existing window semantics, one can obtain the number of objects detected in last t time units however cannot obtain the number of objects detected in last x distance units. The window capable of bounding or tracking the length of trajectory to answer the continuous queries is called the distance-based window.
Keeping in view the importance of the distance-based window, this paper presents a distance-window based approach for the continuous processing of spatial data streams to perform operations on a fixed trajectory length. Since the window operation involves repeated computation, especially in case of sliding window, this work presents two efficient incremental distance-based window approaches, namely ITL (Incremental Trajectory Length) and IDA (Incremental Distance Array).
This paper is an extended version of our earlier work (Salman et al, 2019). In (Salman et al, 2019), authors presented the semantics of a Naive distance-based window. However, the Naive window implementation is too expensive to be practical, hence more efficient and incremental approaches are desired for it. The main contributions of this work can be summarized as follows: