A fast unified optimal route query evaluation algorithm

ABSTRACT

We investigate the problem of how to evaluate, fast and efficiently, classes of optimal route queries on a massive graph in a unified framework. To evaluate a route query effectively, a large network is partitioned into a collection of fragments, and distances of some optimal routes in the network are pre-computed. Under such a setting, we find a unified algorithm that can evaluate classes of optimal route queries. The classes that can be processed efficiently are called constraint preserving (CP) which include, among others, shortest path, forbidden edges, forbidden nodes and α-autonomy optimal route query classes. We prove the correctness of the unified algorithm. We then turn our attention to the optimization of the proposed algorithm. Several pruning and optimization techniques are derived that minimize the search time and I/O accesses. We show empirically that these techniques are effective. The proposed optimal route query evaluation algorithm, with all these techniques incorporated, is compared with a main-memory and a disk-based brute-force CP algorithms. We show experimentally that the proposed unified algorithm outperforms the brute-force algorithms, both in term of CPU time and I/O cost, by a wide margin.

REFERENCES

• 1: R. Agrawal , H. V. Jagadish, Algorithms for Searching Massive Graphs, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.225-238, April 1994 [doi>10.1109/69.277767 ]
• 2: Edward P. Chan , Heechul Lim, Optimization and evaluation of shortest path queries, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.3, p.343-369, July 2007 [doi>10.1007/s00778-005-0177-1]
• 3: Liang Guo , Ibrahim Matta, Search space reduction in QoS routing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.1, p.73-88, 15 January 2003 [doi>10.1016/S1389-1286(02)00344-4 ]
• 4: Li, F., Cheng, D., Hadjieleftheriou, M., Kollios, G. and Teng, S.-H.,"On Trip Planning Queries in Spatial Databases," Proceedings of the 9th International Symposium on Spatial and Temporal Databases, pp. 273--290.
• 5: Hutchinson, D., Maheshwari, A. and Zeh Z., "An External-Memory Data Structure for Shortest Path Queries," Proceedings of the 5th Annual Combinatorics and Computing Conference, Tokyo, July 26--28, 1999, Lecture Notes in Computer Science, Vol. 1627, Springer Verlag, pp. 51--60.
• 6: Korkmaz, T., and Krunz, M., "Multi-Constrained Optimal Path Selection," Proceedings of INFOCOM 2001, pp.834--843.
• 7: 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 ]
• 8: 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 ]
• 9: Juttner, A., Szviatovszki, B., Mecs, I., and Rajko, Z., "Lagrange Relaxation Based Method for the QoS Routing Problem, Proceedings of INFOCOM 2001, pp.859--868.
• 10: 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
• 11: Terrovitis, M., Bakiras, S., Papadias, D., and Mouratidis, K., "Constraint Shortest Path Computation", Proceedings of the 9th International Symposium on Spatial and Temporal Databases, pp.181--199.
• 12: Tiger/Line Files, US Department of Commerce Economics and Statistics Administration, Bureau of Census, 1998.
• 13: Michalis Vazirgiannis , Ouri Wolfson, A Spatiotemporal Model and Language for Moving Objects on Road Networks, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.20-35, July 12-15, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
distance materialization, optimal route queries, route query evaluation