Skip to main content
Erschienen in: GeoInformatica 1/2018

07.01.2017

Efficient evaluation of shortest travel-time path queries through spatial mashups

verfasst von: Detian Zhang, Chi-Yin Chow, An Liu, Xiangliang Zhang, Qingzhu Ding, Qing Li

Erschienen in: GeoInformatica | Ausgabe 1/2018

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the real world, the route/path with the shortest travel time in a road network is more meaningful than that with the shortest network distance for location-based services (LBS). However, not every LBS provider has adequate resources to compute/estimate travel time for routes by themselves. A cost-effective way for LBS providers to estimate travel time for routes is to issue external route requests to Web mapping services (e.g., Google Maps, Bing Maps, and MapQuest Maps). Due to the high cost of processing such external route requests and the usage limits of Web mapping services, we take the advantage of direction sharing, parallel requesting and waypoints supported by Web mapping services to reduce the number of external route requests and the query response time for shortest travel-time route queries in this paper. We first give the definition of sharing ability to reflect the possibility of sharing the direction information of a route with others, and find out the queries that their query routes are independent with each other for parallel processing. Then, we model the problem of selecting the optimal waypoints for an external route request as finding the longest simple path in a weighted complete digraph. As it is a MAX SNP-hard problem, we propose a greedy algorithm with performance guarantee to find the best set of waypoints in an external route request. We evaluate the performance of our approach using a real Web mapping service, a real road network, real and synthetic data sets. Experimental results show the efficiency, scalability, and applicability of our approach.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
If R(o i d i ) is directional, o j and d j should locate in the route in order.
 
