Design of a Shape File Index for Fast Map Matching in Electric Vehicle Services

Mainly targeting at a small-city level road network, this paper builds an in-memory index for fast map matching, one of the most fundamental building blocks for vehicle information services. For the ESRI shape file sequentially storing road objects such as intersections and links, our indexing scheme obtains the offset of each link and creates the corresponding record consisting of link id, two end points, and the offset. Along with node entries, each of which includes all emanating links for a node, this index makes it possible to traverse the shape file just like Dijkstra's shortest path algorithm, while all index traversal steps are done within memory. The previous location of a vehicle gives the start point of a map match process, significantly reducing the number of links to check if they include a specific point. This scheme particularly helps us to build an analyzer application for a series of spatiotemporal streams such as battery discharge dynamics.