Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-26T19:46:24.741Z Has data issue: false hasContentIssue false
  • English
  • Français

Time constraint route search over multi-locations

Published online by Cambridge University Press:  21 March 2014

Geng Zhao ,
Kefeng Xuan ,
David Taniar ,
Maytham Safar  and
Bala Srinivasan
Geng Zhao
Affiliation:
Clayton School of Information Technology, Monash University, Australia; e-mail: [email protected]
Kefeng Xuan
Affiliation:
Clayton School of Information Technology, Monash University, Australia; e-mail: [email protected]
David Taniar
Affiliation:
Clayton School of Information Technology, Monash University, Australia; e-mail: [email protected]
Maytham Safar
Affiliation:
Department of Computer Engineering, Kuwait University, Kuwait
Bala Srinivasan
Affiliation:
Clayton School of Information Technology, Monash University, Australia; e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Traditional Route Search aims at finding the path that goes through geographical entities that are relevant to the provided search terms from the start point to the end point. Without constraints, traditional Route Search visiting multiple locations is unreliable because locations may close after a specified time. In this paper, time constraint (operating hours of each location) is drawn into Route Search query in order to make the query more realistic. Two methods are proposed in this paper, namely Route Search for fixed locations (RFix) and Route Search for flexible locations (RFlex). These two queries are different from the existing Route Search query because (1) the end point is not pre-defined and (2) time constraint is involved. Our two proposal queries consider whether the locations are specifically pre-defined by the user or only the location types are specified. In each method, two propositions are presented for pruning expansion branches, which highly improves the performance. Our experiments verified the applicability of RFix and RFlex to solve Route Search queries with time constraint queries.

