Predictive analytics over mobility data is a domain that has received a lot of attention by the research community the past few years and encapsulates a wide range of sub-problems aiming to predict e.g. the future location of a moving object, the future trajectory of a moving object, the trafic flow, the expected time of arrival of a moving object to its destination etc.. These are all quite challenging problems from their nature and what makes them even more challenging is the massive production of mobility data, which sets some limitations over training such predictive models. In this paper we propose Pythia, a framework able to predict simultaneously, the exact future location of an extremely large set of moving objects, given a look-ahead time, by employing massive historical mobility patterns. In order to achieve this we build a predictor for each moving object, in the form of a directed acyclic graph, by taking into account not only its past movement but also collective historical patterns. Our experimental study shows that our approach can predict accurately the future location of moving objects in an eficient way.
The propagation of GPS-enabled devices that has been observed during the recent years has led to an unprecedented rate of mobility data generation which in turn has posed new challenges in terms of storage, querying, analytics and knowledge extraction out of such data. The explosion of mobility data generation has led the research community to devise new interesting methods to analyse them. One of these directions is predictive analytics over mobility data, which aims at the utilization of historical data in order to predict future behavioural patterns and trends. An important operation with a wide range of applications, such as collision detection, trafic estimation and service recommendation, is future location prediction (FLP). What is even more challenging is how to deal with this problem in the Big Data era, where new positions arrive at frequent rates and the accumulated ones scale to petabytes of data, and in application scenarios where latency and scalability matter.
Inspired by the above, in this paper we propose Pythia , a framework able to predict simultaneously, in real-time, the exact future location of an extremely large set of moving objects, given a look-ahead time, by employing historical mobility patterns. In order to achieve this we adopt a hybrid approach, where we build a predictor for each moving object by taking into account not only its individual past movement but also collective historical patterns. By doing so, we increase the predictive ability of our system, meaning that the amount of cases where our system can make a prediction is significantly increased, as compared to only using the individual history of each moving object. Furthermore, the accuracy of our systems predictions is increased, as compared to only using collective historical patterns, since individual moving objects tend to follow the same routes.
Clearly, solving the above problem is quite challenging, since one has to take into account not only the inherent complexity of the FLP problem but also the challenges posed by the Big Data era, in terms of volume and velocity of the incoming data. In more detail, the problem can be broken down in an Ofline and a Query module. The Ofline part is responsible for identifying patterns of movement, either individual or collective, while the Query part is responsible for predicting the future location of a moving object, given a look-ahead time and the set of patterns that were identified during the Ofline module.
Several eforts try to deal with this problem by applying
spatial discretization and generalization and then try to find
frequent locations or sequences of locations ([
Furthermore, all of the above approaches are centralized
and do not scale with the size of today’s trajectory data,
which calls for parallel and distributed algorithms in order
to address the FLP problem in a scalable and eficient way.
Towards this direction, [
Our main contributions are the following: • We propose an eficient and scalable tailor-made prediction-oriented subtrajectory pattern extraction technique. • We propose a distributed pattern network reconstruction technique. These networks have the potential to serve as predictors for other predictive analytics, such as trajectory prediction and ETA. • We perform an experimental study, where the efectiveness of the proposed algorithms is evaluated.
The rest of the paper is organized as follows. In Section 2 we provide an overview of the relevant literature. Subsequently, in Section 3 we introduce some preliminaries and provide the problem definition. In Section 4 we present our proposed solution to the problem of distributed patternbased future location prediction and in Section 5, we present the results of our experimental study. Finally, in Section 6 we conclude the paper and discuss about the future work.
The fact that the FLP problem has been thoroughly
studied brings up its importance and applicability in a wide
range of applications. There are several studies in the past
that dealt with the FLP problem that can be categorized
in some groups. There is a group of studies that adopt a
time series analyses approach [
A diferent way of addressing the FLP problem includes
machine learning approaches. [
Another interesting viewpoint is to take advantage of
historical movement patterns in order to predict the
future location. There are several approaches that use either
collective-only patterns [
To deal with this, there is a group of clustering methods
[
In this section we are going to provide some preliminary definitions. In more detail, given a set of trajectories moving in the xy-plane, Definition 1. (Trajectory) A trajectory ∈ is a sequence of timestamped locations {1, . . . , }. Each = (, , ) represents the -th sampled point, ∈ 1, . . . , of trajectory , where denotes the length of (i.e. the number of points it consists of). The pair (, ) and denote the 2D location in the xy-plane and the time coordinate of point respectively.
Definition 2. (Subtrajectory) A subtrajectory , ∈ ∈ is a subsequence {, . . . , } of which represents the movement of the object between and where < . Definition 3. (Distance) Further, let (, ) denote the spatial distance between two points , , which is defined as the Euclidean distance in this paper, even though other distance functions are also applicable. Also, let (, ) denote the temporal distance, defined as |. − .|.
Regarding the similarity between (sub)trajectories, in this
paper we chose to employ the Longest Common
Subsequence (LCSS) for trajectories, as defined in [
(||, ||) (1) where (, ) is a pair of matched points and || (||) is the length of ( respectively). Moreover, it holds that (, ) = (, ).
The goal of this module is to identify frequent patterns of movement that will maximize the prediction accuracy and the predictive ability of our system. The desired properties that a prediction-oriented (sub)trajectory pattern extraction algorithm should hold are the following: Discovering patterns of subtrajectories. As argued in Section 1, this will enable us to identify more patterns, which would be otherwise “lost”.
Spatiotemporal pattern extraction. It is of great importance for the task of prediction to discover patterns that take into account time, hence implicitly the speed. Clusters with small spatial extent. In order for the predictions to be more accurate, the identified patterns should represent groups of objects that are not spatially dispersed. Obviously, this, rules out a large number of approaches that perform density-based clustering which might lead to spatially extended clusters through expansion.
Coverage. In order to increase the predictive ability, the identified patterns need not to be concentrated in a specific region, but to cover the datasets extent as much as possible. “Dead ends” minimization. As already mentioned in Section 1, due to the fact that subtrajectory patterns are patterns that are valid for smaller portions of the trajectories lifespan, this might lead to stumbling into “dead ends”, which leads to decreased look-ahead prediction ability.
Distributed. In order for this solution to be able to extract patterns from big trajectory data, parallel and distributed algorithms need to be utilized.
O A (c)
O A (d)
D
Our approach towards building a framework that meets with the aforementioned specifications can be split into four sub-problems. To help us, let us consider the following example.
Example 1. Figure 1 illustrates six trajectories moving in the xy-plane, where each one of them has a diferent origindestination pair. More specifically, these pairs are → , → , → , → , → and → . The goal of a subtrajectory pattern extraction method is to identify 4 patterns ( → , → , → , → ), as depicted in Figures 1(c).
Problem 1. (Subtrajectory Join) The first step is the so
called subtrajectory join, a well-defined problem in the
literature of mobility data management, where the goal is to
retrieve for each trajectory ∈ , all the moving objects,
with their respective portion of movement, that moved close
enough in space and time with , for at least some time
duration [
Problem 2. (Trajectory Segmentation) The second step
takes as input the result of the first step, which is actually a
trajectory and its neighboring trajectories and aims at
segmenting each ∈ into a set of subtrajectories. The way that a
trajectory is segmented into subtrajectories is
neighbourhoodaware, meaning that a trajectory will be segmented every
time the density of its neighbourhood changes significantly.
In this paper, we are going to adopt the approach followed
in [
Problem 3. (Subtrajectory Pattern Extraction) Given
the output of Problem 1, applying a trajectory segmentation
algorithm for the trajectories will result in a new set of
subtrajectories ′. The third step takes as input ′ and the
goal is to identify a set of “representative” subtrajectories
(patterns), whose cardinality is unknown. More specifically, let
= {1, . . . , } denote the set of “representatives”, where
is the number of the identified patterns. Actually, the
problem can be viewed as a subtrajectory sampling problem, where
the goal is, given ′, to select the most “representative”
subset of subtrajectories, in terms not only of the number of
subtrajectories that are represented but also to cover the entire
extent of ′ as much as possible. Towards this direction, we
employ the work presented in [
Here, (a) actually guarantees the large coverage of by allowing a subtrajectory to be added in if it is dissimilar with the already existing members of and (b) ensures that ′ is maximally represented given the restrictions imposed by (a). Figure 1(c) depicts the four identified patterns, namely → , → , → and → , of Example 1.
Finally, the fourth step takes as input the set of identified patterns and aims at constructing a spatiotemporal directed graph = (, ), where is a set of vertices and is a set of edges, that represents a network of movement through which a moving object can be routed. At this point, we should mention that is a set of spatiotemporal points and is a set of subtrajectories, as defined in Definition 2. By this, we can minimize the number of “dead ends” and increase the look-ahead prediction ability.
Due to the hybrid nature of out system, there is the possibility that an individual pattern might be identical with a collective pattern. Furthermore, a pattern might be the continuation of another pattern, irrespective of whether they are individual or collective. Hence, an algorithm that takes as input a set of patterns and tries to construct a directed graph, would have to perform a series of “merge” and “append” operations. More specifically, a “merge” operation between two patterns ′ and ′ takes place if ′ is an individual pattern and ′ a collective one (or vice-versa) and (′, ′) > , where is a similarity threshold. Moreover, an “append” operation two patterns ′ and ′ takes place if 0 ≤ ′1. − ′ . ≤ ∧ (′1, ′ ) ≤ or vice-versa, where ′1 is the first point of ′ and ′ is the last point of ′. The spatiotemporal gap that might arise between ′ and ′1 gets filled by the shortest path between these two points when the underlying network of movement is known or by linearly interpolating in any other case. This can be considered as the “connection edge” between the two patterns. Finally, can be constructed by considering as vertices all the initial and ending points of the patterns and as edges all the resulting patterns along with the connection edges. Figure 1(d) illustrates the reconstructed pattern network, given the patterns of Figure 1(c).
Problem 4. (Pattern Network Reconstruction) Given a set of patterns , a spatial threshold , a temporal tolerance and a similarity threshold , construct a spatiotemporal directed graph = (, ) after performing all the appropriate “merge” and “append” operations.
In this paper, we address the challenging problem of prediction-oriented subtrajectory pattern network extraction in a distributed setting, where the dataset is distributed across diferent nodes, and centralized processing is prohibitively expensive.
Problem 5. (Distributed Subtrajectory Pattern Network Extraction) Given a distributed set of trajectories, = ∪=1, where is the number of partitions of , perform the prediction-oriented subtrajectory pattern extraction task in a parallel manner.
Actually, Problem 5 can be broken down to solving Problems 1, 2, 3 and 4 (in that order) in a parallel/distributed way. Finally, the Future Location Prediction problem can be defined as follows: Definition 5. (Future Location Prediction) Given a desired look-ahead time , a pattern network and the recent positions {− +1, . . . , } of moving object , where, is the latest reported position, predict the position of at . + .
The Pythia framework consists of the distributed subtrajectory pattern network extraction (D-SPaNE) and the Prediction component, as illustrated in Figure 2. The D-SPaNE component is responsible for extracting the subtrajectory pattern networks in a distributed manner, given a large set of accumulated historical data. The Prediction component receives the k-recent positions of a trajectory and the look-ahead time for each moving object, it retrieves its corresponding hybrid pattern network, “matches” its recent history on the network and routes through it until it finds the future location of the moving object at the desired look-ahead time .
Concerning the D-SPaNE component, it consists of a distributed storage file system, such as HDFS, which contains accumulated historical mobility data and D-SPaNE itself, which takes as input a distributed trajectory dataset from the distributed file system and constructs a set of hybrid subtrajectory pattern networks = { 1, . . . , }, where is the number of moving objects. As already mentioned, the term hybrid indicates that we build a predictor for each moving object by taking into account both its individual past movement and collective historical patterns. Algorithm 1 − () 1: Input: 2: Output: set of subtrajectory pattern networks 3: Preprocessing: Align and Repartition D;
4: for each partition ∈ ∪=1 do 5: perform Point-level Join; 6: group by Trajectory; 7: for each Trajectory ∈ do 8: perform Subtrajectory Join; 9: perform Trajectory Segmentation; 10: group by ; 11: perform Pattern Extraction ∀ ; 12: perform Refine Results ; 13: group by Trajectory; 14: for each Trajectory ∈ do 15: perform Network Reconstruction 16: return ;
An overview of D-SPaNE is presented in Algorithm 1. In more detail, initially, we temporally Align the first points of each trajectory starting at = 0, in such a way that the temporal dimension depicts the duration since the start of a trajectory, and then Repartition the data into equi-sized, temporally-sorted temporal partitions (files), which are going to be used as input for the join algorithm in order to perform the subtrajectory join in a distributed way (line 3). Note that this is actually a preprocessing step that only needs to take place once for each dataset . However, it is essential as it enables load balancing, by addressing the issue of temporal skewness in the input data. Subsequently, for each partition ∈ ∪=1 and for each trajectory we Prediction Component
tpred k-recent positions
retrieve D-SPaNE Component
Distributed Storage Historical
Data + Pattern Network match
FLP discover parts of other trajectories that moved close enough in space and time (line 5). Successively, we group by trajectory in order to perform the subtrajectory join (line 8). At this phase, since our data is already grouped by trajectory, we also perform trajectory segmentation in order to split each trajectory to subtrajectories (line 9). In turn, we utilize the temporal partitions created during the Repartition phase and re-group the data by temporal partition. For each ∈ ∪=1 we perform the pattern extraction procedure (line 11). At this point we should mention that if a subtrajectory intersects the borders of multiple partitions, then it is replicated in all of them. This will result in having duplicate and possibly contradicting results. For this reason, as a ifnal step, we treat this case by utilizing the Refine Results procedure (line 12). We should also mention that lines 5-12, will be executed twice, once for identifying collective and once for individual patterns. The actual diference between the two executions lies at the Point-level Join (line 5), where during the extraction of collective patterns, we discover for each trajectory parts of other trajectories that moved close enough in space and time that belong to diferent moving objects, while during the extraction of individual patterns, they need to belong to the same moving object. Finally, we perform the Network Reconstruction (line 15) procedure by grouping the identified individual patterns by trajectory, hence each processing node receives one such group, while we distribute the global patterns to all of the processing nodes. Finally, the set is emitted.
Clearly, tackling the above problem is quite challenging
in a distributed setting. For this reason, we outline a
solution that follows the popular MapReduce paradigm. Figure 3
illustrates the D-SPaNE algorithm in terms of MapReduce.
Up to the Refine Results step we employ the distributed
solutions presented in [
Regarding the Network Reconstruction, the goal is to take as input the set of individual and collective patterns, identified by the previous step, and construct a set of directed graphs = { 1, . . . }, where is the number of moving objects and = (, ) corresponds to the graph of the i-th moving object. As already mentioned in Section 3, the network reconstruction algorithm, will have to perform, a series of “merge” and “append” operations, as depicted in Figure 4 and at the same time calculate the “weight” of each edge and reconstruct the network. Algorithm 2 describes the network reconstruction procedure. Algorithm 2 () 1: Input: 2: Output: set of networks 3: for each moving object do 4: for each pattern ∈ do 5: ℎ(); 6: = + ; 7: for each element ∈ do 8: if . − > . then 9: − ← ; 10: = − ; 11: else 12: if is individual ∧ is collective then 13: if (, ) ≥ then 14: = − ; 15: else if is individual ∧ is collective then 16: if (, ) ≥ then 17: = − ; 18: if . > . then 19: if (., .) ≤ then 20: − {← ., .}); 21: − ← ; 22: return ;
In order to achieve this, for each pattern , we calculate its “weight” and add it in a new set (lines 4-6). The “weight” of each pattern is calculated by taking into account both the voting () of each pattern (i.e. support) and whether is an individual pattern or not. In more detail, Split 1 Data [t1-εt,t2+εt) Split 2 Data [t2-εt,t3+εt) . .
.
Split P Data [tP-1-εt,tP+εt)
Map Split 1 Join(⋈) Split 2 Join(⋈) . .
Split P Join(⋈) where is a boolean that equals to 1 if is an individual pattern and 0 otherwise and () is the normalized voting (support). In this way, edges that correspond to individual and/or highly “voted” patterns take values “closer” to zero and thus become more likely to be traversed by a routing algorithm. We should remind here that the patterns arrive in each reducer sorted by , as illustrated in Figure 3. Subsequently, for each other pattern in , we examine whether . − > .. If this is the case, it means that the end of is so far in the past that is impossible for to participate in any future “merge” or “append” operations, as depicted in Figure 4(a). For this reason, we add to the final set and remove it from (lines 7-10). Otherwise, we examine if is an individual and a collective pattern or vice versa. If so, we calculate their similarity and if (, ) ≥ then we merge the two patterns by keeping in only the individual one (lines 1217), as delineated in Figure 4(b). Further, we investigate if . > .. In case this is true, this indicates that an “append” operation might take place, hence we further examine if (., .) ≤ and if this is also true then perform the “append” operation by adding the “connection edge” {., .} into (lines 18-20), as illustrated in Figure 4(c).When, all patterns are traversed, then gets flushed to and finally, after all moving objects get processed is returned (lines 21- 22).
Regarding the Prediction component, it receives the most recent positions of moving objects and the goal is to predict its future location at the given look-ahead time . This is done in a straightforward way, as depicted in Figure 2, by retrieving the corresponding subtrajectory pattern network, matching its -most recent positions on the network and predict its future location at the given look-ahead time . In case there are multiple candidate positions to be returned, we retrieve the one that there is actually a path between the current position and the candidate destination on the network. Finally, in case we have multiple candidate destinations where a path exists, we select the one with the shortest path, according to the edge weights (Equation 2) that we have assigned.
In this section, we present some preliminary findings. The experiments were conducted in a 49 node Hadoop 2.7.2 cluster. The master node consists of 8 CPU cores, 8 GB of RAM and 60 GB of HDD while each slave node is comprised of 4 CPU cores, 4 GB of RAM and 60 GB of HDD.
For our experimental study, we employed a real and a synthetic dataset. Concerning the real dataset, we used a dataset from the urban domain of 1 week duration , called VFI1, consisting of 25019834 records. Furthermore, we utilized a synthetic dataset in order to verify that our solution operates as anticipated, given a dataset with a known ground truth.
In more detail, the synthetic dataset (SMOD) consists of an object which has performed 400 trips (trajectories) and is used for the ground truth verification. The scenario of the synthetic dataset is the following: the object moves upon a simple graph that consists of the following destination nodes (points) with coordinates: A(0,0), B(1,0), C(4,0) and D(2,1), illustrated in Figure 5(a). Half of the times the object moves with normal speed (2 units per second) and another half moves with high speed (5 units per second). When an object arrives at a node, it ends its trajectory with a 1This private dataset was kindly provided by Vodafone Innovus (a) (b) (c) (d) probability of 15%. Finally, there is 1% of the trajectories that follow a random movement in space (other than these roads) with a speed that is updated randomly.
Our experimental methodology is as follows: Initially, we verify that our solution operates as anticipated by applying it to a dataset with a known ground truth. Subsequently, we evaluate the quality of the predictions by varying the lookahead time and measuring the accuracy of the predictions in terms of MAE. Finally, we measure the performance by varying the look-ahead time and measuring the latency.
In order to verify the correctness of our solution we utilized the aforementioned SMOD dataset. To begin with, we are going to verify that the pattern extraction component of our solution operates as anticipated. In more detail, the ground truth of the patterns that are hidden in SMOD can be inferred by the description of the dataset itself. In particular, eight clusters of subtrajectories need to be identified. The following Table lists the eight clusters along with their spatial (2nd column) and temporal projection (3rd column).
#1, #2 #3, #4 #5, #6 #7 #8
→ → → → →
[0, 0.2], [0.2, 0.7] [0.2, 0.8], [0.7, 1.2] [0.2, 0.52], [0.7, 1.2] [0.8, 1] [0.52, 1]
Indeed, the pattern extraction module discovers these eight clusters, as illustrated in Figure 5(b). The next step is the network reconstruction component, where the goal is to construct a directed graph from the subtrajectory patterns. The challenge here is to restore the connectivity of movement of the specific objects by applying “stitches” when appropriate. In more detail, Figure 5(c) illustrates the edges (each pattern is an edge) of the graph before the graph reconstruction procedure and Figure 5(d) depicts the constructed graph, where the applied “stitches” are in black colour.
Quality of the predictions. At this point we have veriifed that the ofline component functions as expected. Regarding the accuracy of the predictions over the synthetic dataset we performed a set of experiments where we vary the look-ahead time and measure the Mean Average Error (MAE) of the predictions. In more detail, Figure 6(a) shows that the accuracy achieved is high, considering that the dataset diameter is approximately 500 meters and the look-ahead time ranges from 5%-30% of the dataset duration (each trajectory ‘lives” for 100 seconds). Furthermore, as anticipated the larger the look-ahead time, the larger the MAE between the predictions and the actual positions. Regarding the VFI dataset, as depicted in Figure 6(c), the findings regarding the behaviour of MAE w.r.t. the look-ahead time are equivalent, the larger the MAE between the predictions and the actual positions.
Performance. Finally, we investigate the performance of our solution in terms of latency (i.e. how much time it takes to make a prediction). Initially, we utilized the SMOD dataset and measured the latency of our solution. Figure 6(b) presents our findings, where we can observe that our system, for the majority of the cases, can make a prediction at about 1 millisecond. In addition to that, we can see that the look-ahead time does not afect the processing time per prediction. We run the same set of experiments, but this time for the VFI dataset. As expected, the findings are again similar, which demonstrates the capability of our solution to handle large volumes of data in timely fashion. Figure 6(d) presents our findings, where we can observe that our system, for the majority of the cases, can make a prediction at about 1 millisecond.
In this paper, we presented Pythia, a big data framework
able to predict the exact future location of an extremely
large set of moving objects, given a look-ahead time, by
employing massive historical mobility patterns. Our
preliminary results demonstrate the potential of our proposal. As
for future work, we aim perform a more in-depth
experimental study, utilizing more datasets and comparing with
the state of the art. Furthermore we plan to evaluate the
performance of the D-SPaNE component, even though we
anticipate to follow the performance of the work presented
in [
This work was supported in part by the Horizon Europe research and innovation programme under grant agreements 101070416 (Green.Dat.AI) and 101093051 (EMERALDS) funded by the European Union.