In a world where the volume of available trajectory data is constantly increasing, the need for eficient storage and processing of such data has motivated the development of numerous applications and analysis methods. Diferent analysis methods require the trajectory data to be in specific data representations. At the same time, in order to eficiently process complex trajectory queries, multiple representations are necessary. However, current systems focus on a single data representation for trajectories. In this paper, we present the research outline of a Ph.D. in its early stages, where we plan to propose an algebra and a corresponding set of logical and physical operators to support complex trajectory queries by considering diferent trajectory data representations. Furthermore, we propose to design a demonstrator system as proof of concept.
sequently, these systems are ill-suited to efectively and
eficiently answer what we refer to as complex trajectory
Due to technological advances in the last decades that led queries, i.e., queries that involve a combination of
operato the ubiquity of cheap GPS sensors, there is an abun- tions that require or benefit from trajectory data being
dance of trajectory data available. As a result, the eficient represented in diferent forms (e.g., spatial and temporal).
processing and analysis of trajectory data have attracted We give a brief summary of the state of the art in
significant interest[
When processing or analyzing trajectories, the tra- and (b) provides operators to translate between jectory’s representation can significantly impact which trajectory data representations (Section 3.3). operations can be applied or how eficiently they can be 3. Design a query processor that supports complex executed. For example, geographic operations are best trajectory queries (Section 3.4). processed on a trajectory represented as a spatial object, In order to demonstrate the validity of our approach, while others, e.g., temporal operations, need trajecto- we plan to implement a proof-of-concept demonstrator ries represented as time-series. Apart from these spatial (Section 4). Concluding remarks are given in Section 5. and temporal trajectory properties, some applications require processing and analysis of semantic information attributed to a (sub-sequence of a) trajectory. 2. State of the Art
While several systems have been proposed to manage
trajectory data, they tend to only focus on and priori- To the best of our knowledge, no systems currently
tize one of the representations mentioned above. Con- support diferent representations of trajectories.
Polystores [
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License of existing DBMS focused on trajectories. Systems such
1 hCPWrEooUrctkReshtdoinpgpssIhStpN:/c1e:6u1r3-w/-0s.o7r3g/wACwttErwibUu.teRioxnWc4..0uoInnrtekir-nskahtoioonnpaslt(PCaCrnoBzYc.e4d.0ee).d/cinogllsec(tCivEeU-Rbe-WhaSv.ioorugr)/ as Secondo [
A trajectory is defined as = (, ), where is the spatiotemporal structure of the trajectory, deifned as a sequence of (point, timestamp)-tuples = ⟨(1, 1), . . . , (, )⟩ with = (, ) and 1 ≤ ≤ . Each component of the trajectory can have attributes with values from a domain , given by the function : × → , where is an (open or closed) interval over and is the set of attributes. Note that for reasons of simplicity, we assume that overlapping intervals do not share common attribute names. As special cases, the interval [1, ] denotes the entire trajectory, [, + 1] is a single edge, and [, ] is a single point.
Trajectories defined by this conceptual model can be
represented in diferent data models. Figure 2 illustrates
some possible representations of the trajectories shown
in Figure 1. More specifically, Figure 2a shows a mapping
of our definition into the relational model, where a table
is used to store the structure of the trajectory. Logical
models of this nature are employed in existing trajectory
management systems [
Instead of a relational model, trajectories can be
represented by a set of sequences (cf. column-based [
Another option is to extract a graph representation
from trajectories [
Furthermore, it is possible to look at a trajectory as a
time-series (cf. Figure 2d) and use time-series analysis
either on the trajectory itself or on an aggregation, e.g.,
travel distance or speed. Liu et al. [
literature review of the current state of the art [
There are several options for designing a physical data
model employed by existing database systems that can
be used to store trajectory data in our system, which
can be beneficial for diferent operations. For instance,
the row-based storage approach of traditional relational
database systems is beneficial to query entire trajectories
or filtering them based on their attribute values. A
graphbased storage benefits queries that depend on regular
path expression. Finally, the column-oriented storage of
column stores and time-series database systems favors
operations that prioritize analyzing a single aspect of
trajectories. Apart from database systems that focus on
a single physical model, we will also investigate
polystores [
Finally, another well-known option from existing database systems is using index structures to enable different access paths. For example, a B+Tree index provides sorted access to a relational table. In the same way, an index could represent a relational table as a time-series, or another could represent a time-series as a spatial object. Therefore, we will also investigate how clustered, and unclustered indexes can be employed to render the need for a fixed physical data model obsolete.
Based on the findings from the literature review in Subsection 3.2, we identify the need for handling complex trajectory queries on a logical level. Consider the following query : "find all trajectories which pass through a region during a time interval ." Following a filterand-refine strategy to process , we can apply multiple id 1 . . . 1 2 . . . 2 x 3.5. Query Optimizer the given trajectory data, another representation should be obtained using a transformation operator. For the temporal part of , the data can be transformed into a time-series representation before applying the temporal query operator. operators: (a) a spatial operator to find all trajectories that pass through , and (b) a temporal operator to find all trajectories that were recorded during . While we can process with these two operators, we can also derive a third operator, which checks whether the timestamps of specific sample points of each trajectory lie within during . This spatiotemporal operator can use specialized algorithms that consider spatial and temporal aspects at the same time, similar to a join in relational databases.
The first two operators can be applied in any order and aim at reducing the search space, while the third operator verifies the correctness of the result. Following the traditional approach of database systems, we will develop an algebra with logical operators that can be combined to represent any complex trajectory query.
There are multiple ways to combine query and
transformation operators to evaluate a given query. For instance,
one could directly apply a query operator over an already
materialized representation or perform a transformation
on the fly from one representation to another and use a
query operator over the new representation. As physical
operators have diferent costs depending on the operator
type, the representation method, and the cardinalities
3.4. Query Processing of the data, we will devise a cost model from them in
order to build an optimizer that can generate execution
Complex trajectory queries combine parameters for dif- plans. Our optimizer will be based on the Cascades
Frameferent representations. Consider query from Subsec- work [
Physical operators can be divided into two categories: mation procedure is expensive and the representation is query operators and transformation operators. Query op- needed multiple times. erators evaluate the query. In the case of , they evaluate the spatial and temporal parameters. Transformation operators convert the trajectory data from one represen- 4. Proof of Concept tation to another (see Figure 2). Note that both query and transformation operators can benefit from index structures.
For the physical operators, it is essential on which representation they are applied. Not all query operators work with all representations. Some combinations of operators and representations are less eficient, and some are impossible (e.g., extracting the position from a time series). For the spatial part of , we need to check for all trajectories if they intersect the given region. The intersection can be checked eficiently with the geometric representation using an R-Tree index. If the query operator is incompatible with the current representation of
concept, to demonstrate for the concepts shown in this
paper. It is used to evaluate results from Section 3.3 &
Section 3.4 empirically. Chameleon acts as an adapter
layer between the user and a trajectory data source.
Chameleon ofers an API to query trajectory data based
on spatial, temporal, and additional rich features. The
API has diferent methods for each trajectory
representation, meaning the user receives the data in the format
that they need, e.g., as a sequence of tuples or as a
relational table. It can be used with a combination of data
sources for diferent representations. e.g., spatiotemporal
DBMS (e.g., Secondo [
The system architecture of Chameleon will consist of three layers: operations layer, query processing layer, and data storage layer, as shown in Figure 3.
• The operations layer of Chameleon ofers an API that a user can interact with. The API is in the form of diferent methods for diferent kinds of operators to pose queries to the system. This layer is also responsible for returning the query result to the user. • The query processing layer is responsible for the generation of execution plans. Furthermore, it determines which data representations to transform and which to materialize. • The data storage layer contains the physical transformation operators and the access methods for the underlying data sources. It supports multiple data sources, e.g., CSV, shapefiles, etc.
In this paper, we have proposed a system to improve the management and processing of complex trajectory queries. By considering the diverse representations for trajectories, we can process all the parts of a complex query with the optimal methods. To build an eficient execution plan, we can use the extensive advancements of query optimization. Furthermore, we proposed to develop a proof of concept to evaluate the results of our system with real-world data.
schaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC 2117 – 422037984.