An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TidsskriftGeoinformatica
Vol/bind23
Udgave nummer1
Sider (fra-til)105-161
Antal sider57
ISSN1384-6175
DOI
StatusUdgivet - 2019

Fingerprint

diagram
costs
evaluation
Costs
cost

Citer dette

Zhang, Ji ; Harn, Po-Wei ; Ku, Wei-Shinn ; Sun, Min-Te ; Qin, Xiao ; Lu, Hua ; Jiang, XunFei. / An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries. I: Geoinformatica. 2019 ; Bind 23, Nr. 1. s. 105-161.
@article{e7b26f242b354ef8b85a66efe20c9bfe,
title = "An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries",
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.",
keywords = "Optimal location query, Voronoi diagram",
author = "Ji Zhang and Po-Wei Harn and Wei-Shinn Ku and Min-Te Sun and Xiao Qin and Hua Lu and XunFei Jiang",
year = "2019",
doi = "10.1007/s10707-018-00338-7",
language = "English",
volume = "23",
pages = "105--161",
journal = "Geoinformatica",
issn = "1384-6175",
publisher = "Springer",
number = "1",

}

An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries. / Zhang, Ji; Harn, Po-Wei; Ku, Wei-Shinn; Sun, Min-Te; Qin, Xiao; Lu, Hua; Jiang, XunFei.

I: Geoinformatica, Bind 23, Nr. 1, 2019, s. 105-161.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries

AU - Zhang, Ji

AU - Harn, Po-Wei

AU - Ku, Wei-Shinn

AU - Sun, Min-Te

AU - Qin, Xiao

AU - Lu, Hua

AU - Jiang, XunFei

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Optimal location query

KW - Voronoi diagram

U2 - 10.1007/s10707-018-00338-7

DO - 10.1007/s10707-018-00338-7

M3 - Journal article

VL - 23

SP - 105

EP - 161

JO - Geoinformatica

JF - Geoinformatica

SN - 1384-6175

IS - 1

ER -