UV-diagram: A Voronoi diagram for uncertain data

Reynold Cheng, Xike Xie, Man Lung Yiu, Jinchuan Chen, Liwen Sun

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

37 Citations (Scopus)


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.
Original languageEnglish
Title of host publication26th IEEE International Conference on Data Engineering, ICDE 2010 - Conference Proceedings
Number of pages12
Publication statusPublished - 1 Jun 2010
Event26th IEEE International Conference on Data Engineering, ICDE 2010 - Long Beach, CA, United States
Duration: 1 Mar 20106 Mar 2010


Conference26th IEEE International Conference on Data Engineering, ICDE 2010
Country/TerritoryUnited States
CityLong Beach, CA

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'UV-diagram: A Voronoi diagram for uncertain data'. Together they form a unique fingerprint.

Cite this