La Ku Labot

ROAD: A New Spatial Object Search

             Framework for Road Networks

Abstract:

             We present a new system framework called ROAD for spatial object search on road networks. the ROAD is Extensible to diverse object types and efficient for processing various location-dependent spatial queries (LDSQs).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 sub networks (called Rents). Each Rent 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 Rent hierarchy and several properties useful in constructing and maintaining the Rent 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. The analysis and experiment results show the superiority of ROAD over the state-of-the-art approaches.     

Existing System:

• Ø Existing works on processing LDSQs on road networks are categorized as solution-based approaches and extended spatial database approaches.

• As solution-based approaches: Distance Index precomputes for all needs to traverse the network in a node by node fashion.

• Ø Bulky Spots accessed for all visited nodes make this approach very I/O-inefficient. While the design and implementation of HEPV and HiTi only allow point-to-point shortest path searches.

• Our ROAD facilitates network expansion to reach multiple destinations for objects.

• Ø Extended spatial database approaches: Two basic search strategies were studied.

• Ø The first strategy is based on the idea of Euclidean distance bound approaches first identify...