BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data
Open Access
- 30 September 2024
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (4) , 1-27
Abstract
With the increasing availability of trajectory data, it is important to have good indexes to facilitate query processing. In this work, we propose BT-Tree, which is built through a recursive bi-partitioning approach, for the processing of range and KNN queries for past trajectory data. We first propose a cost function based method (CFBM) to build the BT-Tree. Specifically, we design a novel cost function, which incorporates the characteristics of both the data and historical query workload, to decide how to partition a BT-Tree node. Then we propose a reinforcement learning (RL) based method to address CFBM's limitations, such as making locally optimal decisions that may lead to global suboptimality. Experiments on three real datasets with up to 800 million data points show that the CFBM generally outperforms the baselines in terms of query processing time and the RL based method consistently outperforms the baselines and has more significant advantages on larger datasets.Keywords
This publication has 45 references indexed in Scilit:
- Tinba: Incremental partitioning for efficient trajectory analyticsAdvanced Engineering Informatics, 2023
- SQUID: subtrajectory query in trillion-scale GPS databaseThe VLDB Journal, 2023
- X-FIST: Extended flood index for efficient similarity search in massive trajectory datasetInformation Sciences, 2022
- GCOTraj: A storage approach for historical trajectory data sets using grid cells orderingInformation Sciences, 2018
- Human-level control through deep reinforcement learningNature, 2015
- Indexing in-network trajectory flowsThe VLDB Journal, 2011
- Optimized algorithms for predictive range and KNN queries on moving objectsInformation Systems, 2010
- The B dual -Tree: indexing moving objects by space filling curves in the dual spaceThe VLDB Journal, 2006
- The TPR*-Tree2003
- Kinetic Medians and kd-Trees2002