GoodTP: An Effective Data Selection Framework for Enhancing Trajectory Similarity Learning via Monte Carlo Tree Search

Trajectory similarity computation is fundamental to spatial data management. Recent representation learning methods have advanced similarity computation through neural embeddings, yet they rely on naive random sampling of training data, overlooking strategic data selection that determines learning effectiveness. Existing data selection paradigms are not suitable due to their requirement for labeled trajectory pairs with prohibitive cost. We present GoodTP, a novel framework that addresses challenges in data selection for trajectory similarity learning. First, the framework reformulates the expensive pair selection into iterative trajectory selection that dynamically constructs and evaluates pairs, eliminating exhaustive pairwise similarity pre-computation. Second, we design a hierarchical clustering tree that organizes trajectories across multiple granularities. We model selection as tree sampling optimization via Monte Carlo Tree Search (MCTS), efficiently navigating the exponential policy space. Third, we bridge the local-to-global optimization gap through two complementary mechanisms: (1) An effective learned policy based on Upper Confidence Bound (UCB) balances exploration-exploitation with provable convergence guarantees. (2) Cache-enhanced bilevel optimization learns instance-specific weights that align new pairs with accumulated global pairs while jointly optimizing model parameters. Extensive experiments across representative trajectory similarity models on real-world datasets demonstrate that GoodTP achieves substantial performance improvements.