MUD: Mapping-based query processing for high-dimensional uncertain data

详细信息	查看全文 | 推荐本文 |

• 作者：Lidan Shou ; ^{should@zju.edu.cn} ; Xiaolong Zhang ^{xiaolongzhang@zju.edu.cn} ; Gang Chen ^{cg@zju.edu.cn} ; Yuan Gao ^{yuangao1@zju.edu.cn} ; Ke Chen ^{chenk@zju.edu.cn}
• 关键词：High-dimensional uncertain data ; Probabilistic threshold range query
• 刊名：Information Sciences
• 出版年：2012
• 期刊代码：62_00200255
• 类别：cp
• 出版时间：1 September, 2012
• 卷：198
• 期：Complete
• 页码：147-168
• 文件大小：1453 K

摘要

Many real-world applications require management of uncertain data that are modeled as objects in high-dimensional space with imprecise values. In such applications, data objects are typically associated with probability density functions. A fundamental operation on such uncertain data is the probabilistic-threshold range query (PTRQ), which retrieves the objects appearing in the query region with probabilities no less than a specified value. In this paper, we propose a novel framework called MUD for efficient processing of PTRQs on high-dimensional uncertain data. We first propose a cost-effective pruning technique based on a very simple form of probabilistic pruning information (PPI), namely the probabilistic quantiles. Then we map high-dimensional uncertain objects to a single-dimensional space, where the quantiles of uncertain objects can be indexed using the existing single-dimensional indices such as the B+-tree. Each PTRQ in the high-dimensional space is transformed into multiple range queries on the single-dimensional space and evaluated there. We also discuss a method to optimize the indexing scheme for MUD. Specifically, we formulate a mathematical model for measuring the 鈥減runing power鈥?of quantiles, and propose a dynamic programming algorithm which selects the 鈥渂est鈥?quantiles for mapping and indexing. We perform extensive experiments on both synthetic and real data sets. Our experimental results reveal that the MUD framework is both effective and efficient for processing PTRQs on high-dimensional uncertain data, and it can significantly outperform state-of-the-art schemes.