The multi-rule partial sequenced route query

ABSTRACT

Trip planning search (TPS) represents an important class of queries in Geographic Information Systems (GIS). In many real-world applications, TPS requests are issued with a number of constraints. Unfortunately, most of these constrained TPS cannot be directly answered by any of the existing algorithms. By formulating each restriction into rules, we propose a novel form of route query, namely the multi-rule partial sequenced route (MRPSR) query. Our work provides a unified framework that also subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. In this paper, we first prove that MRPSR is NP-hard and then present three heuristic algorithms to search for near-optimal solutions for the MRPSR query. Our extensive simulations show that all of the proposed algorithms can answer the MRPSR query effectively and efficiently. Using both real and synthetic datasets, we investigate the performance of our algorithms with the metrics of the route distance and the response time in terms of the percentage of the constrained points of interest (POI) categories. Compared to the LORD-based brute-force solution, the response times of our algorithms are remarkably reduced while the resulting route length is only slightly longer than the shortest route.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Catriel Beeri , Yaron Kanza , Eliyahu Safra , Yehoshua Sagiv, Object fusion in geographic information systems, Proceedings of the Thirtieth international conference on Very large data bases, p.816-827, August 31-September 03, 2004, Toronto, Canada
• 3: L. F. Escudero. An Inexact Algorithm for the Sequential Ordering Problem. European Journal of Operational Research, 37(2):236--249, 1988.
• 4: B. George, S. Kim, and S. Shekhar. Spatio-temporal Network Databases and Routing Algorithms: A Summary of Results. In Proceedings of the 10th International Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 460--477, 2007.
• 5: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 6: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 7: Ellis Horowitz , Sartaj Sahni , Susan Anderson-Freed, Fundamentals of Data Structures in C, W. H. Freeman & Co., New York, NY, 1992
• 8: 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]
• 9: A. B. Kahn, Topological sorting of large networks, Communications of the ACM, v.5 n.11, p.558-562, Nov. 1962 [doi>10.1145/368996.369025]
• 10: 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
• 11: Wei-Shinn Ku , Roger Zimmermann , Haojun Wang , Chi-Ngai Wan, Adaptive nearest neighbor queries in travel time networks, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097094]
• 12: F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On Trip Planning Queries in Spatial Databases. In Proceedings of the 9th International Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 273--290, 2005.
• 13: Xiaobin Ma , Shashi Shekhar , Hui Xiong , Pusheng Zhang, Exploiting a page-level upper bound for multi-type nearest neighbor queries, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183501]
• 14: 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
• 15: Raj Reddy, To dream the possible dream, Communications of the ACM, v.39 n.5, p.105-112, May 1996 [doi>10.1145/229459.233436]
• 16: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 17: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 18: Hanan Samet, Issues, developments, and challenges in spatial databases and geographic information systems (GIS) (Invited Talk), Proceedings of the 9th ACM international symposium on Advances in geographic information systems, p.1-1, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512162]
• 19: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 20: Mehdi Sharifzadeh , Mohammad Kolahdouzan , Cyrus Shahabi, The optimal sequenced route query, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.4, p.765-787, July 2008 [doi>10.1007/s00778-006-0038-6]
• 21: Shashi Shekhar , Mark Coyle , Brajesh Goyal , Duen-Ren Liu , Shyamsundar Sarkar, Data models in geographic information systems, Communications of the ACM, v.40 n.4, p.103-111, April 1997 [doi>10.1145/248448.248465]
• 22: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 23: M. Terrovitis, S. Bakiras, D. Papadias, and K. Mouratidis. Constrained Shortest Path Computation. In Proceedings of the 9th International Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 181--199, 2005.
• 24: Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872812]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms

Keywords:
advanced traveler information systems, location-based services