Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
HIMM: An HMM-Based Interactive Map-Matching System Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

MinSum Based Optimal Location Query in Road Networks

verfasst von : Lv Xu, Ganglin Mai, Zitong Chen, Yubao Liu, Genan Dai

Erschienen in: Database Systems for Advanced Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Consider a road network G on which a set C of clients and a set S of servers are located. Optimal location query (OLQ) in road networks is to find a location such that when a new server is set up at this location, a certain objective function computed based on the clients and the servers serving the clients is optimized. In this paper, we study the OLQ with the MinSum objective function in road networks, namely the MinSum query. This problem has been studied before, but the state-of-the-art is still not efficient enough. We propose an efficient algorithm based on the two-level pruning technique. We also study the extension of the MinSum query problem, namely the optimal multiple-location MinSum query. Since this extension is shown to be NP-hard, we propose a greedy algorithm. Moreover, we give an approximate guarantee for our solution. Extensive experiments on the real road networks were conducted to show the efficiency of our proposed algorithms.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Efficient Landmark-Based Candidate Generation for kNN Queries on Road Networks
Nächstes Kapitel Efficiently Mining High Utility Co-location Patterns from Spatial Data Sets with Instance-Specific Utilities
Literatur
1.
Cabello, S., Diaz-Banez, J.M., Langerman, S., Seara, C., Ventura, I.: Reverse facility location problems. In: CCCG (2005)
2.
Cardinal, J., Langerman, S.: Min-max-min geometric facility location problems. In: EWCG (2006)
3.
Chen, Z., Liu, Y., Wong, R.C.W., Xiong, J., Mai, G., Long, C.: Efficient algorithms for optimal location queries in road networks. In: SIGMOD (2014)
4.
Chen, Z., Liu, Y., Wong, R.C.W., Xiong, J., Mai, G., Long, C.: Optimal location queries in road networks. ACM Trans. Database Syst. 40(3), 17 (2015)MathSciNetCrossRef
5.
6.
Du, Y., Zhang, D., Xia, T.: The optimal-location query. In: Bauzer Medeiros, C., Egenhofer, M.J., Bertino, E. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 163–180. Springer, Heidelberg (2005). doi:10.​1007/​11535331_​10 CrossRef
7.
Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: SIGMOD (2000)
8.
Gamper, J., Böhlen, M., Innerebner, M.: Scalable computation of isochrones with network expiration. In: Ailamaki, A., Bowers, S. (eds.) SSDBM 2012. LNCS, vol. 7338, pp. 526–543. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-31235-9_​35 CrossRef
9.
Ghaemi, P., Shahabi, K., Wilson, J.P., Kashani, F.B.: A comparative study of two approaches for supporting optimal network location queries. GeoInformatica 18(2), 229–251 (2014)CrossRef
10.
11.
Liu, R., Fu, A.W.C., Chen, Z., Huang, S., Liu, Y.: Finding multiple new optimal locations in a road network. In: SIGSPATIAL (2016)
12.
Liu, Y., Wong, R.C.W., Wang, K., Li, Z., Chen, C., Chen, Z.: A new approach for maximizing bichromatic reverse nearest neighbor search. Knowl. Inf. Syst. 36(1), 23–58 (2013)CrossRef
13.
Long, C., Wong, R.C.W., Yu, P.S., Jiang, M.: On optimal worst-case matching. In: SIGMOD (2013)
14.
Qi, J., Zhang, R., Kulik, L., Lin, D., Xue, Y.: The min-dist location selection query. In: ICDE (2012)
15.
Qi, J., Zhang, R., Wang, Y., Xue, A.Y., Yu, G., Kulik, L.: The min-dist location selection and facility replacement queries. World Wide Web 17(6), 1261–1293 (2014)CrossRef
16.
Tansel, B.C., Francis, R.L., Lowe, T.J.: Location on networks: a survey. Manage. Sci. 29(4), 498–511 (1983)CrossRefMATH
17.
Tong, Y., She, J., Ding, B., Chen, L., Wo, T., Xu, K.: Online minimum matching in real-time spatial data: experiments and analysis. PVLDB 9(12), 1053–1064 (2016)
18.
U, L.H., Yiu, M.L., Mouratidis, K., Mamoulis, N.: Capacity constrained assignment in spatial databases. In: SIGMOD (2008)
19.
Vlachou, A., Doulkeridis, C., Kotidis, Y., Norvag, K.: Monochromatic and bichromatic reverse top-k queries. IEEE Trans. Knowl. Data Eng. 23(8), 1215–1229 (2011)CrossRef
20.
Wong, R.C.W., Ozsu, M.T., Fu, A.W.C., Yu, P.S., Liu, L.: Efficient method for maximizing bichromatic reverse nearest neighbor. PVLDB 2(1), 1126–1137 (2009)
21.
Wong, R.C.W., Ozsu, M.T., Fu, A.W.C., Yu, P.S., Liu, L., Liu, Y.: Maximizing bichromatic reverse nearest neighbor for lp-norm in two- and three-dimensional spaces. VLDB J. 20, 893–919 (2011)CrossRef
22.
Wong, R.C.W., Tao, Y., Fu, A.W.C., Xiao, X.: On efficient spatial matching. In: VLDB (2007)
23.
Xiao, X., Yao, B., Li, F.: Optimal location queries in road network databases. In: ICDE (2011)
24.
Xu, Z., Jacobsen, H.A.: Processing proximity relations in road networks. In: SIGMOD (2010)
25.
Yan, D., Wong, R.C.W., Ng, W.: Efficient methods for finding influential locations with adaptive grids. In: CIKM (2011)
26.
Yao, B., Xiao, X., Li, F., Wu, Y.: Dynamic monitoring of optimal locations in road network databases. VLDB J. 23(5), 697–720 (2014)CrossRef
27.
Zhang, D., Du, Y., Xia, T., Tao, Y.: Progressive computation of the min-dist optimal-location query. In: VLDB (2006)
28.
Zhou, Z., Wu, W., Li, X., Lee, M.L., Hsu, W.: MaxFirst for MaxBRkNN. In: ICDE (2011)
Metadaten
Titel
MinSum Based Optimal Location Query in Road Networks
verfasst von
Lv Xu
Ganglin Mai
Zitong Chen
Yubao Liu
Genan Dai
Copyright-Jahr
2017
Buch
Database Systems for Advanced Applications

Print ISBN: 978-3-319-55698-7

Electronic ISBN: 978-3-319-55699-4

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-55699-4_27