In this paper, we present a new system framework called ROAD for spatial object search on road networks. ROAD is extensible to diverse object types and efficient for processing various location-dependent spatial queries (LDSQs), as it maintains objects separately from a given network and adopts an effective search space pruning technique. Based on our analysis on the two essential operations for LDSQ processing, namely, network traversal and object lookup, ROAD organizes a large road network as a hierarchy of interconnected regional subnetworks (called Rnets). Each Rnet is augmented with 1) shortcuts and 2) object abstracts to accelerate network traversals and provide quick object lookups, respectively.
To manage those shortcuts and object abstracts, two cooperating indices, namely, Route Overlay and Association Directory are devised. In detail, we present 1) the Rnet hierarchy and several properties useful in constructing and maintaining the Rnet hierarchy, 2) the design and implementation of the ROAD framework, and 3) a suite of efficient search algorithms for single-source LDSQs and multisource LDSQs. We conduct a theoretical performance analysis and carry out a comprehensive empirical study to evaluate ROAD. The analysis and experiment results show the superiority of ROAD over the state-of-the-art approaches.
Existing works on processing LDSQs on road networks are categorized as solution-based approaches and extended spatial database approaches, extended spatial database approaches incorporate road networks to existing spatial databases. Two basic search strategies were studied. The first strategy is based on the idea of euclidean distance bound. New roads are constructed or existing roads are closed, the corresponding network topology is changed. We model these changes as addition or deletion of nodes and edges. Here, we treat changes of nodes as special cases of changes of edges, and only consider addition and deletion of edges below. Deleting an edge breaks the link between two nodes n and n0. Consider deleting in R2 in. Its deletion can be managed as handling the change of its edge distance to infinity and updating affected shortcuts. It is possible that one end node n of a deleted edge is a border node.
We propose two novel index structures, namely, Route Overlay and Association Directory (and ROAD is named after these two key components). The Distance browsing has been recently proposed based on the concept of path coherence that for any node n, all other nodes with their shortest paths from n via one of nís immediate neighboring nodes are spatially close. Based on this idea, shortest path quad-tree (SPQT). A new system framework for LDSQ processing, in this paper. The design of ROAD achieves a clear separation between objects and network for better system extensibility. It also exploits search space pruning, a powerful technique for efficient object search. Upon the framework, efficient search algorithms for single source and multisource LDSQs are devised. Via a comprehensive performance evaluation on real road networks, ROAD is shown to significantly outperform the state-of-the art techniques.
- Spatial Road Network
- Shortest Path
- Query Performance
- Edge Distance