Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
GeoInformatica
Published in: GeoInformatica 1/2019

09-01-2019

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

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

Published in: GeoInformatica | Issue 1/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

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.
previous article Query rewriting for semantic query optimization in spatial databases

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Footnotes
Literature
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
Metadata
Title
An overlapping Voronoi diagram-based system for multi-criteria optimal location queries
Authors
Ji Zhang
Po-Wei Harn
Wei-Shinn Ku
Min-Te Sun
Xiao Qin
Hua Lu
Xunfei Jiang
Publication date
09-01-2019
Publisher
Springer US
Published in
GeoInformatica / Issue 1/2019
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-018-00338-7