Description

To present a new system framework called ROAD for spatial object search on road networks. ROAD isextensible to diverse object types and efficient for processing various location-dependent spatial queries (LDSQs), as it maintainsobjects separately from a given network and adopts an effective search space pruning technique. Based on our analysis on the twoessential operations for LDSQ processing, namely, network traversal and object lookup, ROAD organizes a large road network as ahierarchy of interconnected regional subnetworks (called Rnets). Each Rnet is augmented with 1) shortcuts and 2) object abstracts toaccelerate network traversals and provide quick object lookups, respectively. To manage those shortcuts and object abstracts, twocooperating indices, namely, Route Overlay and Association Directory are devised. In detail, we present 1) the Rnet hierarchy andseveral properties useful in constructing and maintaining the Rnet hierarchy, 2) the design and implementation of the ROADframework, and 3) a suite of efficient search algorithms for single-source LDSQs and multisource LDSQs. We conduct a theoreticalperformance analysis and carry out a comprehensive empirical study to evaluate ROAD. The analysis and experiment results show thesuperiority of ROAD over the state-of-the-art approaches.