BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data

Summary: BT-Tree: a reinforcement-learning–driven index for big trajectory data, built by recursive bi-partitioning to accelerate range and KNN queries. It combines a cost-function-based build (CFBM) that encodes data and workload, with an RL refinement to avoid locally optimal cuts; experiments with up to 800M points show CFBM outperforms baselines, and RL consistently wins, especially on large datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4a0157f59405157e
Venue: SIGMOD
Year: 2024
Pagerank: 5.0979044e-05
Overall Rank: 10,002 | 32.76%
DOI: 10.1145/3677130

Incoming Non-self Citations Over Time

Authors

1. Tu Gu (Nanyang Technological University)
2. Kaiyu Feng (Beijing Institute of Technology)
3. Jingyi Yang (Nanyang Technological University)
4. Gao Cong (Nanyang Technological University)
5. Cheng Long (Nanyang Technological University)
6. Rui Zhang (Huazhong University of Science and Technology)

BibTeX Citation

@inproceedings{gu_sigmod24,
        title = {{BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data}},
        author = {Gu, Tu and Feng, Kaiyu and Yang, Jingyi and Cong, Gao and Long, Cheng and Zhang, Rui},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3677130},
        url = {https://dl.acm.org/doi/10.1145/3677130},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,844	Rethinking Learned Index and LSM-tree Integration	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016173068
868	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013354403
985	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012685169
1,132	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011898257
1,191	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011590153
1,226	Fractals for Secondary Key Retrieval	1989	PODS	0.00011431306
1,446	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010629222
1,878	Effectively Learning Spatial Indices	2020	VLDB	9.4451309e-05
2,021	Distributed Trajectory Similarity Search	2017	VLDB	9.1719539e-05
2,196	DITA: Distributed In-Memory Trajectory Analytics	2018	SIGMOD	8.8780862e-05
2,310	The MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries	2001	VLDB	8.6626285e-05
2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.4897323e-05
2,911	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8720638e-05
3,161	Effective Travel Time Estimation: When Historical Trajectories over Road Networks Matter	2020	SIGMOD	7.5796549e-05
4,134	ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects	2008	SIGMOD	6.787575e-05
4,850	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.3808017e-05
5,743	VRE: A Versatile, Robust, and Economical Trajectory Data System	2022	VLDB	6.0099017e-05
6,596	PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories	2021	VLDB	5.7410544e-05
7,303	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5598057e-05
8,179	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3826446e-05
9,427	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.178769e-05
10,168	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.0682654e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,697	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
2	12,754	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
3	7,856	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB
4	8,107	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB
5	12,181	The Maximum Trajectory Coverage Query in Spatial Databases	2019	VLDB
6	8,179	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB
7	4,352	Searching Trajectories by Locations - An Efficiency Study	2010	SIGMOD
8	4,968	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD
9	2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
10	4,850	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD