Noname manuscript No. (will be inserted by the editor) UV-Diagram: A Voronoi Diagram for Uncertain Spatial Databases

the date of receipt and acceptance should be inserted later Abstract The Voronoi diagram is an important tech-nique for answering nearest-neighbor queries for spa-tial databases. We study how the Voronoi diagram can be used for uncertain spatial data, which are inheren-t in scientific and business applications. Specifically, we propose the Uncertain-Voronoi Diagram (or UV-diagram), which divides the data space into disjoin-t “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 non-zero probabilities. The UV-diagram enables queries that re-turn objects with non-zero chances of being the nearest neighbor (NN) of a given point q. It supports “continu-ous nearest neighbor search”, which refreshes the set of NN objects of q, as the position of q changes. It also al-lows the analysis of nearest neighbor information, e.g., 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 devis