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.0954911e-05
Overall Rank: 10,007 | 32.75%
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,854	Rethinking Learned Index and LSM-tree Integration	2026	VLDB	4.9769913e-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.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016165512
869	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013363241
985	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012679233
1,128	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011901941
1,188	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011598149
1,228	Fractals for Secondary Key Retrieval	1989	PODS	0.00011427053
1,440	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010638444
1,877	Effectively Learning Spatial Indices	2020	VLDB	9.4498401e-05
2,023	Distributed Trajectory Similarity Search	2017	VLDB	9.167612e-05
2,198	DITA: Distributed In-Memory Trajectory Analytics	2018	SIGMOD	8.8738834e-05
2,313	The MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries	2001	VLDB	8.6585352e-05
2,422	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.4857212e-05
2,912	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8683521e-05
3,162	Effective Travel Time Estimation: When Historical Trajectories over Road Networks Matter	2020	SIGMOD	7.5760668e-05
4,135	ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects	2008	SIGMOD	6.7843671e-05
4,851	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.377837e-05
5,745	VRE: A Versatile, Robust, and Economical Trajectory Data System	2022	VLDB	6.0070567e-05
6,598	PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories	2021	VLDB	5.7383366e-05
7,306	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5571749e-05
8,186	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3800965e-05
9,436	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.1763176e-05
10,172	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.0658661e-05

Semantically Similar Papers

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