Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/12231
Title: UV-diagram : a voronoi diagram for uncertain spatial databases
Authors: Xie, X
Cheng, R
Yiu, ML 
Sun, L
Chen, J
Keywords: Nearest-neighbor query
Uncertain data
Voronoi diagram
Issue Date: 2013
Publisher: Springer
Source: VLDB journal, 2013, v. 22, no. 3, p. 319-344 How to cite?
Journal: VLDB Journal 
Abstract: The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. We study how the Voronoi diagram can be used for uncertain spatial data, which are inherent in scientific and business applications. Specifically, we propose the Uncertain-Voronoi diagram (or UV-diagram), which divides the data space into disjoint "UV-partitions". Each UV-partition P is associated with a set S of objects, such that any point q located in P has the set S as its nearest neighbor with nonzero probabilities. The UV-diagram enables queries that return objects with nonzero chances of being the nearest neighbor (NN) of a given point q. It supports "continuous nearest-neighbor search", which refreshes the set of NN objects of q, as the position of q changes. It also allows the analysis of nearest-neighbor information, for example, to find out the number of objects that are the nearest neighbors of any point in a given area. A UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation of a UV-diagram, by using a set of UV-cells. A UV-cell of an object o is the extent e for which o can be the nearest neighbor of any point q ∈ e. We study how to speed up the derivation of UV-cells by considering its nearby objects. We also use the UV-cells to design the UV-index, which supports different queries, and can be constructed in polynomial time. We have performed extensive experiments on both real and synthetic data to validate the efficiency of our approaches.
URI: http://hdl.handle.net/10397/12231
ISSN: 1066-8888
DOI: 10.1007/s00778-012-0290-x
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

9
Last Week
0
Last month
1
Citations as of Sep 20, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Sep 21, 2017

Page view(s)

48
Last Week
1
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.