Multi-Criteria Optimal Location Query with Overlapping Voronoi Diagrams

Ji Zhang, Wei-Shinn Ku, Min-Te Sun, Xiao Qin, Hua Lu

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review


This paper presents a novel optimal location selection problem, which can be applied to a wide range of applications. After providing a formal definition of the novel query type, we explore an intuitive approach that sequentially scans all
possible object combinations in the search space. Then, we propose an Overlapping Voronoi Diagram (OVD) model that defines OVDs and Minimum OVDs, and construct an algebraic structure under an OVD overlap operation. Based
on the OVD model, we design an advanced approach to answer the query. 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). We also propose a cost-bound iterative approach that efficiently processes a large number of Fermat-Weber problems. Our experimental results show that the proposed algorithms can evaluate the novel query type effectively and efficiently
TitelAdvances in Database Technology - EDBT 2014 : 17th International Conference on Extending Database Technology, Athens, Greece, March 24-28, 2014 Proceedings
RedaktørerSihem Amer-Yahia, Vassilis Christophides, Anastasios Kementsietsidis, Minos N. Garofalakis, Stratos Idreos, Vincent Leroy
Antal sider12
ISBN (Elektronisk)978-3-89318065-3
StatusUdgivet - 2014
Udgivet eksterntJa
Begivenhed17th International Conference on Extending Database Technology - Athen, Grækenland
Varighed: 24 mar. 201428 mar. 2014
Konferencens nummer: 17


Konference17th International Conference on Extending Database Technology

Citer dette