Acceleration technique of snake-shaped regions retrieval method for telematics navigation service system

Telematics services, which provide traffic information such as route guidance, congestion warnings, etc. via a wireless communication network, have spread recently. The demand is growing for graphical guide information to be provided in addition to the conventional service that provides text only guidance. To improve graphical service, we propose a new retrieval method. This method enables fast extraction of map objects within a snake-shaped region (SSR) along a driving route from a geo-spatial database that stores map data without rectangular mesh boundaries. For this retrieval method, we have considered three techniques. The first is based on simplification of the snake-shaped route region through point elimination, and the second is based on reduction of the processing load of the geometrical intersection detection processes. This second technique is accomplished by dividing the snake-shaped region into multiple cells, and the third is multiple distributions of the SSR retrieval result to terminals for quick start of navigation processing. We have developed a prototype to evaluate the performance of the proposed methods. The prototype provides route guidance information for an actual terminal, and uses information taken from United States road maps. Even in an urban area, we managed to provide an approximately 200-mile route of guide information within 10 seconds. We are convinced that the proposed method can be applied to actual telematics services.