Hot spot analysis is the problem of identifying statistically significant spatial clusters and is typically applied on point data. The aim of this paper is to discover hot spots in an urban environment, namely road segments with statistically significant amount of trafic congestion, using massive GPS data of moving objects. To this end, we adjust the Getis-Ord index for hot spot discovery to become applicable for road networks. Then, we propose two data-parallel algorithms for hot spot discovery in road networks implemented in Apache Spark; an exact algorithm that has scalability limitations for very large data sets, and a scalable approximate algorithm that balances between performance and accuracy. We provide experiments over a large real-life data set that indicate the salient features of our approach.
In recent years, the analysis of mobility data has drawn the attention of both the academic society and the industry. Tracking of moving objects on road networks is ubiquitous in fleet management applications and can support diverse scenarios of urban planning, more eficient transportation, reduction of greenhouse gas emissions, and improvement of life quality. Due to the technological evolution of GPS sensors and their integration in mobile devices and cars, it is possible to collect vast amounts of spatio-temporal data. Thus, our work is motivated by the need for identifying trafic congestion from GPS data on the road network.
In this paper, we present an approach for identifying trafic hot spots, using big trajectory data collected by GPS sensors. Through hot spot analysis, we aim to identify road segments with statistically significant high levels of trafic congestion. This means that we do not just aim to identify road segments that have high congestion values; such road segments may be of interest, but they are not necessarily statistically significant. Instead, a hot spot is statistically significant if it has high congestion value but additionally is surrounded by other segments with high congestion values.
For this purpose, we employ the Getis-Ord Statistic index, a popular metric for hot spot analysis, which – to the best of our knowledge – has so far been used for spatial and spatiotemporal data of objects with free movement. Instead, we adapt the Getis-Ord index to become applicable for graphs that represent the road network, such as the ones obtainable via OpenStreetMap. Moreover, to handle the temporal dimension, we consider diferent temporal snapshots of the road network whose duration is user-defined according to the application requirements. Efectively, we have multiple snapshots of the same graph, each corresponding to the same road network but for a diferent time interval and thus each road segment has diferent trafic congestion values. In this way, we formulate the problem of hot spot discovery in road networks using a model that consists of a sequence of temporal snapshots of the same graph (road network).
Computing the hot spots using this model is a processingintensive operation, which relies on difusion of information over (parts of) the graphs. Moreover, the necessary data to infer trafic congestion on roads may be in the order of millions of GPS records per temporal interval. Therefore, we need to design scalable algorithms for hot spot analysis by exploiting big data technologies. To this end, we introduce two data-parallel algorithms for hot spot discovery in road networks, with a goal to be applicable for massive trajectory data sets. The first algorithm returns the exact result, but faces performance limitations for really large data sets due to the underlying exchange of information between pairs of edges. Then, we present an approximate algorithm with a cut-of threshold for excluding edges that are located too far away spatially or temporally, as their contribution to hot spot discovery is minimal. It turns out that our approximate algorithm provides an interesting trade-of between scalability and accuracy, returning hot spots that are very similar to ones discovered by the exact algorithm but orders of magnitude faster.
In summary, we make the following contributions: • We formulate the problem of hot spot analysis in road networks, by the means of Getis-Ord Statistic, appropriately tailored for graphs. • We design and implement an exact algorithm in
Apache Spark that computes hot spots in parallel. • We present a scalable approximate algorithm that discovers hot spots of high accuracy but significantly faster. • We evaluate the performance and scalability of our algorithms for diferent parameters, using a real-life data set from the Metropolitan Area of Athens.
The rest of this paper is structured as follows: Section 2 reviews related research eforts. Section 3 formulates the problem under discussion. In Section 4, we present our approach for hot spot analysis over road networks, while in Section 5 we present the parallel algorithms for detecting hot spots. Then, in Section 6 describes the results of our evaluation, while in Section 7, we conclude the paper. Existing works in hot spot analysis over mobility data can be broadly classified in two categories: (a) point-based hot spot analysis, where mobility data consist of individual spatial or spatio-temporal points, and (b) trajectory-based hot spot analysis, where sequences of spatio-temporal points that belong to the same user/vehicle/vessel (i.e., trajectories) are considered. As our work belongs to the latter category, we briefly review point-based approaches and put our main focus on trajectory-based approaches.
Eftelioglu et al. [
=1 , − ∑︀ √︂ [ ∑︀ =1 2, − (∑︀=1 , )2] − 1 (1) where is the attribute value for cell , , is the spatial weight between cell and , is equal to the total number of cells, and and represent the mean and standard deviation respectively: = ∑︀ =1 = √︃ ∑︀ =1 2 In our work, we adapt the Getis-Ord statistic to be applicable on graphs representing temporal snapshots of road networks. The attribute can be any indicator of trafic congestion, such as the average speed or the number of vehicles per time unit.
The proposed approaches of [
In their studies, Häsner et al. [
Sacharidis et al. [
Our work difers from these approaches as we consider road segments as candidate hot spots and adapt a wellknown hot spot index to be applicable on temporal graphs that represent the road network for diferent temporal intervals. In this way, we capture the efect of spatial and temporal proximity of neighboring congested road segments. This is a diferentiating factor compared to related works that operate over trajectories, as they produce hot spots at diferent level of granularity (e.g., routes, paths, grid cells) and using other metrics. To the best of our knowledge ours is the first work that shows how to apply hot spot analysis via Getis-Ord in road networks.
We consider a directed graph (, ) that represents the road network, where an edge ∈ corresponds to a road segment and is defined by two vertices , ′ ∈ , which represent crossroads. The edge is directed, indicating the lfow of movement on the road network from to ′. We use the terms edge and road segment interchangeably.
To model the efect of time on trafic congestion, we consider a sequence = {1, 2, . . . , } of temporal snapshots of the graph , where each snapshot corresponds to a pre-defined temporal duration . A snapshot corresponds to an interval [, +1) of duration , i.e., +1 − = . For example, if is set to 5 minutes, one such interval could be 9:00 am – 9:05 am. A temporal snapshot of the graph is used to represent the trafic for the specific time interval [, +1). Fig. 1 illustrates the concept of temporal snapshots of a graph that represents the road network.
The problem of hot spot analysis addressed in this work is to identify statistically significant road segments that indicate hot spots, due to trafic congestion. An edge at snapshot , denoted ∈ (), where () represents the edges of the snapshot , is associated with an attribute value that indicates trafic congestion on during the temporal interval of . As such, whether an edge is considered hot spot is a function of the edge’s attribute value , but also of other neighboring edges’ attribute values. By neighboring edges, we mean both spatially (nearby edges on the graph ) and temporally (edges at previous/next temporal snapshots).
To express this dependence on neighboring edges, we
adjust a commonly used function, namely the Getis-Ord
statistic [
The weight (),() between two edges (edge at snapshot ) and (edge at snapshot ) indicates the influence of edge to edge . Intuitively, if a road segment is congested, this also afects other road segments in its vicinity. More precisely, in this paper, we assume that if a road segment is congested, this afects (or will afect in the near future) the previous road segments, i.e., those leading to . For example, in Fig. 1 (left), the edge 3 (in red color) is afected by the weights of edges 4, 5 and 6 (in blue color), whereas all other weights are considered equal to zero (3)(1) = (3)(2) = 0 .
Moreover, when considering diferent temporal snapshots of the graph , the congestion of edges in snapshot +1 afect edges of previous and next temporal snapshots {. . . , +2, , − 1, . . . }. In Fig. 1 (right), edge 3 at snapshot is afected by edges 3, . . . , 6 at .
According to the above, the problem of hot spot analysis in road networks is to identify the most statistically significant road segments (edges) according to the Getis-Ord statistic and can be formally stated as follows.
Problem 1. (Hot spot analysis in road networks) Given a sequence of temporal snapshots of a directed graph (, ) representing the road network, find the top- edges of based on the Getis-Ord statistic *, such that: * ≥ *, ∀ ∈ , ∈ (⋃︀=1 ()) − .
Intuitively, for each road segment we compute a value that indicates if it is a hot spot. This value depends on the trafic congestion of the road segment itself, but also on the trafic congestion of subsequent road segments (as congestion is propagated backwards). Moreover, it depends on the trafic congestion of these road segments in the next temporal snapshots of the network, as illustrated in Fig. 1.
The novelty of our work lies in the identification of hot spots in road networks using a statistically significant metric. In contrast, existing works (Section 2) either use ad-hoc ways to compute hot spots or compute statistically significant hot spots as 2D/3D cells of predefined size. Adapting the Getis-Ord statistic to become applicable for graphs is the main technical contribution of our work. The challenge relates to the definition of neighboring edges over multiple temporal snapshots of the same graph.
This section presents our approach for hot spot analysis in road networks. The input is a data set of GPS records, each corresponding to a specific vehicle (based on identifier vehID), a timestamp , as well as the longitude and latitude values. Also, a graph (, ) is available that represents the road network, which consists of road segments, their geometry, as well as additional information, such as direction, speed limit, etc. Such a graph can be typically obtained from external sources, such as OpenStreetMap.
Data collected from GPS sensors typically contain small
errors, thereby making the mapping of GPS coordinates to
the underlying road network hard. This problem is typically
solved by applying a map-matching algorithm, which is
responsible for mapping each pair of GPS coordinates
(longitude, latitude) to another point located on the road network.
Several sophisticated algorithms for map-matching have
been developed, such as [
As the problem of map-matching is orthogonal to the one we are trying to solve, we adopt a simplistic approach where each pair of GPS coordinates is assigned to the nearest edge. In this way, each GPS record is enriched with an edge (road segment) of the graph, the coordinates of the two points that define the road segment, its length, as well as with other available information such as the speed limit.
In order to compute the Getis-Ord value of an edge , the
ifrst step is to compute the edge’s attribute value , an
indicator of trafic congestion. This is computed as the
average value of contributions from each vehicle that reported
its position on during the timespan of . In the same
spirit as in [
− where is the length of the edge, and () is the entry (exit) time. Unfortunately, for a vehicle that provides its position on edge (after map-matching), we do not know the exact entry and exit time. Therefore, we estimate these values, in particular given two successive positions we compute the entry time as follows: 2 − 1 = 1 + 1 · 1 + 2 where 1 and 2 correspond to the two timestamps, while 1 and 2 are the distances of the two points from the entry node, as shown in Fig. 2. In this way, we can estimate the entry/exit times for each edge.
Given two edges and , where precedes on graph
, the weight (),() indicates the influence of trafic
congestion of edge to edge . The weight is a function
of the distance between the edges, as an edge that is
in close proximity with , has a stronger efect on ’s
congestion in comparison with another edge ′ that is
further away. As in [
(),() is the spatial distance and
(),() the temporal distance. The spatial distance (),() is measured as the number of edges between and on graph . The temporal distance is the diference between temporal snapshots, e.g., edges at snapshots and +1 have temporal distance equal to 1.
In this section, we present two data-parallel algorithms designed and implemented in Apache Spark that compute hot spots over very-large collections of GPS records in a scalable way. The first algorithm is an exact algorithm, whereas the second computes approximate results but with high accuracy and much faster.
In Apache Spark, the main data structure is the
DataFrame, and its predecessor the RDD (Resilient
Distributed Dataset) [
In the pre-processing phase, we perform map-matching (see Section 4.1) and we split the data of each vehicle in a set of trajectories. For each vehicle, we create a new trajectory when we observe a temporal gap of in the timestamps of reported positions. The value of is a parameter that depends on the sampling rate of the data set at hand.
As a result, the output of the pre-processing phase is a
set of records in the following format: (vehID, trajID, , ,
, , length, speed, , ′), where each GPS record (vehID,
, , ) of the original data set is enriched with information
Algorithm 1 Computation of trafic congestion on edges
Algorithm 2 Computation of Getis-Ord index
1: Input: The result of pre-processing: inputfile,
number of Apache Spark partitions , temporal parameters:
, , ,
2: Output: RDD[(,),]
3: function
4: dataRDD = sc.load(inputfile)
5: attrRDD = dataRDD.groupByKey().
6: mapValues(sort_grouped_values).
7: lfatMap (lambda group: calc_attribute_value(group,
, , , )).
8: partitionBy( , lambda k: hash_partitioner).
9: mapValues(lambda x: (x,1)).
10: reduceByKey(lambda x, y: (x[0] + y[0], x[
The main stages of our algorithm are summarized below: • Stage 1: A set of transformations and aggregations is applied to the input data set to assign a trafic congestion value to each edge . • Stage 2: The road network is represented in the form of a graph and the mean value () and standard deviation () of the trafic congestion variable are computed. This data is assigned to a broadcast variable in order to become available to all the nodes of the cluster. • Stage 3: The * z-score for each edge is computed. • Stage 4: The results of the previous step are filtered for a level of confidence and the top- edges with the highest * z-score are selected.
It should be noted that stages 1 and 3 are the time-consuming steps, therefore we delve into their details next. Stage 3 is the dominant cost, while stage 1 practically involves reading data from disk, but it is still much lower than the cost of stage 3.
Algorithm 1 describes how the trafic congestion values are computed (i.e., stage 1). First, we create an RDD of keyvalue pairs (known as PairRDD) with trajID as key (groupByKey, line 5) and value the records that correspond to this trajectory in sorted temporal order (mapValues, line 5). Then, for subsequent edges of each trajectory we compute the congestion value per vehicle per edge (using function calc_attribute_value()) and we create a new PairRDD with a composite key that consists of the edge and the temporal snapshot, while the value is the congestion value (flatMap, line 7). Subsequently, we partition the records based on edge using hash partitioning (line 8). In other words, all records that have been mapped to the -th edge at snapshot are assigned to the same partition. This allows the computation of the average congestion value per edge based 1: Input: The attrRDD: RDD[(,),], number of Apache Spark partitions , temporal parameters: , , , , bandwidth ℎ, output of stage 2: , , 2: Output: RDD[(,),*] 3: function 4: GetisOrdRDD = attrRDD.flatMap (lambda x : GetisOrd
Calculations(x, , , , , ℎ, , , ))).
5: partitionBy( , lambda k: hash_partitioner).
6: reduceByKey(lambda x, y: (x[0] + y[0], x[
Then, in stage 2, we compute the aggregate values necessary for the computation of Getid-Ord. These include the mean , the standard deviation , and the total number of edges for all temporal snapshots of the graph . This information together with the graph is broadcast to all worker nodes in the cluster, so as to be available during the computation of Getis-Ord.
In stage 3, we compute the Getis-Ord index * per edge and temporal snapshot . Algorithm 2 provides the pseudocode for the computation of Getis-Ord values. First, using flatMap (line 4), we transform attrRDD into a new RDD with key the edge and value a triple:
(),(), (2),(), (),() that corresponds to another edge . This computation is performed by function GetisOrdCalculations(), which takes into account neighboring edges to the current edge and computes their contribution to in terms of weight, squared weight and weight times attribute value, which are the basic constituent parts for computing Getis-Ord. Notice that this function takes as parameters the information about temporal snapshots, the kernel’s bandwidth ℎ, as well the broadcast data. Then, we perform hash partitioning based on edge in order to accumulate all records that correspond the same edge for the same timestamp (line 5), in order to compute the aggregate values (line 6): || ∑︁ ∑︁ (),() =1 =1 || ∑︁ ∑︁ (2),() =1 =1 || ∑︁ ∑︁ (),() =1 =1 Thereafter, we compute the Getis-Ord value * per edge and per temporal snapshot using function Gi_formula() (line 7).
Finally, in stage 4, the edges are ordered based on the computed Getis-Ord value and only the top- edges are returned. Obviously, is a parameter that is set according to the application requirements. From the analysis of the exact algorithm we can derive useful information about its complexity with respect to the input parameters. We focus on the number of records that need to be processed, as they influence the processing cost.
In Algorithm 1, the size of dataRDD is ( ), where denotes the number of GPS records. Then, the algorithm builds the attrRDD which contains one record per edge per temporal snapshot. If || is used to denote the number of edges of graph (the road network) and denotes the number of temporal snapshots of , then attrRDD contains (|| · ) records. As such, its size is linearly dependent on the size of the road network (in edges) and the number of temporal snapshots.
In Algorithm 2, the attrRDD is given as input and another RDD called GetisOrdRDD is built. For a given temporal snapshot, this contains (||2) records because it combines each edge with its neighboring edges with nonzero congestion value (in worst case with all edges). When other temporal snapshots are considered too, the number of records increases exponentially. Distributing these records and aggregating per edge is the main factor that afects the processing cost of the exact algorithm.
The previous algorithm computes the exact Getis-Ord zscores, but it is computationally expensive because every edge with non-zero congestion value () has an influence on the z-score of all other edges. However, edges at high distance (in spatial or temporal terms) are expected to have extremely small impact on the computed z-score.
Motivated by this observation, we propose the use of an approximate algorithm that takes as input a cut-of threshold , which determines the subset of neighboring edges that will be considered when computing the Getis-Ord values of a given edge. In spatial terms, corresponds to number of hops between two edges. In temporal terms, corresponds to the number of (previous/next) temporal snapshots that should be considered. In this way, we limit the number of records that need to be processed and do not allow this number to increase exponentially. In turn, this drastically reduced number of records that need to be processed makes the algorithm work much faster, at the expense of slightly inaccurate results.
As shown in our experimental study, the approximate algorithm ofers an interesting trade-of between performance and accuracy. Thus, we can compute hot spots with high accuracy but in a much shorter execution time.
Parameters Size of the data set (x106 GPS records) Duration ( ) of temporal snapshots (in hrs) Number of partitions ( ) Cut-of threshold ( ) in hops
We evaluate the performance of our approach for urban hot spot analysis. We implemented both algorithms in PySpark, using Apache Spark 3.1.1 Core API.
Platform. We deployed our code in Google Cloud Platform (GCP). The platform supports the process of big data in Apache Spark. The initiated cluster runs on Debian 10, while we used the version Spark 3.1.1 in Hadoop 3.2.2. The cluster consisted of 4 nodes in total, 1 Master and 3 Workers. Each node has 2vCPU 13GB RAM, 500GB hard drive and 375GB SSD.
Data Set. We employed a real data set of anonymized GPS records collected by a fleet management provider. The data was collected over a a period of five months from July to November 2018, consisting of 368,977 individual vehicle trajectories moving at the Metropolitan Area of Athens in Greece (Fig. 3). This data set is 1.1GB in total size and contains approximately 7.4M (million) GPS records. We also create two subsets of size 5M and 2.5M records. After pre-processing (Section 5.1), each record consists of the ifelds: (vehID, trajID, , , , , length, speed, , ′). Even though the specific data set is sparse and medium-sized, it is still a real-world data set that allows the evaluation of our approach.
Metrics. Our main evaluation metric was the execution time needed for each individual stage of the algorithm to be completed. The execution time is measured in seconds.
Evaluation Methodology. The eficiency of our algorithm was assessed based on four parameters: (a) the size of the data set, (b) the temporal window , which determines the number of temporal snapshots, (c) the number of Apache Spark partitions , and (d) the cut-of threshold , used only by the approximate algorithm (for the exact = ∞), that defines the neighboring edges in the axes of time and space that contribute in Getis-Ord z-score, measured in hops. After diferent tests, we also set the kernel’s bandwidth ℎ = 8 for the exact algorithm, while ℎ = 23 · for the approximate algorithm. Our experimental setup is summarized in Table 1.
Varying the size of the data set. In Fig. 4 (left), we demonstrate the performance of the exact algorithm when increasing the data set size. We measure the time of stage 3, which is the most time-consuming part of the algorithm. As the number of observations to be processed increases from 2.5M to 7.4M, so does the total execution time of the algorithm but not linearly. This is due to the fact that the larger data set implies more temporal snapshots, hence more edges in total, which all need to be processed for the computation of the Getis-Ord value of an edge.
Varying the duration of temporal snapshots. The temporal duration of 24, 48 and 168 hours for a period of five months leads to the generation of 153, 27 and 22 non-empty temporal snapshots respectively. Therefore, the fewer the temporal partitions, the smaller the overall execution time. In Fig. 4 (left) the temporal partitioning that comes from = 48 hrs time window is twice as eficient in terms of execution time as the = 24 hrs time window. The = 168 hrs time window is about seven times more eficient than = 24 hrs, indicating a linear relationship between execution time and temporal duration for the data set of 2.5M and 5M records.
Varying the number of Spark partitions. Fig. 4 (right) shows the total execution time of the exact algorithm and the time of stage 3 for diferent numbers of Spark partitions. The first observation is that the execution time of stage 3 practically determines the overall execution time. Regarding the efect of using a higher number of partitions, this seems to reduce execution time. Using more partitions results in smaller subsets of data to be processed, which require less processing time. However, the reduction is not that big (about 15% when using 120 partitions for = 24hrs).
shows that our approximate algorithm that uses the cut-of threshold can make the discovery of hot spots practically applicable for extremely large data sets.
However, the remaining question is how accurate are the results of the approximate algorithm? Fig. 6 shows the hot spots discovered by the approximate and the exact algorithm. This demonstrates visually that the results of the experiment for = 12 are similar to those obtained when applying the exact algorithm.
To complement the visual evaluation, we also performed a quantitative study. We obtained a ranked list of the top100 edges in terms of trafic congestion for = 12 and for the exact algorithm. Then, we computed the Spearman’s rank correlation for these two lists, in order to assess if the same ordering is observed (i.e., if the ranking for = 12 resembles the ranking obtained by the exact algorithm). If the two rankings were identical, we would obtain a value of 1. In our case, we obtained a value of 0.82 for the Spearman’s rank correlation. This indicates that the two lists are highly correlated, or (put diferently) that the hot spots discovered for = 12 are very similar to the ones of discovered by the exact algorithm. In the case of the results using = 6, there is less sensitivity in the recognition of extreme values, while in the case of = 24 there is hypersensitivity resulting in more edges being recognized as hot spots. Our experiments indicate that using a cut-of threshold around = 12 provides a nice trade-of between performance and accuracy.
In this paper, we formulate the problem of hot-spot discovery in road networks. We proposed an exact and an approximate algorithm for hot spot discovery, which are implemented as data-parallel algorithms on top of Apache Spark. Our experiments using a real-life data set indicate that the approximate algorithm provides a viable solution that trades performance for accuracy. In the future, we will apply our algorithms to other real-life data sets of larger scale.
This research has received funding from the European Union’s funded Project EMERALDS under grant agreement no 101093051.