Reinforcement Learning based Tree Decomposition for Distance Querying in Road Networks

Computing the shortest path distance between two vertices in a road network is a building block in numerous applications. To do so efficiently, the state-of-the-art proposals adopt a tree decomposition process with heuristic strategies to build 2-hop label indexes. However, these indexes suffer from large space overheads caused by either tree imbalance or a large tree height. Independently of this, reinforcement learning has recently show impressive performance at sequential decision making in spatial data management tasks. We observe that tree decomposition is naturally a sequential decision making problem that decides which vertex to process at each step. In this paper, we propose a reinforcement learning based tree decomposition (RLTD) approach that reduces the space overhead significantly. We model tree decomposition as a Markov Decision Process, exploiting features of both the network topological structure and the tree structure. We further optimize the tree decomposition process by taking the network density into account, which yields a great generalization of the model on large road networks. Extensive experiments with real-world data offer insights into the performance of the proposals, showing that they are able to reduce the space overhead by about 51% and achieve on average about 14% speedup for queries with almost the same preprocessing time when compared with the state-of-the-art proposals.