This study introduces time-windowed variations of three established trajectory simplification algorithms. These new algorithms are specifically designed to be used in contexts with bandwidth limitations. We present the details of these algorithms and highlight the diferences compared to their classical counterparts. To evaluate their performance, we conduct accuracy assessments for varying sizes of time windows, utilizing two diferent datasets and exploring diferent compression ratios. The accuracies of the proposed algorithms are compared with those of existing methods. Our ifndings demonstrate that, for larger time windows, the enhanced version of the bandwidth-constrained STTrace outperforms other algorithms, with the bandwidth-constrained improved version of Squish also yielding satisfactory results at a lower computational cost. Conversely, for short time windows, only the bandwidth-constrained version of Dead Reckoning remains satisfactory.
During the last decades, the rapid proliferation of mobile
devices equipped with tracking capabilities has led to a surge
in the production of spatio-temporal data. This can be
observed across diverse types of geolocation data sources [
To overcome this dificulty, diferent compression or
simplification algorithms have been proposed [
The main use case motivating compression under bandwidth constraints concerns the extension of AIS signal coverage for maritime monitoring and is detailed in Section 2.1.
Further potential use cases are detailed in Section 2.2.
2.1. Extension of AIS signal coverage
Since 2004, all cargo vessels over 500 GT and all passenger
vessels are required to be equipped with AIS transceivers.
These transceivers allow automatic exchange of information
in between ships and between ships and coastal stations by
broadcasting positional messages using the Self-Organizing
Time Division Multiple Access (SOTDMA) protocol. The
International Telecommunication Union (ITU)
recommendation defines 2 default communication frequencies: AIS
1 (161.975 MHz) and AIS 2 (162.025 MHz) [
Things Another family of use cases for compression under bandwidth constrains could be the tracking of objects over the Internet of Things (IoT). By design, many IoT devices have limited capabilities (battery, bandwidth, ...). Object tracking devices with such limitations could need to compress the trajectories before communicating them to other devices. For such devices, compression is not aimed at but a technical necessity. In this situation BWC algorithms would ofer the necessary compression while minimizing the deterioration of the trajectories. Many situations could be considered. Some examples are given as follows: Animal tracking is more and more used by private pet owners, live stock owners and by scientists. For the latter, compressing trajectories under bandwidth constraints might be necessary to study animals’ behaviors in remote locations where communication capabilities are inherently constrained.
Autonomous fleets: with the recent development of smart cities, the amount of positional information generated is always increasing. Combined with the additional information exchange required, the monitoring of fleets of autonomous vehicles might benefit from bandwidth constrained compression.
In this section, 3 existing algorithms which can be adapted in bandwidth constraint scenarios will be introduced. For all these algorithms, we will consider entities (or targets) for which the position on earth is tracked over time. For each entity , its actual continuous movement over time will be called its real trajectory and denoted by . In practice, this continuous trajectory will be measured at discrete timestamps leading to the generation of the trajectory of , denoted as a time ordered sequence of measurements of ’s position.
The main purpose of the algorithms will be to compress (or simplify) the trajectories into samples (denoted with ∈ {1, ...}). The main purpose of the algorithms will be to compress (or simplify) the trajectories into samples (denoted with ∈ {1, ...}). In this work, we will only consider compression techniques such that the sample obtained by compressing is composed of a subset of the points of . In addition for being important algorithms in the literature, these algorithms have been chosen for the following reason. Both Squish and STTrace are designed to compress trajectories to a predetermined target size which inherently makes them suitable candidates to be adapted in a bandwidth constrained context. DR, on the other hand, is designed to be applied in real time and will be modified to respect bandwidth limitations.
Hereunder, the three classical algorithms will be introduced. For simplicity purposes, Squish and STTrace will be illustrated with a priority queue. It should be noted however that this is done to simplify the algorithms description. Indeed, both methods could be implemented more eficiently without it.
The Squish algorithm has initially been presented in [
Algorithm 1 Pseudocode of the Squish algorithm Require: trajectory , sample size 1: = empty list of points 2: = empty priority queue 3: for in do 4: p.priority = ∞ 5: .append() 6: compute_priority([− 2], ) {s[-2] is the previous point} 7: .add() 8: if .size() > then 9: drop_point_update_priorities(, s) 10: end if 11: end for 12: return {or }
The priority of a point in the sample (line 6) is computed as the Synchronized Euclidian Distance (SED) error introduced in the sample by removing this point. The SED of a point with respect to points and such that: . ≤ . ≤ . represents the distance between the point and its projection ′ which is the position the entity would have at time . if it was moving at constant speed between and . Therefore, (, , ) be computed as follows: (, , ) = (, (, , .)) (2) with the distance between two points being computed as their euclidian distance: (, ) = √︀(. − .)2 + (. − .)2 (3) and with the position at a specicfi time ∈ [., .] (according to a segment between the two other points and ) being defined by: The priority of a point at the position in a sample of size is computed as follows: _([], ) =([ − 1], [], [ + 1]) ∀ = 1, ..., − 1 (6) With the priorities of [0] = [] = ∞ as the first and the last point of the sample will always be kept.
When a new point is added to the sample, the size of the priority queue might exceed the maximum allowed bufer size. In this case, the point with the lowest priority should be dropped (both from the sample and from priority queue) (see line 9). Once a point is dropped, the priority of the "neighbors" of this point should be updated. In order not to recompute the priority of the points, Squish works by increasing the priority of the neighboring points by the priority of the point dropped. By denoting the sample before the dropping of the point [] and ′ the sample after the removal, the priorities of the points which were neighboring [] will be computed as follows: ′[ − 1]. = [ − 1]. + []. ′[]. = [ + 1]. + []. (7) It should be noted that the point following [] has the index + 1 in while it has the index in ′ due to the removal of []. Once the priority of these two points is recomputed, their positions in the priority queue are adapted as well.
It is important to keep in mind that for Squish as well as for all other algorithms presented in this work, when a point is dropped, it is dropped both from the priority queue and from the sample it belongs to.
The STTrace algorithm was initially presented in [
It is very similar to Squish except the three following
diferences:
line 3: It compresses the diferent trajectories
simultaneAlgorithm 2 Pseudocode of the STTrace algorithm
Require: , maximal bufer size
1: = matrix of empty lists
2: = empty priority queue
3: for in do
4: s = S[p.id]
5: if interesting(p, s, ) then
6: p.priority = ∞
7: .append()
8: compute_priority(, [− 2])
9: .add()
10: if .size() > then
11: drop_point_recompute_priorities(, S)
12: end if
13: end if
14: end for
15: return {or }
ously (the trajectories are contained into a single
stream of points ). Each point will be a tuple
composed of (., ., ., .) with . being
the index of the trajectory . it belongs to, . and
. being its coordinates and . being its
timestamp. Furthermore, it operates in an unbalanced
way, i.e. after simplification, samples representing
more complicated trajectories will be composed of
more points. This result is obtained by
maintaining a single priority queue for all the points of the
diferent trajectories.
line 11: When one point is dropped from the priority
queue and from the concerned sample [.] (note
that the sample [.] is generally not the same
sample as the sample in which the last point was
added), the priorities of the neighboring points of
in the sample [.] will not be updated using
an heuristic approach such as in Squish. Instead,
when removing a point [], both the priorities of
[ − 1] and [ + 1] will be recomputed as
([ − 2], [ − 1], [ + 1]) and as
([ − 1], [ + 1], [ + 2]).
line 5: Before adding the next point in a
sample = [.], it will first check whether
this point seems promising. This is performed
by computing what the priority of the last
point in would be if was added to :
([− 2], [− 1], ). If this potential priority is
lower than the lowest priority in the priority queue,
then point is not added to the sample.
3.3. DR
The DR algorithm has been initially presented in [
Algorithm 3 Pseudocode of the DR algorithm Require: , deviation threshold 1: = matrix of empty lists 2: for in do 3: s = S[p.id] 4: ′ = estimate_position(s, p.ts) 5: if dist(′, ) > then 6: .append() 7: end if 8: end for 9: return
The estimated position (line 4) can be computed in two diferent ways according to the information contained in the stream of points. If each point of the stream is composed of (., ., ., .) (such as for Squish and STTrace ), then the expected position will be computed as if the object was travelling with constant direction and speed from [− 1] (with the direction and the speed being computed according to the straight line between [− 2] and [− 1]). For instance, the x coordinate of the expected position is computed as follows: ′. = [− 1]. + ([− 1]. − [− 2].) [− 1]. − [− 2]. (. − [− 1].) (8)
In some cases (such as in the AIS data), each point in the stream contains some information with respect to its speed and direction of the moving object. Each point p is then composed of (., ., ., ., ., .) with . and . representing respectively the speed over ground and course over ground of the entity. Then this additional information can be used to compute the estimated position ′ of . For instance, the x coordinate of the expected position is computed as follows: ′. =[− 1].+ ([− 1].) × [− 1]. × (. − [− 1].) (9)
While the previous section consisted in an introduction of diferent existing compression techniques, this section consists in the introduction of BandWidth-Constrained (BWC) variants of the existing algorithms. Four variants will be analysed in this work: BWC-STTrace, BWC-STTrace-Imp, BWC-Squish, BWC-DR. All of them share the main idea of extending their respective existing algorithm in a time windowed manner. However some slight adaptations have to be performed for the BWC-Squish and BWC-DR algorithms. Furthermore, the time windowed constraint also gives us the opportunity of proposing “improvement” of the BWCSTTrace algorithm (which is denoted BWC-STTrace-Imp). The modifications necessary for these three algorithms will be developed hereunder.
For simplicity purposes, the bandwidth will be considered as a constant parameter in all the algorithms. This means that for each time window, the same number of points will be kept. However, in practice, nothing prevents the algorithms of being used with an array of bandwidths for each diferent time window or in a more dynamic way by adapting the bandwidth according to the real time congestion of the network. 4.1. BWC-Squish and BWC-STTrace The BWC-STTrace method is simply the modification of the STTrace method applied on every time window, with the particularity that points kept in the sample of previous time windows can be used to compute the priority of points in the current time window. The priority of points in BWCSTTrace is identically computed as in the original STTrace method. The bandwidth constrains are respected by flushing and re-initializing the priority queue after each time window. A similar approach is used for the BWC-Squish algorithm. One of the characteristics of the Squish method, is that the numbers of points kept in the simplification of the trajectories have to be determined beforehand. However, the repartition of the number of points that should be kept for each trajectory individually in each time window is not straight forward. For this reason, the BWC-Squish algorithm is an “STTrace inspired" modification of the Squish algorithm as instead of compressing the trajectories individually, a single priority queue of limited size is shared for all trajectories. Such as for BWC-STTrace , the priority of points in BWC-Squish is identically computed as in the original Squish method. The pseudocode for the algorithms fo BWC-STTrace and BWC-Squish are identical and are shown in Algorithm 4. While the pseudocodes are identical, it is important to remember that both methods still compute the priorities diferently.
Algorithm 4 Pseudocode of the BWC-Squish , BWCSTTrace and BWC-STTrace-Imp algorithms. Underlined parts are the addition required for BWC-STTrace-Imp . Require: , window limit , window duration , start time , precision 1: = matrix of empty lists 2: = matrix of empty lists 3: = empty priority queue 4: _ = + 5: for in do 6: if . > _ then 7: lfush( ) 8: _ = _ + 9: end if 10: s, t = S[p.id], T[p.id] 11: p.priority = ∞ 12: .append() 13: .append() 14: compute_priority_imp([− 2], , , ) 15: .add() 16: if .size() > then 17: drop_point_recompute_priorities(, S, T, ) 18: end if 19: end for 20: return
The main motivation behind this improvement is that in STTrace, the priority of a point is computed using the sample it belongs to. Therefore, this priority is computed independently of the previously removed points. While the removal of a single point with a small priority will lead to a slight deviation in the sample, significant deviations can result of successively removing such points. The pseudocode of BWC-STTrace-Imp is detailed in Algorithm 4.
The priority of a point in a sample is therefore computed as follows. Instead of computing the SED error introduced in the sample when removing the concerned point, BWCSTTrace-Imp computes the diference between the SED error of the sample with respect to the initial trajectory with and without the considered point.
This error will be computed according to the distance between the synchronized position in the trajectory and the position in corresponding sample at regular time intervals (denoted ). To compute these positions (in a trajectory or in sample denoted ) at a specific time , the "neighboring" points should be identified. These neighbor points will be denoted − (the first point in before time ) and + (the ifrst point in after time ): − = + = ∈ .. . ≤ ∈ .. ≤ . ∧ ̸ ∃ ∈ ..
. < . ≤ ∧ ̸ ∃ ∈ .. ≤ . < .
By using equations 4, 5 and 11, we will define a function () providing the position of the entity at time according to the sample or trajectory :
() = (− , +, ) Then, the set of all the timestamps where the errors will be computed will be denoted ([], ). Indeed, the priority of a points [] will be the sum of all the errors for all timestamps between [ − ([], , ) will therefore be denoted:
1]. and [ + 1]. with the step . ([], , ) = {[ −
1]. + | ∈ N + ∧ [ − 1]. + < [ + 1].} (13) Finally, the sample that would be obtained by removing the node [] from will be denoted:
− = ∖ []
Using these notations, the priority in the sample with respect to an initial trajectory of a point [] can then be computed as: __([], , , ) = ︁( (︀ (), ()))︀ − (︀ (), − ()))︀ ︁) ∑︁ ∈ ([],, )
Once more, such as in STTrace, when dropping a point from a sample, the priority of the previous and following points in the sample will need to be recomputed.
While BWC-STTrace-Imp will produce more accurate results, it is at the cost of a more computationally expensive computation of the priorities. The computation of the priority of the point [] in STTrace or BWC-STTrace requires the computation of one distance as well as one (10) (11) (12) (14) (15) position (from two existing points and one timestamp). On the other hand the computation of the priority of [] in BWC-STTrace-Imp requires the computation of at most 2×
× since [ − 2 distances as well as 2× ×
1] might belong to the previous time window, the duration between [ −
1] and [ + 1] is at most 2 × which leads the set ([], , ) to be at most of size 2× . For every timestamp in this set, 3 positions (according to the real trajectory, the initial sample and the simplified sample) as well as 2 distances must be computed. 4.3. BWC-DR The DR algorithm has been modified in order to fulfill bandwidth constrains. This is performed, such as for Squish and STTrace by the introduction of time windows and a priority queue. Instead of using the distance between the position of the processed point with its expected position as a binary criterion to decide whether to add this point to the corresponding sample or not, this distance will be used as the priority of the point. Therefore, only the points which are the furthest of their expected position will be kept in
The pseudocode for the BWC-DR algorithm is detailed in each time window.
Algorithm 5 Pseudocode of the BWC-DR algorithm. Require: , window limit , window duration , start time 1: = matrix of empty lists 2: = empty priority queue 3: _ = + 5: for in do if . > _ then lfush( ) _ = _ + end if ′ = estimate_position(s, p.ts) p.priority = dist(′, ) .append() .add() if .size() > then
drop_point_recompute_priorities(, S) 4: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
end if 17: end for 18: return
Similarly as with Squish and STTrace (bandwidth constrained versions or not), when one point [] is dropped from the priority queue, it is also removed from the corresponding sample. Therefore, the priorities of some points of must be recomputed. With BWC-DR, its is not the priorities of the two neighbors ([ − must be recomputed, but the priorities of the one or two 1] and [ + 1]) which next nodes ([ + 1] and [ + 2]).
In this section, the performance of the introduced BWC algorithms as well as their classical equivalents and the classical TD-TR algorithm will be compared. The comparison will be performed on two datasets of diferent spatial and temporal ranges.
5.1.1. AIS
The first dataset consists of 24h of AIS data in the region
between the cities of Copenhagen and Malmo on first January
2021 [
It is important to note that this evaluation is not aimed at stating that some compression algorithms are better than others. Indeed, when selecting a compression algorithm, diferent factors have to be taken into account. While the ASED is generally an important factor, other factors such as time and space complexity should be taken into account. Furthermore the BWC algorithms are designed to be able to be used in situations with additional bandwidth constraints. It is not surprising that the fulfillment of these additional constraints may lead to a deterioration of the algorithms ASED.
While the diferent algorithms require diferent parameters, these were determined in order to produce a similar total number of points in the simplified trajectories produced by the diferent algorithms. For each dataset, the algorithms will be assessed with parameters such that both around 10% and around 30% of the original points are kept in the simplified trajectories.
The exact value of the parameters for the classical algorithms are listed hereunder.
Squish Squish requires the maximal number or points kept for each individual trajectory. This maximal number of point as been set to 10% and 30% of the initial points of each trajectory.
STTrace STTrace requires the maximal number or points kept for for all trajectories. This maximal number of points has been set to 10% and 30% of all initial points.
DR TD-TR
DR requires a distance threshold. This threshold has been set to 425 and 115 meters for the ais dataset and has been set to 2500 and 950 meters for the birds dataset.
The TD-TR time algorithm requires a tolerance threshold. This threshold has been set to 0.15 and 0.051 in the AIS dataset as well as 16.7 and 1.5 for the Birds dataset.
For each of the classical algorithms, its ASED can be seen in Table 1.
Squish STTrace DR TD-TR
AIS
Birds 10% 20.87 58.66 6.75 2.95 30% 4.83 9.78 2.32 1.08
10% 585.34 1823.10 697.14 274.78 30% 44.95 431.65 46.48 26.87
As it can be seen from Table 1, TD-TR is outperforming the other algorithms. This is due to the fact that Squish, STTrace and DR are designed to be less computationally expensive.
The performances of the BWC algorithms on the AIS dataset can be found in Tables 2 and 3.
Furthermore, we can notice from Tables 2 and 3 that for large enough windows (between 15 and 120 minutes), BWCSTTrace-Imp is outperforming the other BWC and classical algorithms. This is due to the fact that the priority of the points is evaluated using the sample and the original trajectory. It can also be noticed that for small time windows, the performances of BWC-Squish, BWC-STTrace and BWCSTTrace-Imp deteriorate. The deterioration is even drastic for 30 seconds time windows when keeping 10% of the points. The reason for this deterioration is that these three algorithms compute the priority of a point according to both the previous and the next point in the sample. Therefore, for small time windows, there will generally be less than 2 points per trajectory in the sample, making the removal of a point arbitrary and therefore leading to inaccurate simpliifcations. On the other hand the performances of BWC-DR are more constant and even improve for smaller time windows. This is due to the fact that BWC-DR only makes use of the previous one (or two) points to compute the priority of the currently processed point. Therefore, even with small time windows, it will be able to compute the priorities correctly using points kept during the previous time windows.
As expected, it can also be noted that the average error of the improved version of BWC-STTrace-Imp is indeed smaller than the one of BWC-STTrace. Surprisingly however, even BWC-STTrace outperforms the classical STTrace algorithm. One hypothesis is that this is due to STTrace both assessing the priority of points using current simplified trajectory only and simultaneously comparing diferent trajectories of diferent natures. Therefore, trajectories with diferent sampling frequencies could be compressed simultaneously. Trajectories with lower frequencies might fill up the priority queue as the priority of a point which is far apart in time from its neighbors in the sample will intuitively be higher than the one of a point close to its neighbors. Restarting with an empty priority queue at frequent time interval might help mitigate this phenomenon. Squish on the other hand, does not seem to sufer from this drawback. This might be due to their heuristic which counterbalance this efect by adding the priorities of points deleted from the sample.
The Tables 2 and 3 represent tests performed with a constant bandwidth (indicated by the window size and the number of points per window). It should be noted however that similar results can be obtained by selecting a random number of points (around the value indicated in the tables) individually for each time window.
The performances of the BWC algorithms on the Birds dataset can be found in Tables 4 and 5. Similar observations can be made for the Birds dataset as for the AIS dataset. Surprisingly, it can be seen that increasing the bandwidth from 8 to 22 points for the 1 hour time window lead to worse results for BWC-Squish, BWC-STTrace and BWCSTTrace-Imp. This confirms the arbitrary simplification performed by these algorithms if there are not enough points for each trip in each time window.
window size (days) points per window BWC-Squish BWC-STTrace BWC-STTrace-Imp BWC-DR window size (days) points per window BWC-Squish BWC-STTrace BWC-STTrace-Imp BWC-DR
In this section, the time repartition of points conserved with classical compression algorithms will be illustrated. This will be done by compressing the AIS dataset to 10% of its original size and by analysing the time repartition of the points kept for each period of 15 minutes. It will be shown that these algorithms do not produce an homogeneous timepartitioned results. In this configuration, 100 points should be kept in each period in order to satisfy the bandwidth constrain. The time repartition of simplified points for the TD-TRand DR are illustrated in Figures 3 and 4 (similar ifgures are obtained for Squish and STTrace). These figures consist in histograms representing the number of points remaining in all simplified trajectories during each period.
In each figure, the limit of 100 points is indicated with the blue dotted line. These figures confirm the need of using diferent compression techniques in context with bandwidth constrains.
In this work, four variations of existing algorithms for the simplification of trajectories have been introduced. These variations are aimed at being used in a situation with bandwidth limitations. The performances of the four algorithms have been studied for diferent sizes of time windows for two diferent datasets and for diferent compression rates. While the more computationally intensive BWC-STTraceImp outperforms the other algorithms for the larger time windows, the performances of BWC-DR remain more stable with small time windows.
Several further improvements could still be considered. First of all, this work extends three well known algorithms to a time windowed context. Diefrent algorithms might also be considered for such an extension. Furthermore, the presented algorithms could be further optimized. For instance the transition between time windows for the BWCSquish, BWC-STTrace and BWC-STTrace-Imp could be improved. Indeed, actually, all the last points of a trajectory in a window are assigned an infinity priority as there is no information accessible within the window with respect to the next points. This is probably the main reason why BWC-Squish , BWC-STTrace and BWC-STTrace-Imp perform poorly when the number of points kept in a time window is low compared to the number of trips. The priority of these last points could therefore be computed during the next time window, leading hopefully to more accurate results. The DR algorithm could also be modified in a different manner to satisfy bandwidth constrains instead of using a time-windowed approach with a priority queue. For instance, the distance threshold could be modified in real time by the algorithm according to the current number of points in the sample. Finally, the diferent algorithms could be further studied by applying the on a larger variety of datasets.
The research leading to the results presented in this paper has received funding from the European Union’s funded Project MobiSpaces under grant agreement no 101070279.