With the wide spread of cheap and mobile GPS sensors as well as mobile data connections, live streams from moving objects are becoming a huge data source. The services based on these data streams, for example, for connected cars, vessels or smartphone users, need real-time results for queries based on the current or even near-future positions of the moving objects. Spatio-temporal data from moving objects cannot just be treated as a crowd of points with timestamps, but must be seen as points in a trajectory with non-measured points in between. In this paper I present my work on the management of such real-time trajectories within a Data Stream Management System (DSMS) to enable simple, exible and e cient in-memory moving object query processing.
Moving objects in the real world are everywhere and have been there for a while: pedestrians and cars on the streets, vessels on the oceans and airplanes in the sky. Comparably new is the huge amount of data these objects are producing. Many of these send their location regularly to a central server or other facility, may it be the smartphone user with a Location-based Service (LBS) or a vessel with an Automatic Identi cation System (AIS) sender.
This data can be used to answer questions and solve realworld problems. For example, vessels can be warned about congested or currently dangerous areas based on their own position as well as the positions of other vessels. As more data can be shared via live-streams and as the results of such queries are required with minimal delay, traditional systems that rst store and then query the data streams are not ideal. They typically run short-term queries on static data sets that are stored on the hard drive.
Data Stream Management Systems (DSMSs) especially target data streams. They o er solutions for many data stream related challenges, provide query languages to de ne queries without the need to write code in a general purpose programming language and simplify the connection to typical data sources. Maintenance of queries on data streams is made simple due to the ease to change and update the query text. Hence, queries can be adapted to new requirements quickly. These features make them a useful tool to easily create and change queries for many di erent use cases and are therefore a good choice for rapid prototyping systems in the eld of data stream processing and analysis.
To cope with the requirements of data streams, DSMSs support continuous queries and use a data-driven approach. New results are incrementally calculated when new data arrives at the system. This increases the demand for quick calculations, wherefore data is typically kept in-memory. Unfortunately, a potentially in nite data stream cannot be hold in-memory. A typical solution DSMSs provide are windows. These reduce the amount of data hold in-memory to a smaller part of the data streams, e. g., all elements from the last hour or the last 100 elements.
Even though DSMSs already tackle lots of the challenges that occur with data stream processing, they lack features necessary to work with moving objects data. Two of these features are (1) continuous location interpolation and nearfuture prediction and (2) fast moving objects index structures for windows with high uctuation. In this work, I concentrate on point data, hence, moving regions are not in the scope. That is because most moving object data of interest today, such as vessels and pedestrians, can be simpli ed to point objects without loosing too much precision in the queries. Moving or evolving regions in contrast introduce a whole new palette of challenges.
One important feature of moving objects data streams is
that the objects move continuously but are only measured
once in a while. Therefore, the objects have unknown
locations in between the measurements, which can and
sometimes need to be used for querying. Imagine a query where
a vessel needs to know all vessels around it. Another vessel,
which last known location is (temporal and spatial) far away
but will probably be within that range on querytime, should
be included in the answer, hence, its location needs to be
automatically predicted to the future by the query. This
scenario is particularly important for satellite AIS where it is
normal to have hours between location updates [
Challenges with this approach are that interpolation and prediction depends on the use case and always comes with an uncertainty. When new data about an interpolated object is available, old query results may need to be updated. When and how to update results by more precise ones is a nontrivial question within a DSMS. To my best knowledge, there is no work that tackles these challenges in the eld of data streams for moving objects.
The second feature mentioned above are moving objects windows and suitable index structures. As not all data can be stored, it needs to be decided which data is still needed for processing and which is not and how and when old data can be wiped. Typical window concepts such as time-based windows can be extended by windows especially for moving objects. A possible window type could be a distance-based window. It would store all data within a certain distance of a single moving object, e. g., the last kilometer of every object. The requirements for the underlying index structures di er both from pure temporal as well as pure spatial index structures. 2.
The overall goal of this work is to create and implement concepts to allow DSMSs to process spatio-temporal data from moving objects. To reach this goal, I am tackling the challenges of including location interpolation and prediction as well as window concepts for moving object data streams. 2.1
Location Interpolation Moving objects naturally move continuously but are only measured once in a while. Within a data stream, they seem to be hopping from point to point, resulting in delayed and possibly wrong results. I aim to introduce location interpolation into the data stream processing to that the objects move continuously in time and space. The interpolation should also be used for short-term location prediction.
Result Uncertainty As prediction always comes with a degree of uncertainty, the results are uncertain as well and can change when new data from a moving objects arrives. The accuracy or uncertainty of a result should be transparent to the user and updates of results should be possible.
Moving Object Windows Window de nitions that are especially useful for moving objects data should be introduced.
Spatio-temporal Indexes The data within the windows need to be hold in spatio-temporal index structures optimized for high data uctuation.
The concepts created to solve the goals should be evaluated by implementing them into an open source DSMS. Scenarios with AIS data from vessels should show that the concepts work with real-world data and queries. 2.2
Typical spatio-temporal queries include neighborhood and range queries. An example query could be \Continuously report all vessels within a range of 10 km around vessel X". Such a query is depicted in Figure 1. The orange vessel in
CCBY-SA2.0, Editors of http://map.openseamap.org/ the middle sent its last location at 12 o'clock and wants to know which vessels are in its range at that point in time. The trajectory of the other vessels one to three are visualized with the arrows and circles. The circles are the measurements where the correct location of the vessel is known. The arrows in between visualize a simple interpolation. It is assumed that the path between the measurements is straight. That is not necessarily the case but it is a reasonable and simple approximation. The dashed lines with the striped circles are predictions of the future trajectory.
The need to interpolate and predict locations arises from the fact that the moving objects do not measure and send their location synchronized with each other, but at di erent time intervals. In the gure, the last known location of the orange vessel in the middle was captured at 12 o'clock. For this point in time, the locations of all other vessels are needed to answer the query correctly. Unfortunately, the known, i. e., measured, locations of the other vessels are not at 12 o'clock, but slightly before or after this point in time. If only the last known location would be used to answer the query, the result would be wrong: Vessel 1 would not be within the result but should be, Vessel 2 would be within the result but should not and the location of Vessel 3 would be wrong.
Hence, interpolation and prediction is necessary to answer the query approximately correct. When doing so, a few challenges arise. The interpolation has to work in an incremental manner with limited knowledge about the data, as not all past data can be stored in a streaming environment. The accuracy of a query result needs to be known to the user or further processing steps. When the prediction was wrong, old results for a query may need to be updated (e. g., if Vessel 1 takes a di erent path than predicted). In a streaming scenario, the approximate result may already be used for further processing or a following result, for example, for 12:03, has already been processed. The questions on how to integrate uncertain results and updates to them within a DSMS need to be tackled. 2.3
Windows are necessary to reduce the in nite data stream to a nite set of data. The data within a window can be kept in-memory and never needs to be permanently written to a hard drive. Next to the performance improvements, the concept of windows has more bene ts. They are based on the assumption that in many cases, queries are only or mostly interested in the current data and not in the data from the distant past. To de ne a window according to the use case, the domain needs to be known. A typical window could, for example, hold all data from the last hour.
In the domain of moving objects, the requirements for
windows can di er depending on the scenario. The de
nition of a window only by the time and not by the space
dimension is often not enough. Imagine, for example, a
window where the speed of all objects within a data stream is
diverse and variable (e. g., slow vessels and fast planes within
one stream). It could be necessary to have from each
object at least the last kilometer within the window. With a
time-based window this would be di cult to achieve.
Additionally, compression could be introduced to moving objects
windows. Patroumpas et al. [
Windows reduce the amount of the required (in-memory) storage space. Nevertheless, it opens up new questions about how to clean up the memory, for example, when to delete old data. This question gets more complicated as window indexes have to be shared between multiple queries. Imagine a data stream of all vessels on the North Sea. As spatial queries can be heavily accelerated when using an index, the data in the windows are indexed. Thereby, due to memory limitations, creating multiple nearly identical indexes must be avoided. Subsequently, one index is shared between multiple queries. Nevertheless, such a sharing makes the decision when to delete old data more complicated, as the window requirements from the queries can be di erent.
Additionally, not every index structure is suitable for a spatio-temporal data stream index. In contrast to more traditional Geographic Information System (GIS) applications, the uctuation in the data is very high. New data needs to be inserted and at the same time old data needs to be removed on a high frequency. It is possible that the whole set of data within a window can be swapped within minutes or even seconds, which, for example, distinguishes the requirements from static time-series data. Traditional indexstructures that require heavy reorganization when data gets changed are probably not suitable for this environment. In this work it needs to be evaluated if index structures for this purpose are useful as it is only an improvement if the indexing needs less time than it saves while querying the data.
In this PhD project I aim to create suitable window concepts, implement them and choosing an e cient index structure for this very dynamic environment.
In this section, the main approaches to overcome the challenges from above are described. 3.1
Query processing on data streams is typically done with operator graphs. The elements of the data stream are send from one operator to the next, each operator doing a speci c task. Joins, projections and selections are typical examples for such operators.
When adding support for moving objects data, this modular architecture should be exploited. New operators can implement the spatio-temporal operations. While doing so, they have to behave like normal operators to the outside so that other operators can seamlessly use the output. Two example operators that are needed are a range and a k nearest neighbors (k NN) operator. Both search for other moving objects close to a certain object. The external behavior of these operators is similar to other operators. They receive stream elements, process them and send their results as stream elements to the next operator.
Internally, these operators need to use location interpolation and prediction to compute correct results and annotate these results with the level of (un)certainty in the meta data of a streaming object. The interpolation should be done by a framework within the DSMS that allows to interchange algorithms, as the interpolation algorithm can change from case to case. 3.2
Currently, prototype versions for moving object range and
k NN queries are available. A prototype implementation
within a DSMS was developed. For spatial querying with
moving object windows, an index structure based on
GeoHashes [
The correct integration of those queries as well as moving object windows is ongoing work. The results are currently only partly usable for other query operators. Interpolating and predicting locations are in the concept phase. Development and implementation of these will be a major part of the future work. 3.3
The concepts that are created in this PhD project will
be implemented into the open source DSMS Odysseus1 [
With that implementation, the feasibility of the concepts will be evaluated. Using an iterative approach, the concepts can be adjusted if uncovered challenges occur while evaluating. The implementation will be used with scenarios in the maritime context, especially with AIS data. An example query could be to continuously query if a vessel is heading to an area that will be congested during its transit.
For the given scenarios with moving objects, timely query results are necessary, wherefore the performance of the solutions will be measured. The latency and throughput of the queries will be used to compare di erent implementations, e. g., di erent approaches for spatio-temporal indexes. 1http://odysseus.offis.uni-oldenburg.de/, last accessed on 03/21/2017 2https://flink.apache.org/, last accessed on 05/24/2017 3https://twitter.github.io/heron/, last accessed on 05/24/2017
General purpose and open source streaming systems such
as Apache Flink and Apache Storm4 as well as
commercial systems such as IBM InfoSphere Streams5 (short: IBM
Streams) o er high performance and distributed stream
processing, but have only limited support for moving objects.
While spatio-temporal data is supported in some systems
(e. g., with IBM Streams [
Zhang et al. [
The open source project GeoMesa6 works with
spatiotemporal data, e. g., from moving objects [
The RxSpatial library [
Interpolation for moving objects is a di cult challenge for
moving regions (e. g., described by Heinz et al. [
Secondo [
Patroumpas et al. [
This paper describes the motivation, challenges and approaches of processing data from moving objects in DSMSs. A major challenge are asynchronous updates of locations of multiple moving objects. To serve timely query results, e. g., for a range query, locations of objects need to be interpolated and predicted. The integration of interpolated values into a DSMS provides some challenges that are tackled with this PhD project. First approaches to solve these are explained. The planned evaluation uses AIS data from vessels for continuous queries. 6.
We thank the Ministry of Science and Culture of Lower Saxony, Germany for supporting us with the graduate school Safe Automation of Maritime Systems (SAMS).