期刊
ACM TRANSACTIONS ON DATABASE SYSTEMS
卷 32, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1272743.1272745
关键词
algorithms; experimentation; uncertain databases; range search
In an uncertain database, every object o is associated with a probability density function, which describes the likelihood that o appears at each position in a multidimensional workspace. This article studies two types of range retrieval fundamental to many analytical tasks. Specifically, a nonfuzzy query returns all the objects that appear in a search region r(q) with at least a certain probability t(q). On the other hand, given an uncertain object q, fuzzy search retrieves the set of objects that are within distance epsilon(q) from q with no less than probability tq. The core of our methodology is a novel concept of probabilistically constrained rectangle, which permits effective pruning/validation of nonqualifying/qualifying data. We develop a new index structure called the U-tree for minimizing the query overhead. Our algorithmic findings are accompanied with a thorough theoretical analysis, which reveals valuable insight into the problem characteristics, and mathematically confirms the efficiency of our solutions. We verify the effectiveness of the proposed techniques with extensive experiments.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据