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: 7022
Venue: SIGMOD
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,193 | 23.21%
DOI: 10.1145/3677130

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

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 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012962576
1,135	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00012032847
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
1,202	Fractals for Secondary Key Retrieval	1989	PODS	0.00011672157
1,418	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010835539
1,840	Effectively Learning Spatial Indices	2020	VLDB	9.6404567e-05
2,046	Distributed Trajectory Similarity Search	2017	VLDB	9.260657e-05
2,282	The MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries	2001	VLDB	8.8103794e-05
2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.6753909e-05
2,416	DITA: Distributed In-Memory Trajectory Analytics	2018	SIGMOD	8.6068712e-05
2,853	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	8.0383547e-05
3,345	Effective Travel Time Estimation: When Historical Trajectories over Road Networks Matter	2020	SIGMOD	7.4975085e-05
4,043	ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects	2008	SIGMOD	6.9403241e-05
4,751	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.5241784e-05
6,472	PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories	2021	VLDB	5.8700652e-05
7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.6873519e-05
7,155	VRE: A Versatile, Robust, and Economical Trajectory Data System	2022	VLDB	5.6869288e-05
8,003	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.5084586e-05
9,254	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.297624e-05
9,974	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.1845938e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,124	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB
2	3,792	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
3	7,708	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB
4	7,939	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB
5	11,881	The Maximum Trajectory Coverage Query in Spatial Databases	2019	VLDB
6	8,003	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB
7	4,316	Searching Trajectories by Locations - An Efficiency Study	2010	SIGMOD
8	5,091	Budget-aware Index Tuning with Reinforcement Learning	2022	SIGMOD
9	2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
10	4,751	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD