Indexing multi-dimensional uncertain data with arbitrary probability density functions

TLDR

An uncertain database associates each object with a multi‑dimensional probability density function that indicates the likelihood of the object appearing at each point in space, and a probabilistic range search retrieves objects that lie within a specified rectangle with probability at least a given threshold. This paper proposes the U‑tree, an access method designed to reduce both I/O and CPU time for range retrieval on multi‑dimensional imprecise data. The U‑tree is fully dynamic, imposes no constraints on the data PDFs, and its query and update efficiency were validated through extensive experiments.

Abstract

In an uncertain database, an object o is associated with a multi-dimensional probability density function(pdf), which describes the likelihood that o appears at each position in the data space. A fundamental operation is the probabilistic range search which, given a value pq and a rectangular area rq, retrieves the objects that appear in rq with probabilities at least pq. In this paper, we propose the U-tree, an access method designed to optimize both the I/O and CPU time of range retrieval on multi-dimensional imprecise data. The new structure is fully dynamic (i.e., objects can be incrementally inserted/deleted in any order), and does not place any constraints on the data pdfs. We verify the query and update efficiency of U-trees with extensive experiments.