Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this paper, we present ROAD, a general framework to evaluate Location-Dependent Spatial Queries (LDSQ)s that searches for spatial objects on road networks. By exploiting search space pruning technique and providing a dynamic object mapping mechanism, ROAD is very efficient and flexible for various types of queries, namely, range search and nearest neighbor search, on objects over large-scale networks. ROAD is named after its two components, namely, Route Overlay and Association Directory, designed to address the network traversal and object access aspects of the framework. In ROAD, a large road network is organized as a hierarchy of interconnected regional sub-networks (called Rnets) augmented with 1) shortcuts for accelerating network traversals; and 2) object abstracts for guiding traversals. In this paper, we present (i) the Rnet hierarchy and several properties useful to construct Rnet hierarchy, (ii) the design and implementation of the ROAD framework, (iii) efficient object search algorithms for various queries, and (iv) incremental update techniques for framework maintenance in presence of object and network changes. We conducted extensive experiments with real road networks to evaluate ROAD. The experiment result shows the superiority of ROAD over the state-of-the-art approaches.

REFERENCES

• 1: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 2: Hyung-Ju Cho , Chin-Wan Chung, An efficient and scalable approach to CNN queries in a road network, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Rina Dechter , Judea Pearl, Generalized best-first search strategies and the optimality of A*, Journal of the ACM (JACM), v.32 n.3, p.505-536, July 1985 [doi>10.1145/3828.3830]
• 4: E. W. Dijkstra. A Note on two Problems in Connexion with Graphs. In Numerische Mathematik, pages 269--271, 1959.
• 5: Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
• 6: Haibo Hu , Dik Lun Lee , Victor C. S. Lee, Distance indexing on road networks, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: H. Hu, D. L. Lee, and J. Xu. Fast Nearest Neighbor Search on Road Networks. In Proceedings of the 10th International Conference on Extending Database Technology (EDBT), Munich, Germany, Mar 26--31, pages 186--203, 2006.
• 8: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Effective graph clustering for path queries in digital map databases, Proceedings of the fifth international conference on Information and knowledge management, p.215-222, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238497]
• 9: Christian S. Jensen , Jan Kolářvr , Torben Bach Pedersen , Igor Timko, Nearest neighbor queries in road networks, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.1-8, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956677]
• 10: Ning Jing , Yun-Wu Huang , Elke A. Rundensteiner, Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.409-432, May 1998 [doi>10.1109/69.687976]
• 11: Sungwon Jung , Sakti Pramanik, An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.1029-1046, September 2002 [doi>10.1109/TKDE.2002.1033772]
• 12: B. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell Systems Technical Journal, 49(2):291--308, 1970.
• 13: Mohammad Kolahdouzan , Cyrus Shahabi, Voronoi-based K nearest neighbor search for spatial network databases, Proceedings of the Thirtieth international conference on Very large data bases, p.840-851, August 31-September 03, 2004, Toronto, Canada
• 14: F. Li. Real Datasets for Spatial Databases: Road Networks and Points of Interest. http://www.cs.fsu.edu/~lifeifei/SpatialDataset.htm.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: Dimitris Papadias , Jun Zhang , Nikos Mamoulis , Yufei Tao, Query processing in spatial network databases, Proceedings of the 29th international conference on Very large data bases, p.802-813, September 09-12, 2003, Berlin, Germany
• 17: B. R. Preiss. Data Structures and Algorithms with Object-Oriented Design Patterns in Java. 1998.
• 18: Shashi Shekhar , Duen-Ren Liu, CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.102-119, January 1997 [doi>10.1109/69.567054]
• 19: Man Lung Yiu , Nikos Mamoulis , Dimitris Papadias, Aggregate Nearest Neighbor Queries in Road Networks, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.820-833, June 2005 [doi>10.1109/TKDE.2005.87]
• 20: Donghui Zhang , J. Tsotras, Optimizing spatial Min/Max aggregations, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.170-181, April 2005 [doi>10.1007/s00778-004-0142-4]

INDEX TERMS

General Terms:
Algorithms

Keywords:
road network, spatial search