Literatur
1.
Zurück zum Zitat Bruno N, Chaudhuri S, Gravano L (2001) Stholes: a multidimensional workload-aware histogram. In: ACM SIGMOD Bruno N, Chaudhuri S, Gravano L (2001) Stholes: a multidimensional workload-aware histogram. In: ACM SIGMOD
2.
Zurück zum Zitat Bruno N, Gravano L, Marian A (2002) Evaluating top-k queries over web-accessible databases. In: IEEE ICDE Bruno N, Gravano L, Marian A (2002) Evaluating top-k queries over web-accessible databases. In: IEEE ICDE
3.
Zurück zum Zitat Chang KCC, Hwang SW (2002) Minimal probing: supporting expensive predicates for top-k queries. In: ACM SIGMOD Chang KCC, Hwang SW (2002) Minimal probing: supporting expensive predicates for top-k queries. In: ACM SIGMOD
4.
Zurück zum Zitat Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press
5.
Zurück zum Zitat Demiryurek U, Banaei-Kashani F, Shahabi C, Ranganathan A (2011) Online computation of fastest path in time-dependent spatial networks. In: SSTD Demiryurek U, Banaei-Kashani F, Shahabi C, Ranganathan A (2011) Online computation of fastest path in time-dependent spatial networks. In: SSTD
6.
Zurück zum Zitat Ding B, Yu JX, Qin L (2008) Finding time-dependent shortest paths over large graphs. In: EDBT Ding B, Yu JX, Qin L (2008) Finding time-dependent shortest paths over large graphs. In: EDBT
7.
Zurück zum Zitat George B, Kim S, Shekhar S (2007) Spatio-temporal network databases and routing algorithms: a summary of results. In: SSTD George B, Kim S, Shekhar S (2007) Spatio-temporal network databases and routing algorithms: a summary of results. In: SSTD
10.
Zurück zum Zitat Gutin G, Punnen AP (2006) The traveling salesman problem and its variations. Springer Science & Business Media Gutin G, Punnen AP (2006) The traveling salesman problem and its variations. Springer Science & Business Media
11.
Zurück zum Zitat Huang X, Cheng H, Li RH, Qin L, Yu JX (2013) Top-k structural diversity search in large networks. VLDB J 6(13):1618–1629 Huang X, Cheng H, Li RH, Qin L, Yu JX (2013) Top-k structural diversity search in large networks. VLDB J 6(13):1618–1629
13.
Zurück zum Zitat Kosaraju SR, Park JK, Stein C (1994) Long tours and short superstrings. In: FOCS Kosaraju SR, Park JK, Stein C (1994) Long tours and short superstrings. In: FOCS
14.
Zurück zum Zitat Levandoski JJ, Mokbel MF, Khalefa ME (2010) Preference query evaluation over expensive attributes. In: CIKM Levandoski JJ, Mokbel MF, Khalefa ME (2010) Preference query evaluation over expensive attributes. In: CIKM
15.
Zurück zum Zitat Li J, Liu C, Liu B, Mao R, Wang Y, Chen S, Yang JJ, Pan H, Wang Q (2015) Diversity-aware retrieval of medical records. Comput Ind 69:81–91CrossRef Li J, Liu C, Liu B, Mao R, Wang Y, Chen S, Yang JJ, Pan H, Wang Q (2015) Diversity-aware retrieval of medical records. Comput Ind 69:81–91CrossRef
16.
Zurück zum Zitat Li Y, Yiu ML (2015) Route-saver: leveraging route apis for accurate and efficient query processing at location-based services. IEEE TKDE 27(1):235–249 Li Y, Yiu ML (2015) Route-saver: leveraging route apis for accurate and efficient query processing at location-based services. IEEE TKDE 27(1):235–249
17.
Zurück zum Zitat Liu A, Zheng K, Li L, Liu G, Zhao L, Zhou X (2015) Efficient secure similarity computation on encrypted trajectory data. In: IEEE ICDE, pp 66–77 Liu A, Zheng K, Li L, Liu G, Zhao L, Zhou X (2015) Efficient secure similarity computation on encrypted trajectory data. In: IEEE ICDE, pp 66–77
18.
Zurück zum Zitat Lu M, Tang Y, Sun R, Wang T, Chen S, Mao R (2015) A real time displacement estimation algorithm for ultrasound elastography. Comput Ind 69:61–71CrossRef Lu M, Tang Y, Sun R, Wang T, Chen S, Mao R (2015) A real time displacement estimation algorithm for ultrasound elastography. Comput Ind 69:61–71CrossRef
19.
Zurück zum Zitat Mao R, Xu H, Wu W, Li J, Li Y, Lu M (2015) Overcoming the challenge of variety: big data abstraction, the next evolution of data management for aal communication systems. IEEE Commun Mag 53(1):42–47CrossRef Mao R, Xu H, Wu W, Li J, Li Y, Lu M (2015) Overcoming the challenge of variety: big data abstraction, the next evolution of data management for aal communication systems. IEEE Commun Mag 53(1):42–47CrossRef
20.
Zurück zum Zitat Mao R, Zhang P, Li X, Liu X, Lu M (2016) Pivot selection for metric-space indexing. Int J Mach Learn Cybern 7(2):311–323CrossRef Mao R, Zhang P, Li X, Liu X, Lu M (2016) Pivot selection for metric-space indexing. Int J Mach Learn Cybern 7(2):311–323CrossRef
26.
Zurück zum Zitat Sommer C (2014) Shortest-path queries in static networks. ACM Comput Surv, CSUR 46(4):45 Sommer C (2014) Shortest-path queries in static networks. ACM Comput Surv, CSUR 46(4):45
29.
Zurück zum Zitat Thomsen JR, Yiu ML, Jensen CS (2012) Effective caching of shortest paths for location-based services. In: ACM SIGMOD Thomsen JR, Yiu ML, Jensen CS (2012) Effective caching of shortest paths for location-based services. In: ACM SIGMOD
31.
Zurück zum Zitat U LH, Zhao HJ, Yiu ML, Li Y, Gong Z (2014) Towards online shortest path computation. IEEE TKDE 26(4):1012–1025 U LH, Zhao HJ, Yiu ML, Li Y, Gong Z (2014) Towards online shortest path computation. IEEE TKDE 26(4):1012–1025
32.
Zurück zum Zitat Wang J, Huang JZ, Guo J, Lan Y (2015) Recommending high-utility search engine queries via a query-recommending model. Neurocomputing 167:195–208CrossRef Wang J, Huang JZ, Guo J, Lan Y (2015) Recommending high-utility search engine queries via a query-recommending model. Neurocomputing 167:195–208CrossRef
33.
Zurück zum Zitat Wu L, Xiao X, Deng D, Cong G, Zhu AD, Zhou S (2012) Shortest path and distance queries on road networks: an experimental evaluation. In: VLDB Wu L, Xiao X, Deng D, Cong G, Zhu AD, Zhou S (2012) Shortest path and distance queries on road networks: an experimental evaluation. In: VLDB
35.
Zurück zum Zitat Zhang D, Chow CY, Li Q, Liu A (2016) Efficient evaluation of shortest travel-time path queries in road networks by optimizing waypoints in route requests through spatial mashups. In: APWEb Zhang D, Chow CY, Li Q, Liu A (2016) Efficient evaluation of shortest travel-time path queries in road networks by optimizing waypoints in route requests through spatial mashups. In: APWEb
36.
Zurück zum Zitat Zhang D, Chow CY, Li Q, Zhang X, Xu Y (2011) Efficient evaluation of k-NN queries using spatial mashups. In: SSTD Zhang D, Chow CY, Li Q, Zhang X, Xu Y (2011) Efficient evaluation of k-NN queries using spatial mashups. In: SSTD
37.
Zurück zum Zitat Zhang D, Chow CY, Li Q, Zhang X, Xu Y (2013) SMAshq: Spatial mashup framework for k-NN queries in time-dependent road networks. Distributed and Parallel Databases, DAPD 31(2):259–287CrossRef Zhang D, Chow CY, Li Q, Zhang X, Xu Y (2013) SMAshq: Spatial mashup framework for k-NN queries in time-dependent road networks. Distributed and Parallel Databases, DAPD 31(2):259–287CrossRef
38.
Zurück zum Zitat Zhang D, Chow CY, Li Q, Zhang X, Xu Y (2016) A spatial mashup service for efficient evaluation of concurrent k-nn queries. IEEE Trans Comput 65(8):2428–2442CrossRef Zhang D, Chow CY, Li Q, Zhang X, Xu Y (2016) A spatial mashup service for efficient evaluation of concurrent k-nn queries. IEEE Trans Comput 65(8):2428–2442CrossRef
39.
Zurück zum Zitat Zhu AD, Ma H, Xiao X, Luo S, Tang Y, Zhou S (2013) Shortest path and distance queries on road networks: towards bridging theory and practice. In: ACM SIGMOD Zhu AD, Ma H, Xiao X, Luo S, Tang Y, Zhou S (2013) Shortest path and distance queries on road networks: towards bridging theory and practice. In: ACM SIGMOD
40.
Zurück zum Zitat Zhu CJ, Lam KY, Cheng RC, Poon CK (2015) On using broadcast index for efficient execution of shortest path continuous queries. Inf Syst 49:142–162CrossRef Zhu CJ, Lam KY, Cheng RC, Poon CK (2015) On using broadcast index for efficient execution of shortest path continuous queries. Inf Syst 49:142–162CrossRef
41.
Zurück zum Zitat Zhu Z, Xiao J, Li J, Wang F, Zhang Q (2015) Global path planning of wheeled robots using multi-objective memetic algorithms. Integrated Computer-Aided Engineering 22(4):387–404CrossRef Zhu Z, Xiao J, Li J, Wang F, Zhang Q (2015) Global path planning of wheeled robots using multi-objective memetic algorithms. Integrated Computer-Aided Engineering 22(4):387–404CrossRef
Metadaten
Titel
Efficient evaluation of shortest travel-time path queries through spatial mashups
verfasst von
Detian Zhang
Chi-Yin Chow
An Liu
Xiangliang Zhang
Qingzhu Ding
Qing Li
Publikationsdatum
07.01.2017
Verlag
Springer US
Erschienen in
GeoInformatica / Ausgabe 1/2018
Print ISSN: 1384-6175
Elektronische ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-016-0288-4

Weitere Artikel der Ausgabe 1/2018

GeoInformatica 1/2018 Zur Ausgabe