The B+-tree-based Method for Nearest Neighbor Queries in Traffic Simulation Systems

Abstract

Extensive used traffic simulation systems are helpfulin planning and controlling the traffic system. In traffic sim-ulation systems, the state of each vehicle is affected by thatof nearby vehicles, called neighbors. Nearest neighbor (NN) queries, which are multi 1-dimensional and highly concurrent,largely determine the performance of traffic simulation systems. Majority of existing traffic simulation systems use Linked list-based methods to process NN queries. Although simple andeffective they are, existing methods are neither scalable nore fficient. In this paper, we propose a B+-tree-based method to improve the efficiency of NN queries by borrowing ideas from methods used in databases. In particular, we create a linked local B+-tree, called LLB+-tree, which is a variation of Original B+-tree, to maintain the index of neighbors of each vehicle. We also build a mathematical model to optimize the parameter setting of LLB+-tree according to multiple parameters for lanes and vehicles. Our theoretical analysis shows that the time complexityof the method is O(logN) under the assumption of randomly distribution of vehicles. Our simulation results show that LLB+-tree can outperform Linked list and Original B+-tree by 64.2%and 12.8%, respectively.