Is Medoid Suitable for Averaging GPS Trajectories?
Round 1
Reviewer 1 Report
This is an interesting study that investigated the usefulness of the Medoid to solve the averaging problem with ten different trajectory similarity/distance measures. This analysis results indicate the performance of Medoid is sensitive to sample size and noise. And the research concludes Medoid seems not a good choice for GPS trajectory averaging and should be used with caution. It has the potential contribution to help with the selection of the methods when applying GPS trajectory averaging. The overall quality of the paper is okay. However, I have a few concerns that may need to be addressed by the authors:
- Generally speaking, I feel lost in key points when reading the paper. It is hard to say how the study would contribute to the research community in the current format. The paper concludes that Medoid is sensitive to sample size and noise and should be carefully considered when applying. However, the more important question is how to? What should be done when applying the method? Are there any practical suggestions or recommendations?
- The research questions need more consideration and to be justified. What is the motivation to systematically study the usefulness of Medoid for the averaging problem? Is it because Medoid is being widely used despite its shortcomings? This needs to be clearly introduced or discussed in the Introduction section.
- The whole paper feels more like a comparison of several different performing measures for the GPS trajectory averaging problem. I don’t see how the paper concludes that “other averaging methods than Medoid seem a better alternative for higher accuracy with explicit outlier removal for noise tolerance.”
- Figures 1 and 2 should appear right after the paragraph citing them.
- Line 96: double 4?
- If Table 4 can be visualized as a chart, it would be much easier for the comparison.
Author Response
See the attached Word file.
Author Response File: 
Author Response.docx
Reviewer 2 Report
This paper targets the problem of averaging a set of trajectories to define the "centerline".
The medoid concept is presented and computed using various well known similarity measures between trajectories.
Section 2.1 presents a literature review about existing heuristics for finding mean
Title should be detailing what "mean" is investigated in this section (full trajectories or segments or position clouds).
The description of the literature technique are very fast and could be more detailed.
Author states "There are several reasonable algorithms in literature but many of them suffer from high time complexity and their implementation can be somewhat complicated".
However, the previously mentioned algorithms complexity is not clearly indicated in the literature review.
Figure 4 details a previous proposal from the author cited as reference [6].
However this proposal is not positioned against other algorithms presented in the literature review.
Why Douglas Peucker algorithm is applied at the last step of the process ?
What would be the impact of applying Douglas Peucker before the reordering process ?
How do these algorithms handle "loops" in trajectories ?
In section 2.2 author states that the medoid of a trajectory cluster is one of the trajectory of the cluster.
However, one could argue that the centerline could be created from the medoids of ordered positions clouds of the trajectory cluster.
l164 : The complexity O(nk) is not clear because the k trajectories need to be compared to each other giving k² distance matrix between all trajectories
Considering theoretically that the distance D operator is O(n) then you should get a O(nk²) complexity.
However l169, author states that distances function D are usually O(n²) and that the medoid computation complexity is O(n²k²).
Reviewer suggest to revise l164 complexity to O(nk²) or to withdraw the theoretical statement of line 164 and keep l169 instead.
Section 2.3 author detail one of their own proposal [26] combining heuristics and medoid.
l179-180, it is not clear why the author use a k-mean algorithm to extract endpoints of segments (source and destination set).
Then author state that the travel direction is ignored (however there are two positions set named source and destination).
Why is the direction ignored ? How many trajectories are required to give an interesting "centerline" ?
l181, please define the "middle point" of a trajectory. Depending on the sampling rate of a trajectory and change in speed of the moving object, this notion can be complicated to define.
Reviewer suggest to include a discussion about the positions that are neither in the endpoints set nor in the middle points set.
If these points in between the sets are deviating a lot from the start/middle/end sets, then they might not be considered by the algorithm whereas they might have a huge impact.
A small conclusion of this section could indicate why this hybrid method is better than the previous one.
Section 3 presents similarity measure applied to trajectories.
l201 : Author indicate that similarity measure that ignore directions have a drawback.
However in previous section, author also ignore the direction in the SMD method.
Table 1 presents the results of previous work from authors [4,6].
In this table, the "human score" is not clearly defined.
Moreover there are no quality assessment for line IRD.
This is not discussed in the IRD section of the paper even if this section indicates that IRD is somehow similar to DTW.
Section 3.7 l254 : sentence "it calculates distance to a constant" should be clarified.
Section 3.9 l256: sentence "Interpolation route distance (IRD) [27] is similar to DTW with two differences" lead to misunderstanding regarding the differences between these two algorithms.
DTW allows "time warping" leading to point alignments that are not exactly at the same time whereas IRD interpolates points and align the points of two trajectories using time.
Section 4 presents the experiment
Some terms should be more precisely defined at the beginning of the section, here authors use sets of "segments" instead of trajectories there are also 4 "sub-set".
Moreover, the average number of segments and points per segments are very low as indicated in table 2.
l294, authors indicate "we generate GPS segments for each set using Medoid with the selected distance measure".
What does "generating" GPS segments means ? GPS positions have already been collected in the 4 sub-set.
It may be generating "centerlines" for each GPS segments using the various distance measures.
l295, "The result is compared against ground truth using HC-SIM". Why was the HC-SIM similarity measure selected to compare to ground truth ?
l296-298 : Authors indicate that a re-ordering process and outlier removal was applied. However, the parameter and technique used to conduct these process are not detailled.
Then, authors point the reader to a website presenting many tools that were not discussed in the paper such as transport mode detection, road network extraction...
Results are presented in section 5
l341, author indicates that HC-SIM perform best to define the centerline however, the measure used to compare the ground truth with the selected centerline is also HC-SIM.
Authors state "This is as expected as the Medoids are optimized for the same measure than used in the evaluation".
Reviewer wonder if the results would be different if the quality assessment measure would have been different ?
A more detailed discussion about the impact of the similarity measure used to compare the centerline with ground truth is needed.
Frechet distance was last in the table 1 and then becomes 4th in table 4.
l348 define what "poor segments" means (<30% using the HC-SIM measure).
l358 Throughout the paper, author indicate that reordering might be required.
However, one can argue that position order in trajectories are important.
Especially when driving on roads or walking on sidewalks, people are following directed path.
These informations are also included in "ground truth" simplified and generalized roads in OSM (oneway tag).
It could be of interest to analyse "segments" to define 2 sub-segments clusters depending on theirs direction.
Section 6 comments the results
Section 6.1 illustrates examples of unusual results clearly presented in figure 8.
However, only the DTW centerline was presented on figure.
It could be of interest to visualize how other algorithm perform on such datasets.
Please also indicate that black line is the "ground truth" in figure 8 caption.
Section 6.2 presents the re-ordering and outlier removal impact.
Reviewer points out the small number of segments in dataset illustrated on figure 9 (3rd line).
Using techniques that are designed to account for point ordering without knowing the segments order in the cluster is a major problem.
In this example, as there are only 5 segments in the illustrated dataset, there are chance that only 1 or 2 segments of the dataset has the same direction than the ground truth.
Then, the best matching segments will be then one matching with the same direction than the ground truth.
Section 6.3 deal with normalizing the segments to a fixed number of points.
Here the figure 10 is difficult to interpret as authors indicates that segments have been resampled to 10 points however, neither the ground truth, nor the grey segments lines have 10 points.
Moreover, the similarity measure used to produce the blue centerline is not indicated in this section whereas it was mentioned in the two previous sections.
In the conclusion section, author claim that the medoid technique has numerous weaknesses.
These weaknesses have been highlighted in previous sections.
However, the dataset used to conduct these experiments has many biases that have been illustrated in the discussion section 6.
The size of the segment set is relatively small as presented in table 2.
3 out of 4 of the experimental set have less than 7 segments per set in average.
Moreover, the average number of point per segments are also very small (less than 4 points).
Finally, having different trajectories directions mixed within the same small set of segment is a major drawback of the dataset.
Most of the sets illustrated in figure 8, 9, 10, 11 are presenting examples of simple "straight line" ground truth.
For all these reasons, reviewer does not agree with the author claim that all these problems lower the usefulness of the medoid.
Typos :
l96: number 4 twice
l144: constrcuted
l201: ignorers
l245: sensitive (to) sub-sampling
l321 : and an
l332 : are ... are
Figure 10 is numbered twice. l348 is figure 11
Reviewer suggest to reinforce the literature review about trajectory k-mean and trajectory alignment using Frechet distance computation:
"Trajectory Box Plot: a new pattern to summarize movements" 2016
"klcluster: Center-based Clustering of Trajectories" 2019
Author Response
See the attached Word file.
Author Response File: Author Response.docx
Round 2
Reviewer 1 Report
Lines 37-38: citations are needed for the claimed "widely used in many applications".
Table 4: author can keep table 4 while adding figures to illustrate the comparison. The readability of the figures can be improved by proper cartography design.
Author Response
- Citations added in line 39 as proposed.
- Added Figure 8 to illustrate the distribution and readability improved by limiting only the best (HC-SIM) and worst (Euclidean) as cited in text.
Reviewer 2 Report
In this second version of the paper, authors have included some of the reviewers comment and provided comprehensives responses to reviewer questions.
Reviewer acknowledge that this paper is highly related to reference [6] and presents an extended analysis of this competition results.
Response 1 has been partially addressed reviewers comments by updating the title to indicate that the scope of this section is related to segments. Discussion about loops is discarded considering that loops does not appears in the dataset (in segments)
In response 3 reviewer agrees that the Medoid is applied to the full trajectory (or at least segments of these trajectories)
Point 4 is fixed
Point 5 : Author indicate that "travel direction is ignored". And in the answer 5 indicates that the idea itself generalizes even if the directions were preserved. Reviewer suggest to simply add a sentence in the paper about this generalization possibility. This will also solve the same comment about direction in point 6.
Point 7 is fixed
Point 8 is clarified as segments are extracted from the 4 datasets and not generated using an algorithm.
Point 9 From [6] authors recap the three main observations from the results.
Poor segments were clarified.
Point 10 is related to same discussion than point 5 and 6
Point 11 was addressed by author (fig 8 legend was updated).
However the low number of segments in some examples of figure 9 cannot be fixed in this paper due to the dataset quality itself.
Figure 10 cannot be fixed to display the grey subsampled trajectories with 10 points each.
This should be indicated in the text l426 that only the blue line is subsampled on figure. However with text explanation, this is clear enough.
The measure used (LCSS) is now indicated in the legend.
Regarding trajectories datasets, here are some suggestions:
https://privamov.github.io/accio/docs/datasets.html
http://www.chorochronos.org/
Typos have been fixed
Bibliography has been extented
Author Response
Point 1: How do these algorithms handle "loops" in trajectories ?
Response 1: There is no natural place in the paper to discuss about loops. They are not expected and do not appear in our data. The entire trajectories do contain loops so if extended then the issue would become relevant (but so would several others). Currently it is off-topic side issue that would just distract reader if discussed.
Point 5: Author indicate that "travel direction is ignored". And in the answer 5 indicates that the idea itself generalizes even if the directions were preserved. Reviewer suggest to simply add a sentence in the paper about this generalization possibility. This will also solve the same comment about direction in point 6.
Response 5: Done as proposed by adding the following sentence: “The travel direction is ignored but the idea itself generalizes even if the directions were preserved.”
Point 10: Figure 10 cannot be fixed to display the grey subsampled trajectories with 10 points each. This should be indicated in the text l426 that only the blue line is subsampled on figure. However with text explanation, this is clear enough.
Response 10: Done as proposed by adding the following sentece into Figure 10 legend: “The re-sampling (to 10 points) is shown only for the segment average (blue line).”
Point 13: Regarding trajectories datasets, here are some suggestions:
https://privamov.github.io/accio/docs/datasets.html
http://www.chorochronos.org/
Response 13: Thanks for the pointers. These can be valuable in our future research.
