{"ID":2897778,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.05542","arxiv_id":"2507.05542","title":"GTRSS: Graph-based Top-$k$ Representative Similar Subtrajectory Query","abstract":"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.","short_abstract":"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 t...","url_abs":"https://arxiv.org/abs/2507.05542","url_pdf":"https://arxiv.org/pdf/2507.05542v1","authors":"[\"Mingchang Ge\",\"Liping Wang\",\"Xuemin Lin\",\"Yuang Zhang\",\"Kunming Wang\"]","published":"2025-07-07T23:50:17Z","proceeding":"cs.DB","tasks":"[\"cs.DB\"]","methods":"[]","has_code":false}