Rapid advances in location-acquisition technologies have led to large amounts of trajectory data. This data is the foundation for a broad spectrum of services driven and improved by trajectory data mining. However, for hybrid transactional and analytical workloads, the storing and processing of rapidly accumulated trajectory data is a non-trivial task. In this paper, we propose an approach to optimize the trajectory data management capabilities for relational database systems. Based on the observations that the relational database structure is well-suited to store trajectory data in the sample point format and that the access patterns for trajectory data change over time, we develope a concept for optimized spatio-temporal data structures for inmemory column stores and describe a workload-aware tiered data compression approach. The first evaluations of the approach demonstrate that the observed data access patterns of di↵erent real-world use cases are supporting the proposed system architecture.
In recent years, rapid advances in location-acquisition
technologies have led to large amounts of time-stamped
location data. Positioning technologies like GPS-based or
communication network-based systems enable the tracking of
various moving objects. This data is the foundation for a
wide spectrum of applications [
The most common format to store trajectory data is the
sample point format. Here, each observed location is stored
as a tuple with the following attributes: trajectory
identifier, moving object identifier, multi-dimensional location,
and timestamp. In trajectory query processing, we
distinguish the four query types: (i) trajectory-based queries, (ii)
spatio-temporal range queries, (iii) KNN queries, and (iv)
top-k queries [
Due to the large amount of trajectory data, which have to be stored in various use cases, we also have to evaluate di↵erent compression mechanisms for trajectory data to reduce the data footprint. Particularly for in-memory databases, we have to utilize the available memory eciently. Additionally, in di↵erent use cases we can observe that a specific trajectory segment is less accessed over time. Also, the query types and granularity of queries, which access a specific segment change over time. Similar characteristics can be observed in time-series data analysis. For that reason, it is necessary to analyze how we can adopt compression mechanisms for such kind of data access patterns to further reduce the memory consumption and increase the performance by minimizing the number of sample points. 2.
In this section, we want to highlight the research aspects, that we derived from the observations mentioned in the previous section. We propose a concept to integrate storage mechanisms for trajectory data into a relational in-memory database with particular attention to leverage the capabilities of the columnar database layout and the adoption to observed data access patterns. The objective is to reduce the data footprint and to better utilize the available memory bandwidth. We accordingly focus on data structures and compression techniques.
1. Optimized temporal and spatial data structures for
columnar in-memory databases: The sample point
format, which is used to store trajectory data by the
majority of spatio-temporal data management systems [
As shown in Figure 1, there are several systems, which
focus on the storage, indexing, and compression of trajectory
data. Various systems were primarily designed to store
spatial data points but they are also used for trajectory data.
With the increased availability of spatio-temporal data
management system were built for di↵erent system
infrastructures, which leverage the specific characteristics of
trajectory data. The optimization focus of the developed system
strongly depends on the addressed use cases: (i) scalability,
(ii) footprint reduction, (iii) elasticity, (iv) eciency, or (v)
query performance [
Although the various systems are designed for di↵erent infrastructures and optimized for di↵erent use cases, similarities in the general structure can be determined and summarized in a general blueprint. Most trajectory data management systems are optimized for spatio-temporal range queries or k-nearest neighbor queries. They use a hybrid partitioning approach to eciently skip data partitions during the query execution. To archive spatio-temporal data locality the data is partitioned by the temporal dimension first and the spatial dimension second. The trajectory of a moving object is not stored together in one partition. The systems divide a trajectory into di↵erent trajectory segments and distribute them on the data partitions on the basis of the partitioning scheme. Inside a data partition, the observed locations are often stored in a sample point data format, whereby the sample points are ordered by the trajectory identifier to increase the performance of trajectory-based queries. To compress the data all systems use delta compression. Additionally, a wide range of systems applies further compression techniques for all data partitions. To optimize the query performance, the trajectory data management systems use a layered index structure. As displayed in Figure 2, the structure consists of a three-level hybrid index. The first layer is a temporal index structure, which divides the temporal dimensions into di↵erent time intervals. There are di↵erent implementations for this index (e.g., skip-list, range index). For each time interval in the first layer, there exists a spatial index. In most cases, the spatial index is represented by a traditional KD-tree, quad-tree or oct-tree. The last layer is normally a tree structure (e.g., b+ tree), which index the di↵erent spatio-temporal partitions.
There are also several systems, which already integrate
data structures to store spatial data and spatio-temporal
data in relational database systems [
In this section, we describe the approach we propose to optimize the capabilities of relational databases to store and process trajectory data. Furthermore, we explain our planned evaluation of the concept. 4.1
The foundation of the proposed approach is the chunk
concept implemented by the relational in-memory research
database Hyrise [
Optimized temporal and spatial data structures for columnar in-memory databases
These capabilities enable the workload-aware selection of
compression techniques. Furthermore, it is possible to adopt
the ordering of data tuples per chunk. For example, if we
assume a workload that consists of mainly trajectory-based
queries on recent trajectories and in contrast mainly
spatiotemproal range queries on past trajectories it would be
beneficial to order the newer chunks by trajectory identifier and
the older ones by location (see Figure 3). Also, space-filling
curves might be used to improve the scan performance of
spatial filter queries. Moreover, this approach allows
adoption to changes in the data distribution or the workload.
Zhang et al. [
Additionally, we developed an approach to store timestamps more eciently in columnar databases to address the previously mentioned problem that the temporal scan performance often dominates the execution time of trajectory database queries. For that reason, we propose a separate columns approach. The values for year, month, day, hour, minute, second, and fractional second are each stored in a separate column. This approach has some advantages over traditional timestamp concepts. Since there are only several possible values for the di↵erent columns, dictionary encoding is e↵ective due to saturated and small dictionaries. Another aspect of reducing the data footprint is that in one chunk only a subset of the di↵erent columns (e.g., minutes or seconds) is modified. For that reason, we could minimize the memory consumption of the unmodified columns by applying run-length encoding. Also, we could improve the bandwidth utilization for temporal scan operations. A disadvantage is that for between queries, it is necessary to scan eventually multiple columns. 4.1.2
Workload-aware tiered data compression
Based on the observation that the data access patterns
for a trajectory segment change over time, we propose a
tiered data compression approach. To select a suitable
compression configuration, detailed knowledge about the data
characteristics and the workload are required. Most
current databases use simple heuristics to choose a
compression scheme for a given column [
Depending on the workload, the determined configuration
defines for each chunk, if the spatio-temporal data should
be stored uncompressed, lossless compressed with a specific
compression algorithm or simplified based on a trajectory
simplification algorithm. Additionally, it should also
specify the compression ratio of the simplification algorithm per
chunk. In general, we expect that recent chunks are
uncompressed or only compressed with lossless compression
techniques. In contrast, the compression ratio increases with the
age of a chunk (see Figure 3). Besides reducing the
memory footprint, the selected configuration has also impact on
the query performance as well as the accuracy of the
results. We see potential to optimize the compression schema
for a given memory budget and error-based application
constraints (e.g., accuracy metrics [
For the evaluations of our approach, we plan to use two
real-world use cases. The first one is in the sports sector
and includes positional information of soccer players during
professional soccer games [
Segment c dictionaryencoded Segment c dictionaryencoded …
Segment d dictionaryencoded Segment d dictionaryencoded data. The trajectory data of other games of a season is not analyzed in that depth. All analyses on data of past seasons are typically only on an event-based level. The second one is a dataset of a transportation network company, which includes several million driver positions per hour. Due to the amount of the collected data, it is only possible to perform analysis on compressed data or subsets of the data. For various use cases (e.g., driver-passenger assignment) only recent data is analyzed. Also, older trajectories might not represent the current trac situation.
In this paper, we have presented our approach to store trajectory data in a relational database system. Based on our observation that data points of trajectories are less frequent accessed over time, we developed a workload-aware tired data compression approach to reduce the data footprint and better utilize the available memory bandwidth. Additionally, we presented an optimized data layout for temporal data in the context of in-memory column stores. The first evaluations of the approach demonstrate that the observed data access patterns of di↵erent real-world use cases are supporting the proposed system architecture. Upcoming tasks include the further analysis of trajectory compression techniques for columnar databases, the implementation of workload-aware metrics to select compression techniques for chunks, assessing the impact of di↵erent configurations and an extensive evaluation with real-world systems.