Adaptive Processing for Distributed Skyline Queries over Uncertain Data
Adaptive Processing for Distributed Skyline Queries over Uncertain Data
复制标题
DOI：
10.1109/tkde.2015.2475764
复制
发表时间：
2016-02
影响因子：
8.9
通讯作者：
Xu Zhou;Kenli Li;Yantao Zhou;Keqin Li
中科院分区：
文献类型：
--
作者：
Xu Zhou;Kenli Li;Yantao Zhou;Keqin Li
不确定数据的查询处理越来越受到人们的关注，因为在许多实际应用中需要处理不确定数据。本文研究了分布式环境中不确定数据的天际线查询（DSUD查询），这类查询的研究还处于早期阶段。最先进的算法，称为e-DSUD算法，被设计用于处理此查询。它具有进步性和最小带宽消耗的理想特性。但是，还需要在三个方面加以完善。(1)先进性。每次它最多只返回一个查询结果。(2)效率。有大量的冗余I/O成本和大量的迭代，导致总查询时间很长。(3)普遍性。它仅限于本地天际线元组不可比较的情况。为了解决这些问题，我们首先详细分析了e-DSUD算法，然后开发了一个改进的DSUD查询框架，即IDSUD。在此基础上，我们提出了一种用于DSUD查询的自适应算法ADSUD。在算法中，我们重新定义近似的全局天际线概率，并根据最小概率边界矩形自适应地选择具有局部代表性的元组。在此基础上，设计了一种渐进式剪枝方法，并通过重用机制提高剪枝效率。大量的实验结果验证了我们的算法比e-DSUD算法有更好的综合性能。
Query processing over uncertain data has gained growing attention, because it is necessary to deal with uncertain data in many real-life applications. In this paper, we investigate skyline queries over uncertain data in distributed environments (DSUD query) whose research is only in an early stage. The state-of-the-art algorithm, called e-DSUD algorithm, is designed for processing this query. It has the desirable characteristics of progressiveness and minimum bandwidth consumption. However, it still needs to be perfected in three aspects. (1) Progressiveness. Each time it only returns one query result at most. (2) Efficiency. There are a significant amount of redundant I/O cost and numerous iterations which causes a long total query time. (3) Universality. It is restricted to the case where local skyline tuples are incomparability. To address these concerns, we first present a detailed analysis of the e-DSUD algorithm and then develop an improved framework for the DSUD query, namely IDSUD. Based on the new framework, we propose an adaptive algorithm, called ADSUD, for the DSUD query. In the algorithm, we redefine the approximate global skyline probability and choose local representative tuples due to minimum probabilistic bounding rectangle adaptively. Furthermore, we design a progressive pruning method and apply the reuse mechanism to improve its efficiency. The results of extensive experiments verify the better overall performance of our algorithm than the e-DSUD algorithm.