Distributed Databases in Dynamic R-Tree for Vehicle Information Systems

Information and communication systems for vehicles are getting significant like ETC (electronic toll collection) and car navigation systems. In the next generation navigation systems, each vehicle can not only receive various types of information like maps and traffic but also obtain traffic information around the vehicle by using the sensors and send them to a navigation center. It is critical to discuss how to store information collected by vehicles in databases and how vehicles access the information in the database in the presence of a huge number of vehicles on roads. In this paper, we propose an enhanced dynamic R-tree (EDR-tree) scheme to store and retrieve traffic data collected by vehicles in dynamic distributed database systems. In distributed tree-structured indexes like R-tree and B-tree, the root node and nodes at upper layers easily get performance bottleneck and points of failure since every query request is transferred from root to leaf node. In this paper, we propose a new tree-structured scheme named EDR-tree to store data. A road is realized as a sequence of road units. A geographical space of roads is separated into area units where road units are stored. An area unit is stored in a leaf node and there is a tree-structured index on the leaf nodes like B⁺-tree and R-tree. Each vehicle first makes an access to a leaf node, not the root, which has information of a road unit where the vehicle is currently moving. Then, a query request is efficiently and reliably delivered to a target node by using not only parent-child links but also enhancing links, sibling and adjacent links. We evaluate the EDR-tree in terms of search time and insertion time.