TY - JOUR
T1 - ROAD
T2 - A new spatial object search framework for road networks
AU - Lee, Ken C.K.
AU - Lee, Wang Chien
AU - Zheng, Baihua
AU - Tian, Yuan
N1 - Funding Information:
In this research work, Wang-Chien Lee, Ken C. K. Lee, and Yuan Tian were supported in part by US National Science Foundation (NSF) grants CNS-0626709, IIS-0534343, IIS-0328881 and Taiwan National Science Council grant 98-2219-E-001-001; and Ken C. K. Lee was partly supported by UMass Dartmouth Healey Grant 2011.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84863019892&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863019892&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2010.243
DO - 10.1109/TKDE.2010.243
M3 - Article
AN - SCOPUS:84863019892
SN - 1041-4347
VL - 24
SP - 547
EP - 560
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 3
M1 - 5645632
ER -