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

29
Last Week
0
Last month
Citations as of Aug 17, 2018

WEB OF SCIENCETM
Citations

13
Last Week
0
Last month
1
Citations as of Aug 18, 2018

Page view(s)

54
Last Week
0
Last month
Citations as of Aug 20, 2018

Google ScholarTM

Check

Altmetric


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