{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:51:57Z","timestamp":1760151117534,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T00:00:00Z","timestamp":1644796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Averaging GPS trajectories is needed in applications such as clustering and automatic extraction of road segments. Calculating mean for trajectories and other time series data is non-trivial and shown to be an NP-hard problem. medoid has therefore been widely used as a practical alternative and because of its (assumed) better noise tolerance. In this paper, we study the usefulness of the medoid to solve the averaging problem with ten different trajectory-similarity\/-distance measures. Our results show that the accuracy of medoid depends mainly on the sample size. Compared to other averaging methods, the performance deteriorates especially when there are only few samples from which the medoid must be selected. Another weakness is that medoid inherits properties such as the sample frequency of the arbitrarily selected sample. The choice of the trajectory distance function becomes less significant. For practical applications, other averaging methods than medoid seem a better alternative for higher accuracy.<\/jats:p>","DOI":"10.3390\/ijgi11020133","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T20:26:42Z","timestamp":1644870402000},"page":"133","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Is Medoid Suitable for Averaging GPS Trajectories?"],"prefix":"10.3390","volume":"11","author":[{"given":"Biliaminu","family":"Jimoh","sequence":"first","affiliation":[{"name":"School of Computing, University of Eastern Finland, 80101 Joensuu, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Radu","family":"Mariescu-Istodor","sequence":"additional","affiliation":[{"name":"School of Computing, University of Eastern Finland, 80101 Joensuu, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9554-2827","authenticated-orcid":false,"given":"Pasi","family":"Fr\u00e4nti","sequence":"additional","affiliation":[{"name":"School of Computing, University of Eastern Finland, 80101 Joensuu, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Hautam\u00e4ki, V., Nykanen, P., and Fr\u00e4nti, P. (2008, January 8\u201311). Time-series clustering by approximate prototypes. Proceedings of the International Conference on Pattern Recognition, Tampa, FL, USA.","DOI":"10.1109\/ICPR.2008.4761105"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Buchin, K., Driemel, A., van de L\u2019Isle, N., and Nusser, A. (2019, January 5\u20138). Klcluster: Center-based Clustering of Trajectories. Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL \u201919), Chicago, IL, USA.","DOI":"10.1145\/3347146.3359111"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"61","DOI":"10.3141\/2291-08","article-title":"Inferring road maps from global positioning system traces: Survey and comparative evaluation","volume":"2291","author":"Biagioni","year":"2012","journal-title":"Transp. Res. Rec."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/s10707-014-0222-6","article-title":"A comparison and evaluation of map construction algorithms using vehicle tracking data","volume":"19","author":"Ahmed","year":"2015","journal-title":"GeoInformatica"},{"key":"ref_5","first-page":"8","article-title":"Grid-based method for GPS route analysis for retrieval","volume":"3","year":"2017","journal-title":"ACM Trans. Spat. Algorithms Syst. (TSAS)"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s10472-019-09682-2","article-title":"Sufficient conditions for the existence of a sample mean of time series under dynamic time warping","volume":"88","author":"Jain","year":"2020","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"107730","DOI":"10.1016\/j.patcog.2020.107730","article-title":"Averaging GPS segments competition 2019","volume":"112","year":"2021","journal-title":"Pattern Recognit."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Estivill-Castrol, V., and Murray, A.T. (1998). Discovering associations in spatial data\u2014An efficient medoid based approach. Research and Development in Knowledge Discovery and Data Mining, Springer. Lecture Notes in Artificial Intelligence.","DOI":"10.1007\/3-540-64383-4_10"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s42452-020-2738-8","article-title":"A medoid-based weighting scheme for nearest-neighbor decision rule toward effective text categorization","volume":"2","author":"Mukherjee","year":"2020","journal-title":"SN Appl. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Fr\u00e4nti, P., and Yang, J. (2018, January 3\u20137). Medoid-Shift for Noise Removal to Improve Clustering. Proceedings of the International Conference on Artificial Intelligence and Soft Computing, Zakopane, Poland.","DOI":"10.1007\/978-3-319-91253-0_56"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3336","DOI":"10.1016\/j.eswa.2008.01.039","article-title":"A simple and fast algorithm for K-medoids clustering","volume":"36","author":"Park","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_12","unstructured":"Kaufman, L., and Rousseeuw, P.J. (2009). Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons."},{"key":"ref_13","unstructured":"Wagstaff, K., Cardie, C., Rogers, S., and Schroedl, S. (July, January 28). Constrained k-means clustering with background knowledge. Proceedings of the International Conference on Machine Learning (ICML), Williamstown, MA, USA."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1109\/3477.764879","article-title":"Genetic K-means algorithm","volume":"29","author":"Krishna","year":"1999","journal-title":"IEEE Trans. Syst. Man Cybern. Part B (Cybern.)"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1080\/0094965031000136012","article-title":"A new partitioning around medoids algorithm","volume":"73","author":"Pollard","year":"2003","journal-title":"J. Stat. Comput. Simul."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.patcog.2019.04.014","article-title":"How much can k-means be improved by using better initialization and repeats?","volume":"93","author":"Sieranoja","year":"2019","journal-title":"Pattern Recognit."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1186\/s40537-018-0122-y","article-title":"Efficiency of random swap clustering","volume":"5","year":"2018","journal-title":"J. Big Data"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"89239","DOI":"10.1109\/ACCESS.2020.2993295","article-title":"Can the Number of Clusters Be Determined by External Indices?","volume":"8","author":"Rezaei","year":"2020","journal-title":"IEEE Access"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"107874","DOI":"10.1016\/j.patcog.2021.107874","article-title":"Mean-shift outlier detection and filtering","volume":"115","author":"Yang","year":"2021","journal-title":"Pattern Recognit."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"4743","DOI":"10.1007\/s10489-018-1238-7","article-title":"K-means properties on six clustering benchmark datasets","volume":"48","author":"Sieranoja","year":"2018","journal-title":"Appl. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1016\/j.patcog.2017.08.012","article-title":"Nonsmooth analysis and subgradient methods for averaging in dynamic time warping spaces","volume":"74","author":"Schultz","year":"2018","journal-title":"Pattern Recognit."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1007\/s10618-018-0604-8","article-title":"Exact mean computation in dynamic time warping spaces","volume":"33","author":"Brill","year":"2019","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/B:DAMI.0000026904.74892.89","article-title":"Mining GPS traces for map refinement","volume":"9","author":"Schroedl","year":"2004","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Piegl, L., and Tiller, W. (1997). The NURBS Book, Springer. [2nd ed.].","DOI":"10.1007\/978-3-642-59223-2"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3234692","article-title":"Cellnet: Inferring road networks from GPS trajectories","volume":"4","year":"2018","journal-title":"ACM Trans. Spat. Algorithms Syst. (TSAS)"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Fathi, A., and Krumm, J. (2010, January 14\u201317). Detecting road intersections from GPS traces. Proceedings of the International Conference on Geographic Information Science, Zurich, Switzerland.","DOI":"10.1007\/978-3-642-15300-6_5"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1080\/13658816.2015.1081205","article-title":"Trajectory Box Plot: A new pattern to summarize movements","volume":"30","author":"Etienne","year":"2016","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"375","DOI":"10.2478\/amcs-2019-0028","article-title":"Times Series Averaging and Denoising from a Probabilistic Perspective on Time\u2013Elastic Kernels","volume":"29","author":"Marteau","year":"2019","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","article-title":"Algorithms for the reduction of the number of points required to represent a digitized line or its caricature","volume":"10","author":"Douglas","year":"1973","journal-title":"Cartographica"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Drezner, Z., Klamroth, K., Sch\u00f6bel, A., and Wesolowsky, G.O. (2002). The weber problem. Facility Location: Applications and Theory, Springer.","DOI":"10.1007\/978-3-642-56082-8_1"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"561","DOI":"10.3233\/IDA-2007-11508","article-title":"Toward accurate dynamic time warping in linear time and space","volume":"11","author":"Salvador","year":"2007","journal-title":"Intell. Data Anal."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Yang, J., Mariescu-Istodor, R., and Fr\u00e4nti, P. (2019). Three rapid methods for averaging GPS segments. Appl. Sci., 9.","DOI":"10.3390\/app9224899"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/j.is.2015.11.002","article-title":"Myway: Location prediction via mobility profiling","volume":"64","author":"Trasarti","year":"2017","journal-title":"Inf. Syst."},{"key":"ref_34","unstructured":"Vlachos, M., Gunopulos, D., and Kollios, G. (2002, January 2\u20136). Robust similarity measures for mobile object trajectories. Proceedings of the 13th IEEE International Workshop on Database and Expert Systems Applications (DEXA\u201902), Aix-en-Provence, France."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Chen, L., \u00d6zsu, M.T., and Oria, V. (2005, January 14\u201316). Robust and fast similarity search for moving object trajectories. Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, MD, USA.","DOI":"10.1145\/1066157.1066213"},{"key":"ref_36","unstructured":"Rockafellar, T.R., and Wets, R.J.-B. (2009). Variational Analysis, Springer."},{"key":"ref_37","unstructured":"Chen, L., and Ng, R. (September, January 31). On the marriage of lp-norms and edit distance. Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, ON, Canada."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Zheng, Y., and Zhou, X. (2011). Computing with Spatial Trajectories, Springer Science & Business Media.","DOI":"10.1007\/978-1-4614-1629-6"},{"key":"ref_39","unstructured":"Gradshteyn, I.S., and Ryzhik, I.M. (2000). Tables of Integrals, Series, and Products, Academic Press. [6th ed.]."},{"key":"ref_40","unstructured":"Eiter, T., and Mannila, H. (1994). Computing Discrete Fr\u00e9chet Distance. Technical Report CD-TR 94\/64, Christian Doppler Laboratory for Expert Systems, TU Vienna."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Nie, P., Chen, Z., Xia, N., Huang, Q., and Li, F. (2021). Trajectory similarity analysis with the weight of direction and k-neighborhood for AIS data. ISPRS Int. J. Geo-Inf., 10.","DOI":"10.3390\/ijgi10110757"},{"key":"ref_42","unstructured":"Wang, H., Su, H., Zheng, K., Sadiq, S., and Zhou, X. (February, January 29). An effectiveness study on trajectory similarity measures. Proceedings of the Twenty-Fourth Australasian Database Conference, Adelaide, Australia."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1109\/TPAMI.2007.1078","article-title":"A normalized Levenshtein distance metric","volume":"29","author":"Yujian","year":"2007","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"M\u00fcller, M. (2007). Dynamic time warping. Information Retrieval for Music and Motion, Springer.","DOI":"10.1007\/978-3-540-74048-3"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1109\/34.232073","article-title":"Comparing images using the Hausdorff distance","volume":"15","author":"Huttenlocher","year":"1993","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Waga, K., Tabarcea, A., Chen, M., and Fr\u00e4nti, P. (2012, January 14\u201317). Detecting movement type by route segmentation and classification. Proceedings of the 8th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), Pittsburgh, PA, USA.","DOI":"10.4108\/icst.collaboratecom.2012.250450"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"2770","DOI":"10.1109\/TIP.2012.2186146","article-title":"A fast O(N) multi-resolution polygonal approximation algorithm for GPS trajectory simplification","volume":"21","author":"Chen","year":"2012","journal-title":"IEEE Trans. Image Process."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Mariescu-Istodor, R., and Fr\u00e4nti, P. (December, January 29). Gesture input for GPS route search. Proceedings of the Joint International Workshop on Structural, Syntactic, and Statistical Pattern Recognition (S+SSPR 2016), Merida, Mexico.","DOI":"10.1007\/978-3-319-49055-7_39"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/11\/2\/133\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:19:41Z","timestamp":1760134781000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/11\/2\/133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,14]]},"references-count":48,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["ijgi11020133"],"URL":"https:\/\/doi.org\/10.3390\/ijgi11020133","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2022,2,14]]}}}