GTRSS: Graph-based Top-$k$ Representative Similar Subtrajectory Query
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918086090686464 |
|---|---|
| author | Ge, Mingchang Wang, Liping Lin, Xuemin Zhang, Yuang Wang, Kunming |
| author_facet | Ge, Mingchang Wang, Liping Lin, Xuemin Zhang, Yuang Wang, Kunming |
| contents | Trajectory mining has attracted significant attention. This paper addresses the Top-k Representative Similar Subtrajectory Query (TRSSQ) problem, which aims to find the k most representative subtrajectories similar to a query. Existing methods rely on costly filtering-validation frameworks, resulting in slow response times. Addressing this, we propose GTRSS, a novel Graph-based Top-k Representative Similar Subtrajectory Query framework. During the offline phase, GTRSS builds a dual-layer graph index that clusters trajectories containing similar representative subtrajectories. In the online phase, it efficiently retrieves results by navigating the graph toward query-relevant clusters, bypassing full-dataset scanning and heavy computation. To support this, we introduce the Data Trajectory Similarity Metric (DTSM) to measure the most similar subtrajectory pair. We further combine R-tree and grid filtering with DTSM pruning rules to speed up index building. To the best of our knowledge, GTRSS is the first graph-based solution for top-k subtrajectory search. Experiments on real datasets demonstrate that GTRSS significantly enhances both efficiency and accuracy, achieving a retrieval accuracy of over 90 percent and up to two orders of magnitude speedup in query performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_05542 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | GTRSS: Graph-based Top-$k$ Representative Similar Subtrajectory Query Ge, Mingchang Wang, Liping Lin, Xuemin Zhang, Yuang Wang, Kunming Databases Trajectory mining has attracted significant attention. This paper addresses the Top-k Representative Similar Subtrajectory Query (TRSSQ) problem, which aims to find the k most representative subtrajectories similar to a query. Existing methods rely on costly filtering-validation frameworks, resulting in slow response times. Addressing this, we propose GTRSS, a novel Graph-based Top-k Representative Similar Subtrajectory Query framework. During the offline phase, GTRSS builds a dual-layer graph index that clusters trajectories containing similar representative subtrajectories. In the online phase, it efficiently retrieves results by navigating the graph toward query-relevant clusters, bypassing full-dataset scanning and heavy computation. To support this, we introduce the Data Trajectory Similarity Metric (DTSM) to measure the most similar subtrajectory pair. We further combine R-tree and grid filtering with DTSM pruning rules to speed up index building. To the best of our knowledge, GTRSS is the first graph-based solution for top-k subtrajectory search. Experiments on real datasets demonstrate that GTRSS significantly enhances both efficiency and accuracy, achieving a retrieval accuracy of over 90 percent and up to two orders of magnitude speedup in query performance. |
| title | GTRSS: Graph-based Top-$k$ Representative Similar Subtrajectory Query |
| topic | Databases |
| url | https://arxiv.org/abs/2507.05542 |