Since data uncertainty is inherent in multi-criteria decision making, recent years have witnessed a dramatically increasing amount of attention devoted to conducting advanced analysis on uncertain data. In this paper, we revisit restricted skyline query on uncertain datasets from both complexity and algorithm perspective. Instead of conducting probabilistic restricted skyline analysis under threshold or top-$k$ semantics, we focus on a more general problem that aims to compute the restricted skyline probability of all objects. We prove that the problem can not be solved in truly subquadratic-time unless the Orthogonal Vectors conjecture fails, and propose two algorithms, one with near-optimal time complexity and the other with better expected time complexity. We also propose an algorithm with sublinear query time and polynomial preprocessing time for the case where the preference region is described by $d - 1$ ratio bound constraints. Our thorough experiments over real and synthetic datasets demonstrate the effectiveness of the problem and the efficiency of the proposed algorithms.

翻译：由于数据不确定性是多标准决策所固有的,近年来,人们越来越关注对不确定数据进行高级分析。在本文件中,我们从复杂和算法的角度重新审视关于不确定数据集的有限天空线查询。我们没有在门槛值或最高-美元语义学下进行概率性有限天空线分析,而是侧重于一个旨在计算所有物体的有限天空线概率的更普遍的问题。我们证明,除非Orthogonal矢量计数失败,否则这个问题不可能在真正的亚水层时间得到解决,我们提出了两种算法,一种算法接近最佳时间复杂,另一种算法预期时间复杂度更高。我们还提议了一个带有亚线性查询时间和多线性预处理时间的算法,用于偏好区域用$-1美元比例约束进行描述的情况。我们对真实和合成数据集的彻底实验证明了问题的有效性和拟议算法的效率。</s>