Fréchet Kernel for Trajectory Data Analysis
Open accessAbstract
Trajectory analysis has been a central problem in applications of location tracking systems. Recently, the (discrete) Fréchet distance becomes a popular approach for measuring the similarity of two trajectories because of its high feature extraction capability. Despite its importance, the Fréchet distance has several limitations: (i) sensitive to noise as a trade-off for its high feature extraction capability; and (ii) it cannot be incorporated into machine learning frameworks due to its non-smooth functions. To address these problems, we propose the Fréchet kernel (FRK), which is associated with a smoothed Fréchet distance using a combination of two approximation techniques. FRK can adaptively acquire appropriate extraction capability from trajectories while retaining robustness to noise. Theoretically, we find that FRK has a positive definite property, hence FRK can be incorporated into the kernel method. We also provide an efficient algorithm to calculate FRK. Experimentally, FRK outperforms other methods, including other kernel methods and neural networks, in various noisy real-data classification tasks.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Progress is being made for using trajectories in ML algorithms.
“Further, progress is being made for using trajectories in the ML algorithms [97,98].”
From Human-centred artificial intelligence for mobile health sensing: challenges and opportunities (2023) · cites this paper as [97]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
LeCun, Y., Bengio, Y., & Hinton, G. (2015) · Nature · doi:10.1038/nature14539 · Cited by 84,126 · see citing works
Comparing images using the Hausdorff distance
Huttenlocher, D. P., Klanderman, G. A., & Rucklidge, W. J. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.232073 · Cited by 4,545 · see citing works
(1994) · Knowledge Discovery and Data Mining · Cited by 3,137 · see citing works
Social GAN: Socially Acceptable Trajectories with Generative Adversarial Networks
Gupta, A., Johnson, J., Fei-Fei, L., Savarese, S., & Alahi, A. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00240 · Cited by 2,466 · see citing works
Zheng, Y. (2015) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/2743025 · Cited by 1,667 · see citing works
Understanding mobility based on GPS data
Zheng, Y., Li, Q., Chen, Y., Xie, X., & Ma, W.-Y. (2008) · Proceedings of the 10th international conference on Ubiquitous computing · doi:10.1145/1409635.1409677 · Cited by 1,132 · see citing works
COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
Alt, H., & Godau, M. (1995) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195995000064 · Cited by 1,051 · see citing works
Sur quelques points du calcul fonctionnel
Fréchet, M. (1906) · Rendiconti del Circolo Matematico di Palermo Series 2 · doi:10.1007/bf03018603 · Cited by 1,034 · see citing works
Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks
Liu, T., Bahl, P., & Chlamtac, I. (1998) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.709453 · Cited by 561 · see citing works
Inferring High-Level Behavior from Low-Level Sensors
Patterson, D. J., Liao, L., Fox, D., & Kautz, H. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39653-6_6 · Cited by 521 · see citing works
TrafficPredict: Trajectory Prediction for Heterogeneous Traffic-Agents
Ma, Y., Zhu, X., Zhang, S., Yang, R., Wang, W., & Manocha, D. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33016120 · Cited by 458 · see citing works
Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching
Marteau, P.-F. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.76 · Cited by 337 · see citing works
Deep Representation Learning for Trajectory Similarity Computation
Li, X., Zhao, K., Cong, G., Jensen, C. S., & Wei, W. (2018) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2018.00062 · Cited by 302 · see citing works
Peeking Into the Future: Predicting Future Person Activities and Locations in Videos
Liang, J., Jiang, L., Niebles, J. C., Hauptmann, A. G., & Fei-Fei, L. (2019) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2019.00587 · Cited by 300 · see citing works
Mobility Detection Using Everyday GSM Traces
Sohn, T. Y., Varshavsky, A., LaMarca, A., Chen, M. Y., Choudhury, T., Smith, I., Consolvo, S., Hightower, J. R., Griswold, W. G., & de Lara, E. (2006) · Lecture notes in computer science · doi:10.1007/11853565_13 · Cited by 277 · see citing works
Cuturi, M. (2011) · Cited by 270 · see citing works
A Kernel for Time Series Based on Global Alignments
Cuturi, M., Vert, J., Birkenes, Ø., & Matsui, T. (2007) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2007.366260 · Cited by 240 · see citing works
Peeking Into the Future: Predicting Future Person Activities and Locations in Videos
Liang, J., Jiang, L., Niebles, J. C., Hauptmann, A. G., & Fei-Fei, L. (2019) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw.2019.00358 · Cited by 240 · see citing works
Locadio: inferring motion and location fron Wi-Fi signal strengths
Krumm, J. C., & Horvitz, E. (2004) · doi:10.1109/mobiq.2004.1331705 · Cited by 208 · see citing works
Trajectory clustering via deep representation learning
Yao, D., Zhang, C., Zhu, Z., Huang, J., & Bi, J. (2017) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2017.7966345 · Cited by 196 · see citing works
The Move-Split-Merge Metric for Time Series
Stefan, A., Athitsos, V., & Das, G. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2012.88 · Cited by 189 · see citing works
Bringmann, K. (2014) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.76 · Cited by 155 · see citing works
Application of the self-organising map to trajectory classification
Owens, J. D., & Hunter, A. (2002) · doi:10.1109/vs.2000.856860 · Cited by 145 · see citing works
Fréchet Distance Based Approach for Searching Online Handwritten Documents
Sriraghavendra, E., Karthik, K., & Bhattacharyya, C. (2007) · Proceedings of the International Conference on Document Analysis and Recognition · doi:10.1109/icdar.2007.4378752 · Cited by 72 · see citing works
Path Similarity Analysis: A Method for Quantifying Macromolecular Pathways
Seyler, S. L., Kumar, A., Thorpe, M. F., & Beckstein, O. (2015) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1004568 · Cited by 70 · see citing works
CMTS: A Conditional Multiple Trajectory Synthesizer for Generating Safety-Critical Driving Scenarios
Ding, W., Xu, M., & Zhao, D. X. (2020) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra40945.2020.9197145 · Cited by 69 · see citing works
On Recursive Edit Distance Kernels With Application to Time Series Classification
Marteau, P.-F., & Gibet, S. (2014) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2014.2333876 · Cited by 68 · see citing works
Debunking Four Long-Standing Misconceptions of Time-Series Distance Measures
Paparrizos, J., Liu, C., Elmore, A. J., & Franklin, M. J. M. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3389760 · Cited by 58 · see citing works
Effective and Efficient Sports Play Retrieval with Deep Representation Learning
Wang, Z., Long, C., Cong, G., & Ju, C. (2019) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3292500.3330927 · Cited by 48 · see citing works
Matsumoto, S., Yamamoto, T., Yamamoto, M., Zavalaga, C. B., & Yoda, K. (2017) · ORNITHOLOGICAL SCIENCE · doi:10.2326/osj.16.23 · Cited by 38 · see citing works
Self-citationApproximating (<i>k</i>, <i>ℓ</i>)-center clustering for curves
Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., Löffler, M., & Struijs, M. (2019) · Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611975482.181 · Cited by 16 · see citing works
Schoenberg’s Theorem for Positive Definite Functions on Products: A Unifying Framework
Guella, J. C., & Menegatto, V. . (2018) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-018-9631-5 · Cited by 12 · see citing works
Hearst, A. (2012) · doi:10.1002/9781118437957.ch11 · Cited by 10 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Human-centred artificial intelligence for mobile health sensing: challenges and opportunities
Dang, T., Spathis, D., Ghosh, A., & Mascolo, C. (2023) · Royal Society Open Science · doi:10.1098/rsos.230806 · Cited by 30 · see citing works
Multi-Agent Deep-Learning Based Comparative Analysis of Team Sport Trajectories
Zhang, Z., Bunker, R., Takeda, K., & Fujii, K. (2023) · IEEE Access · doi:10.1109/access.2023.3269287 · Cited by 15 · see citing works
Self-citationPredictive Analysis and Play Evaluation with Machine Learning
Fujii, K. (2025) · SpringerBriefs in computer science · doi:10.1007/978-981-96-1445-5_3 · Cited by 1 · see citing works
Self-citationAdaptive output steps: FlexiSteps network for dynamic trajectory prediction
Liu, Y., Niu, H., & Zhu, J. (2025) · PLoS ONE · doi:10.1371/journal.pone.0333926 · Cited by 1 · see citing works
- Authors
- Takeuchi, K., Imaizumi, M., Kanda, S., Tabei, Y., Fujii, K., Yoda, K., Ishihata, M., & Maekawa, T.
- Affiliations
- Kyoto University (JP)
- The University of Tokyo (JP)
- RIKEN Center for Advanced Intelligence Project (JP)
- Nagoya University (JP)
- NTT (Japan) (JP)
- The University of Osaka (JP)
- ORCID
- Venue
- Proceedings of the 29th International Conference on Advances in Geographic Information Systems
- Publisher
- ACM
- Published
- 2021-11-02
- Pages
- 221-224
- OpenAlex
- W3214289837
- Cited by
- 4
- References
- 33
- Citations by year
- 2025: 2 · 2023: 2
- FWCI
- 0.30
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) (publishedVersion, cc-by)
- Funders
- Japan Society for the Promotion of Science (21H05293, 20H04075, 21K11780, 21H05300)
- Topics
- Physical Sciences › Computer Science › Signal Processing › Data Management and Algorithms
- Physical Sciences › Computer Science › Signal Processing › Time Series Analysis and Forecasting
- Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications
- Keywords
- Fréchet kernels, Fréchet distance, trajectory analysis, trajectory similarity, location tracking, positive definite kernels, kernel methods, noise robustness, trajectory classification
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
