Search of Continuous Nearest Target Objects along Route on Large Hierarchical Road Network
Jun Feng, Toyohide Watanabe · 2003
The query of continuous nearest target objects for a specific route on road network is of primary interest in geo- graphical information systems. Existing methods for computing continuous nearest neighbor (CNN) are based on straight-line distance between points on the assumption that the whole graph can be stored in main memory. We have proposed a fast method for searching continuous nearest target objects along a route on road network. CNN search based on road network is composed of two steps: one is locating a computation point on the route; and another is searching the nearest object for this computation point based on the shortest path in the road network. We proposed heuristics for generating computation points and the region for searching the shortest path based on the intermediate results. By using our method, all the search processes can be limited to the corresponding search region, and the CNN search process can be greatly accelerated. However, when the whole graph cannot be stored in the main memory, the previous method cannot handle the problem. In this paper, we present a fast method for searching CNN on a large road network. The objective is not to artificially introduce hierarchy into a network model, but rather to investigate a search method based on the networks which bear a natural hierarchy and natural partition.