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
GeoInformatica
Erschienen in: GeoInformatica 1/2019

09.01.2019

An overlapping Voronoi diagram-based system for multi-criteria optimal location queries

verfasst von: Ji Zhang, Po-Wei Harn, Wei-Shinn Ku, Min-Te Sun, Xiao Qin, Hua Lu, Xunfei Jiang

Erschienen in: GeoInformatica | Ausgabe 1/2019

Einloggen

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

search-config
loading …

Abstract

This paper presents a novel Multi-criteria Optimal Location Query (MOLQ), which can be applied to a wide range of applications. After providing a formal definition of the novel query type, we propose an Overlapping Voronoi Diagram (OVD) model that defines OVDs and Minimum OVDs (MOVDs), and an OVD overlap operation. Based on the OVD model, we design advanced approaches to answer the query in Euclidean space. Due to the high complexity of Voronoi diagram overlap computation, we improve the overlap operation by replacing the real boundaries of Voronoi diagrams with their Minimum Bounding Rectangles (MBR). Moreover, if there are changes to a limited number of objects, re-evaluating queries over updated object sets would be expensive. Thus, we also propose an MOVD updating model and an advanced algorithm to incrementally update MOVDs to avoid the high cost of query re-evaluation. Our experimental results show that the proposed algorithms can evaluate the novel query type effectively and efficiently.
Vorheriger Artikel Query rewriting for semantic query optimization in spatial databases

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
Literatur
1.
Aurenhammer F (1991) Voronoi diagrams–a survey of a fundamental geometric data structure. ACM Comput Surv 23(3):345–405CrossRef
2.
Aurenhammer F, Klein R, Lee D-T (2013) Voronoi diagrams and delaunay triangulations. World Scientific Publishing Co Inc
3.
Bajaj CL (1988) The algebraic degree of geometric optimization problems. Discret Comput Geom 3:177–191CrossRef
4.
Boissonnat J-D, Delage C (2005) Convex Hull and Voronoi diagram of additively weighted points. In: ESA, pp 367–378
5.
Chandrasekaran R, Tamir A (1990) Algebraic optimization: the Fermat-Weber location problem. Math Program 46:219–224CrossRef
6.
Cheema MA, Zhang W, Lin X, Zhang Y, Li X (2012) Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. VLDB J 21(1):69–95CrossRef
7.
Chen Z, Liu Y, Wong RC-W, Xiong J, Mai G, Long C (2014) Efficient algorithms for optimal location queries in road networks. In: SIGMOD conference, pp 123–134
8.
Farhana M, Choudhury J, Culpepper S, Sellis T, Cao X (2016) Maximizing bichromatic reverse spatial and textual K nearest neighbor queries. PVLDB 9(6):456–467
9.
de Berg M, Cheong O, van Kreveld M, Mark O (2008) Computational geometry: algorithms and applications, 3rd edn. Springer
10.
Demiryurek U, Shahabi C (2012) Indexing network Voronoi diagrams. In: The 17th International conference on database systems for advanced applications, DASFAA, pp 526–543
11.
Devillers O (2002) On deletion in Delaunay triangulations. Int J Comput Geom Appl 12(03):193–205CrossRef
12.
Dinis J, Mamede M (2011) Updates on Voronoi Diagrams. In: ISVD, pp 192–199
13.
Dong P (2008) Generating and updating multiplicatively weighted Voronoi diagrams for point, line and polygon features in GIS. Comput Geosci 34(4):411–421CrossRef
14.
Du Y, Zhang D, Xia T (2005) The optimal-location query. In: SSTD, pp 163–180
15.
Finke U, Hinrichs KH (1995) Overlaying simply connected planar subdivisions in linear time. In: Proceedings of the eleventh annual symposium on computational geometry. ACM, pp 119–126
16.
Fortune S (1986) A sweepline algorithm for Voronoi diagrams. In: Proceedings of the second annual symposium on computational geometry. ACM, pp 313–322
17.
Fortune S (1992) Numerical stability of algorithms for 2D delaunay triangulations. In: Proceedings of the eighth annual symposium on computational geometry, pp 83–92
18.
Gao Y, Zheng B, Chen G, Li Q (2009) Optimal-location-selection query processing in spatial databases. IEEE Trans Knowl Data Eng 21(8):1162–1177CrossRef
19.
Ghaemi P, Shahabi K, Wilson JP, Banaei-Kashani F (2012) Continuous maximal reverse nearest neighbor query on spatial networks. In: ACM SIGSPATIAL, pp 61–70
20.
Green PJ, Sibson R (1978) Computing Dirichlet tessellations in the plane. Comput J 21(2):168–173CrossRef
21.
Green PJ, Sibson R (1978) Computing Dirichlet tessellations in the plane. Comput J 21(2):168–173CrossRef
22.
Guibas L, Stolfi J (1985) Primitives for the manipulation of general subdivisions and the computation of Voronoi. ACM Trans Graph (TOG) 4(2):74–123CrossRef
23.
Guibas LJ, Knuth DE, Sharir M (1992) Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7(1):381–413CrossRef
24.
Guibas LJ, Stolfi J (1985) Primitives for the manipulation of general subdivisions and computation of Voronoi diagrams. ACM Trans Graph 4(2):74–123CrossRef
25.
Haldane JBS (1948) Note on the median of a multivariate distribution. Biometrika 35:414–415CrossRef
26.
Harn P-W, Ji Z, Sun M-T, Ku W-S (2016) A framework for updating multi-criteria optimal location query. In: ACM SIGSPATIAL
27.
Jalal G, Krarup J (2003) Geometrical solution to the fermat problem with arbitrary weights. Annals OR 123(1–4):67–104CrossRef
28.
Karavelas MI, Yvinec M (2002) Dynamic additively weighted Voronoi diagrams in 2D. In: ESA, pp 586–598
29.
Korn F, Muthukrishnan S (2000) Influence sets based on reverse nearest neighbor queries. In: SIGMOD conference, pp 201–212
30.
Korn F, Muthukrishnan S, Srivastava D (2002) Reverse nearest neighbor aggregates over data streams. In: VLDB, pp 814–825
31.
Liu R, Fu AW-C, Chen Z, Huang S, Liu Y (2016) Finding multiple new optimal locations in a road network. In: ACM SIGSPATIAL
32.
Mostafavi MA, Gold C, Dakowicz M (2003) Delete and insert operations in voronoi/delaunay methods and applications. Comput Geosci 29(4):523–530CrossRef
33.
Mu L (2004) Polygon characterization with the multiplicatively weighted Voronoi diagram. Prof Geogr 56(2):223–239
34.
Ohya T, Iri M, Murota K (1984) Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms. J Oper Res Soc Japan 27(4):306–336
35.
Okabe A, Boots B, Sugihara K, Chiu SN (2000) Spatial tessellations: concepts and applications of Voronoi diagrams. Probability and statistics, 2nd edn. Wiley, NYCCrossRef
36.
Pagliara F, Preston J, David S (2010) Residential location choice: models and applications. Springer
37.
Qi J, Zhang R, Kulik L, Lin D, Xue Y (2012) The min-dist location selection query. In: ICDE
38.
Morris JG, Love RF, Wesolowsky GO (1988) Facilities location models and methods
39.
Stanoi I, Riedewald M, Agrawal D, El Abbadi A (2001) Discovery of influence sets in frequently updated databases. In: VLDB, pp 99–108
40.
Sugihara K, Iri M (1992) Construction of the Voronoi diagram for’one million’generators in single-precision arithmetic. Proc IEEE 80(9):1471–1484CrossRef
41.
Tao Y, Papadias D, Lian X (2004) Reverse kNN search in arbitrary dimensionality. In: VLDB, pp 744–755
42.
Tao Y, Papadias D, Lian X, Xiao X (2007) Multidimensional reverse k NN search. VLDB J 16(3):293–316CrossRef
43.
Tao Y, Yiu ML, Mamoulis N (2006) Reverse nearest neighbor search in metric spaces. IEEE Trans Knowl Data Eng 18(9):1239–1252CrossRef
44.
Üster H, Love RF (2002) A generalization of the rectangular bounding method for continuous location models. Comput Math Appl 44(1–2):181–191CrossRef
45.
Vardi Y, Zhang C-H (2001) A modified Weiszfeld algorithm for the Fermat-Weber location problem. Math Program 90:559–566CrossRef
46.
Verkhovsky BS, Polyakov YS (2003) Feedback algorithm for the single-facility minisum problem. Ann Europ Acad Sci 1:127–136
47.
Weisbrod G, Ben-Akiva M, Lerman S (1980) Tradeoffs in residential location decisions: transportation versus other factors. Transp Polic Decis-Making, 1(1)
48.
Weiszfeld E, Plastria F (2009) On the point for which the sum of the distances to n given points is minimum. Annals OR 167(1):7–41CrossRef
49.
Xia T, Zhang D, Kanoulas E, Du Y (2005) On computing top-t most influential spatial sites. In: VLDB, pp 946–957
50.
Xiao X, Yao B, Li F (2011) Optimal location queries in road network databases. In: ICDE, pp 804–815
51.
Yang C, Lin K-I (2001) An index structure for efficient reverse nearest neighbor queries. In: ICDE, pp 485–492
52.
Yao B, Xiao X, Li F, Wu Y (2014) Dynamic monitoring of optimal locations in road network databases. In: VLDB, pp 697–720
53.
Yiu ML, Papadias D, Mamoulis N, Tao Y (2006) Reverse nearest neighbors in large graphs. IEEE Trans Knowl Data Eng 18(4):540–553CrossRef
54.
Zhang D, Du Y, Xia T, Tao Y (2006) Progressive computation of the min-dist optimal-location query. In: VLDB, pp 643–654
55.
Ji Z, Ku W-S, Jiang X, Qin X, Sun M-T, Lu H (2015) A framework for multi-criteria optimal location selection. In: ACM SIGSPATIAL
56.
Ji Z, Ku W-S, Sun M-T, Qin X, Lu H (2014) Multi-criteria optimal location query with overlapping Voronoi diagrams. In: EDBT, pp 391–402
Metadaten
Titel
An overlapping Voronoi diagram-based system for multi-criteria optimal location queries
verfasst von
Ji Zhang
Po-Wei Harn
Wei-Shinn Ku
Min-Te Sun
Xiao Qin
Hua Lu
Xunfei Jiang
Publikationsdatum
09.01.2019
Verlag
Springer US
Erschienen in
GeoInformatica / Ausgabe 1/2019
Print ISSN: 1384-6175
Elektronische ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-018-00338-7