Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/14815
Title: UV-diagram : a Voronoi diagram for uncertain data
Authors: Cheng, R
Xie, X
Yiu, ML 
Chen, J
Sun, L
Keywords: Computational complexity
Computational geometry
Learning (artificial intelligence)
Probability
Visual databases
Issue Date: 2010
Publisher: IEEE
Source: 2010 IEEE 26th International Conference on Data Engineering (ICDE), 1-6 March 2010, Long Beach, CA, p. 796-807 How to cite?
Abstract: The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. In this paper, we study how the Voronoi diagram can be used on uncertain data, which are inherent in scientific and business applications. In particular, we propose the Uncertain-Voronoi Diagram (or UV-diagram in short). Conceptually, the data space is divided into distinct "UV-partitions", where each UV-partition P is associated with a set S of objects; any point q located in P has the set S as its nearest neighbor with non-zero probabilities. The UV-diagram facilitates queries that inquire objects for having non-zero chances of being the nearest neighbor of a given query point. It also allows analysis of nearest neighbor information, e.g., finding out how many objects are the nearest neighbors in a given area. However, a UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation for UV-partitions, and develop an adaptive index for the UV-diagram. This index can be constructed in polynomial time. We examine how it can be extended to support other related queries. We also perform extensive experiments to validate the effectiveness of our approach.
URI: http://hdl.handle.net/10397/14815
ISBN: 978-1-4244-5445-7
978-1-4244-5444-0 (E-ISBN)
DOI: 10.1109/ICDE.2010.5447917
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

24
Last Week
0
Last month
Citations as of Dec 11, 2017

WEB OF SCIENCETM
Citations

12
Last Week
0
Last month
1
Citations as of Dec 13, 2017

Page view(s)

50
Last Week
5
Last month
Checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric



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