Indexing moving objects on transportation networks

Database applications dealing with spatial objects that continuously change their position over time is gaining an increased interest. The goal is to store and query the positions of these objects. Index structures were proposed to achieve this goal. While index structures are designed mainly for unconstrained movement, databases in transportation networks are characterized by not only the speed to retrieve the spatial location of a moving object but also by their constrained movement. Moreover, in a constrained space, traditional indexing methods usually experience longer time in retrieving spatial location of a moving object. Therefore dynamic index structure is needed to efficiently locate moving objects. This paper proposes an efficient and dynamic index structure called transportation network R⁺-Tree (TNR⁺-Tree). The proposed structure meets the above requirements and gives algorithms for searching and updating the structure. Analytical results show that TNR⁺-Tree achieves up to 50% savings in disk accesses when searching files of thousands of rectangles.