Type
Articles
Information
The Knowledge Engineering Review , Volume 29 , Issue 2 , March 2014 , pp. 217 - 233
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Dijkstra, E. W. 1959. A note on two problems in connection with graphs. Numerische Mathematik 1(22), 269–271.Google Scholar
Ehliar, A., Liu, D. 2005. Flexible route lookup using range search. In Communications and Computer Networks, Sanadidi, M. Y. (ed.). IASTED/ACTA Press, 345–350, ISBN 0-88986-546-9.Google Scholar
Goh, J., Taniar, D. 2004a. Mining frequency pattern from mobile users. In KES, Lecture Notes in Computer Science, Negoita, M. G., Howlett, R. J. & Jain, L. C. (eds), 3215, 795–801. Springer, ISBN 3-540-23205-2.Google Scholar
Goh, J. Y., Taniar, D. 2004b. Mobile data mining by location dependencies. In IDEAL, Lecture Notes in Computer Science, Yang, Z. R., Everson, R. M. & Yin, H. (eds), 3177, 225–231. Springer, ISBN 3-540-22881-0.Google Scholar
Huang, X., Jensen, C. S. 2004. In-route skyline querying for location-based services. In W2GIS, Lecture Notes in Computer Science, Kwon, Y. J., Bouju, A. & Claramunt, C. (eds), 3428, 120–135. Springer, ISBN 3-540-26004-8.Google Scholar
Ilarri, S., Mena, E., Illarramendi, A., Yus, R., Laka, M., Marcos, G. 2012. A friendly location-aware system to facilitate the work of technical directors when broadcasting sport events. Mobile Information Systems 8(1), 17–43.Google Scholar
Kanza, Y., Safra, E., Sagiv, Y. 2009. Route search over probabilistic geospatial data. In SSTD, Lecture Notes in Computer Science, Mamoulis, N., Seidl, T., Pedersen, T. B., Torp, K. & Assent, I. (eds), 5644, 153–170. Springer, ISBN 978-3-642-02981-3.Google Scholar
Kanza, Y., Safra, E., Sagiv, Y., Doytsher, Y. 2008b. Heuristic algorithms for route-search queries over geographical data. In Proceedings of ACM GIS, Aref, W. G., Mokbel, M. F. & Schneider, M. (eds). Irvine, California, USA, 11. ACM Press, November.CrossRefGoogle Scholar
Kolahdouzan, M. R., Shahabi, C. 2004. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of 30th VLDB, Nascimento, M. A., Özsu, M. T., Kossmann, D., Miller, R. J., Blakeley, J. A. & Schiefer, K. B. (eds). Toronto, Canada, 840–851. Morgan Kaufmann Publishers Inc., ISBN 0-12-088469-0.Google Scholar
Ku, W.-S., Zimmermann, R., Wang, H., Wan, C.-N. 2005. Adaptive nearest neighbor queries in travel time networks. In Proceedings of ACM GIS, Shahabi, C. & Boucelma, O. (eds). Bremen, Germany, 210–219. ACM Press, November.Google Scholar
Mammeri, Z., Morvan, F., Hameurlain, A., Marsit, N. 2009. Location-dependent query processing under soft real-time constraints. Mobile Information Systems 5, 205–232.Google Scholar
Okabe, A., Boots, B., Sugihara, K., Chiu, S. N. 2000. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edition. John Wiley and Sons Ltd.Google Scholar
Papadias, D., Zhang, J., Mamoulis, N., Tao, Y. 2003. Query processing in spatial network databases. In Proceedings of 29th VLDB, Freytag, J. C., Lockemann, P. C., Abiteboul, S., Carey, M. J., Selinger, P. G. & Heuer, A. (eds). Berlin, Germany, 802–813. Morgan Kaufmann Publishers Inc., ISBN 0-12-722442-4.Google Scholar
Pearson, J., Guesgen, H. W. 1998. Some experimental results of applying heuristic search to route finding. In Proceedings of FLAIRS Conference, Cook D. J. (ed.). Sanibel Island, Florida, USA, 394–398. AAAI Press, ISBN 1-57735-051-0.Google Scholar
Roussopoulos, N., Kelley, S., Vincent, F. 1995. Nearest neighbor queries. In Proceedings of ACM SIGMOD, San Jose, California, 71–79. ACM Press.Google Scholar
Safar, M. 2005. K nearest neighbor search in navigation systems. Mobile Information Systems 1(3), 207–224.Google Scholar
Taniar, D., Goh, J. 2007. On mining movement pattern from mobile users. IJDSN 3(1), 69–86.Google Scholar
Taniar, D., Rahayu, J. W. 2002. A taxonomy of indexing schemes for parallel database systems. Distributed and Parallel Databases 12(1), 73–106.Google Scholar
Taniar, D., Rahayu, J. W. 2004. Global parallel index for multi-processors database systems. Information Science 165(1–2), 103–127.Google Scholar
Taniar, D., Rahayu, W. 2013. A taxonomy for nearest neighbour queries in spatial databases. Journal of Computer and System Sciences 79(7), 1017–1039.Google Scholar
Terrovitis, M., Bakiras, S., Papadias, D., Mouratidis, K. 2005. Constrained shortest path computation. In Proceedings of SSTD, Lecture Notes in Computer Science, Medeiros, C. B., Egenhofer, M. J. & Bertino, E. (eds), 3633, 181–199. Springer, ISBN 3-540-28127-4.Google Scholar
Waluyo, A. B., Srinivasan, B., Taniar, D. 2003. Optimal broadcast channel for data dissemination in mobile database environment. In Proceedings of APPT, Lecture Notes in Computer Science, Zhou, X., Jähnichen, S., Xu, M. & Cao, J. (eds), 2834, 655–664. Springer, ISBN 3-540-20054-1.Google Scholar
Waluyo, A. B., Srinivasan, B., Taniar, D. 2004. A taxonomy of broadcast indexing schemes for multi channel data dissemination in mobile database. In Proceedings of AINA. IEEE Computer Society, Fukuoka, Japan, 213–218, ISBN 0-7695-2051-0.Google Scholar
Waluyo, A. B., Srinivasan, B., Taniar, D. 2005b. Research in mobile database query optimization and processing. Mobile Information Systems 1(4), 225–252.Google Scholar
Xuan, K., Zhao, G., Taniar, D., Safar, M., Srinivasan, B. 2011. Voronoi-based multi-level range search in mobile navigation. Multimedia Tools and Applications 53(2), 459–479.Google Scholar
Xuan, K., Zhao, G., Taniar, D., Srinivasan, B. 2008. Continuous range search query processing in mobile navigation. In Proceedings of ICPADS. IEEE, Melbourne, Australia, 361–368.Google Scholar
Xuan, K., Zhao, G., Taniar, D., Rahayu, W., Safar, M., Srinivasan, B. 2011. Voronoi-based range and continuous range query processing in mobile databases. Journal of Computer and System Sciences 77(4), 637–651.Google Scholar
Yoo, J. S., Shekhar, S. 2005. In-route nearest neighbor queries. GeoInformatica 9(4), 117–137.Google Scholar
Zhang, Q. 2008. Hierarchical route representation, indexing, and search. IEEE Pervasive Computing 7(2), 78–84.Google Scholar
Zhao, G., Xuan, K., Rahayu, W., Taniar, D., Safar, M., Gavrilova, M., Srinivasan, B. 2011. Voronoi-based continuous k nearest neighbor search in mobile navigation. IEEE Transactions on Industrial Electronics 58(6), 2247–2257CrossRefGoogle Scholar
Zhao, G., Xuan, K., Taniar, D. 2013. Path kNN query processing in mobile systems. IEEE Transactions on Industrial Electronics 60(3), 1099–1107.Google Scholar