Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2014 Volume 29
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Time constraint route search over multi-locations

  • 1.

    Clayton School of Information Technology

  • 2.

    Department of Computer Engineering

More Information
  • 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.
  • 加载中
  • Dijkstra E. W.1959. A note on two problems in connection with graphs. Numerische Mathematik1(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 Systems8(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.

    Google 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 Systems5, 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 Systems1(3), 207–224.

    Google Scholar

    Taniar D., Goh J.2007. On mining movement pattern from mobile users. IJDSN3(1), 69–86.

    Google Scholar

    Taniar D., Rahayu J. W.2002. A taxonomy of indexing schemes for parallel database systems. Distributed and Parallel Databases12(1), 73–106.

    Google Scholar

    Taniar D., Rahayu J. W.2004. Global parallel index for multi-processors database systems. Information Science165(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 Sciences79(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 Systems1(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 Applications53(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 Sciences77(4), 637–651.

    Google Scholar

    Yoo J. S., Shekhar S.2005. In-route nearest neighbor queries. GeoInformatica9(4), 117–137.

    Google Scholar

    Zhang Q.2008. Hierarchical route representation, indexing, and search. IEEE Pervasive Computing7(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 Electronics58(6), 2247–2257

    Google Scholar

    Zhao G., Xuan K., Taniar D.2013. Path kNN query processing in mobile systems. IEEE Transactions on Industrial Electronics60(3), 1099–1107.

    Google Scholar

  • Cite this article

    Geng Zhao, Kefeng Xuan, David Taniar, Maytham Safar, Bala Srinivasan. 2014. Time constraint route search over multi-locations. The Knowledge Engineering Review 29(2)217−233, doi: 10.1017/S0269888914000058
    Geng Zhao, Kefeng Xuan, David Taniar, Maytham Safar, Bala Srinivasan. 2014. Time constraint route search over multi-locations. The Knowledge Engineering Review 29(2)217−233, doi: 10.1017/S0269888914000058
    shu
Download PDF

Article Metrics

Article views(24) PDF downloads(52)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Time constraint route search over multi-locations

  • 1.

    Clayton School of Information Technology

  • 2.

    Department of Computer Engineering

  • Published online: 21 March 2014
The Knowledge Engineering Review  29,  2014, 29(2): 217−233  |  Cite this article

Abstract: 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.

    HTML

    Acknowledgments

    • This research has been partially funded by the Australian Research Council (ARC) Discovery Project (Project No: DP0987687).

    Rights and permissions
    • Copyright © Cambridge University Press 2014 2014Cambridge University Press
References (31)
  • About this article
    Cite this article
    Geng Zhao, Kefeng Xuan, David Taniar, Maytham Safar, Bala Srinivasan. 2014. Time constraint route search over multi-locations. The Knowledge Engineering Review 29(2)217−233, doi: 10.1017/S0269888914000058
    Geng Zhao, Kefeng Xuan, David Taniar, Maytham Safar, Bala Srinivasan. 2014. Time constraint route search over multi-locations. The Knowledge Engineering Review 29(2)217−233, doi: 10.1017/S0269888914000058
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return