, 王俊凯 1 , 吴勇 2 , 王敬昌 2 1. 浙江大学 计算机科学与技术学院, 杭州 310027;
2. 浙江鸿程计算机系统有限公司, 杭州 310009
收稿日期：2017-10-09
基金项目：中国工程科技知识中心资助项目（CKCEST-2014-1-5）；国家自然科学基金资助项目（61332017）；浙江省科技计划项目（2015C33002）
作者简介：陈东辉(1995-), 男, 博士研究生
通信作者：陈岭, 副教授, E-mail:lingchen@zju.edu.cn
摘要：随着大数据时代的到来，不确定性数据上的聚合查询面临形式多样、计算复杂等挑战。该文将不确定性数据上聚合查询的结果定义为所有可能的值以及对应的概率。基于动态规划思想的求解"和"的分布（distribution sum，DSUM）精确算法，提出贪心的"和"的分布（greedy distribution sum，GDSUM）和折半合并的"和"的分布（binary merge distribution sum，BMDSUM）的近似算法，这2种算法都能应用于元组级不确定性模型和属性级不确定性模型；并通过理论分析，给出算法的时间和空间复杂度以及最终结果的误差范围。实验结果表明：误差设定为1%时，2种近似算法分别能缩短执行时间15%~21%和22%~32%。
关键词：聚合查询近似算法不确定性数据动态规划误差估计
Approximation algorithms for aggregate queries on uncertain data
CHEN Donghui1, CHEN Ling1
, WANG Junkai1, WU Yong2, WANG Jingchang21.College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China;
2.Zhejiang Hongcheng Computer Systems Co., Ltd., Hangzhou 310009, China
Abstract: Analyses of big data sets often require aggregate queries on uncertain data with various types of data that are computationally complex. In this paper, the results of aggregate queries on uncertain data are defined to include all possible values and their corresponding probabilities. Dynamic programming is then used to solve the Distribution Sum (DSUM) algorithm using a Greedy-based Distribution Sum and a Binary Merge based Distribution Sum approximation algorithms, which both can be applied to tuple-level and attribute-level uncertainty models. The time and space complexities of the algorithms are determined theoretically as well as the error range of the results. Tests demonstrates that these two approximation algorithms with a 1% allowable error shorten the execution times by 15%-21% and 22%-32%, respectively.
Key words: aggregate queriesapproximation algorithmsuncertain datadynamic programmingerror estimation
近年来，随着大量新型应用的发展，不确定性数据的管理越来越重要，主要体现在以下几个方面：1)普遍存在于现实世界，如无线传感器网络、射频识别网络、移动物体检测等; 2)数据的不确定性是固有的，这些不确定性数据通常存在不一致的模式; 3)可以广泛应用在不同领域，如模式匹配、数据挖掘等; 4)利用概率模型处理，能提供概率保证。
许多工作研究不确定性数据的建模[1-3]。为了表示不确定性数据的可信程度，通常在不确定性数据后添加概率值P，表示该数据存在的概率为P，不存在的概率为(1-P)。基于该模型，诞生了大量的概率数据库管理系统[4-5]，相比于传统的关系型数据库，由于概率维度的特殊性，概率数据的存储和索引、查询的定义、处理过程和结果呈现等都将发生变化，因此对概率数据的管理更加复杂和多样化。
近年来，有大量与不确定性数据查询处理相关的研究[6]，包括天际线查询[7]、Top-k查询[8]、范围查询[9]、最近邻查询[10]等。还有大量研究是基于不确定性数据的聚合查询的处理。早期的研究[11]中，只能返回聚合查询结果的期望值，Murthy等[12]提出了基于可能世界的解决方法，但只是定义了3种查询：最低可能的值、最高可能的值和期望值。
Dalvi等[13]证明了不同的可能世界中“和”和“平均值”的大小是不同的，通过枚举方式计算是#P-完全问题。针对不确定数据上的聚合查询的近似算法[14]问题，Nath等[15]提出了基于素描的方法，Zeng等[16]提出了基于采样的方法。这些研究中的近似算法都是通过减少原始数据的数量来降低时间复杂度。
针对以上问题，本文基于可能世界语义，即聚合查询的结果是一系列可能的值和对应的概率，给出基于动态规划的精确求解算法，考虑到其时间复杂度仍然较大，对精确算法进行改进，分别提出了贪心策略和折半合并策略的近似算法，并证明了2种近似算法的时间复杂度和结果的误差范围。
1 问题定义1.1 不确定性模型目前比较公认的将不确定性模型分为2类[6]：元组级不确定性和属性级不确定性。
定义1 元组级不确定性??每张不确定性数据表T有一个概率属性P，该数据表中每一条元组ti的概率属性值p(ti)代表该元组存在的概率。
定义2 属性级不确定性??每一条元组ti中有一个属性V存在β个值：vi, 1, vi, 2, …，vi, β，每一个值对应概率为pi, 1, pi, 2, …，pi, β。
表 1为元组级和属性级不确定性示例。
表 1 不确定性示例
| 元组级 | 属性级 | ||||
| ID | V | P | ID | (V, P) | |
| t1 | 1 | 0.5 | t1 | (10, 0.4) ‖ (8, 0.6) | |
| t2 | 2 | 0.4 | t2 | (3, 0.2) ‖ (2, 0.7) ‖ (5, 0.1) | |
| t3 | 1 | 0.7 | t3 | (5, 1) | |
表选项
1.2 可能世界在元组级不确定性表T中，一个可能世界w是表T中元组的子集，若T中有n条元组，则w发生的概率
| ${\rm{pw(}}{\mathit{e}_\mathit{i}}{\rm{) = }}\left\{ \begin{array}{l}\mathit{p}{\rm{(}}{\mathit{t}_\mathit{i}}{\rm{), }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mathit{t}_\mathit{i}}{\rm{存在}};\\{\rm{1 - }}\mathit{p}{\rm{(}}{\mathit{t}_\mathit{i}}{\rm{), }}\;\;\;\;\;\;\;\;\;{\mathit{t}_\mathit{i}}{\rm{不存在}}{\rm{.}}\end{array} \right.$ | (1) |
表 2为元组级不确定性表 1组成的所有可能世界集合。表 3为元组级不确定性表 2组成的所有可能世界集合。
表 2 元组级不确定性
| W | 可能世界 | Pr[w] |
| w1 | t1, t2, t3 | 0.14 |
| w2 | t1, t2 | 0.06 |
| w3 | t1, t3 | 0.21 |
| w4 | t2, t3 | 0.14 |
| w5 | t1 | 0.09 |
| w6 | t2 | 0.06 |
| w7 | t3 | 0.21 |
| w8 | ? | 0.09 |
表选项
表 3 属性级不确定性
| W | 可能世界 | Pr[w] |
| w1 | t1:10, t2:3, t3:5 | 0.08 |
| w2 | t1:10, t2:2, t3:5 | 0.28 |
| w3 | t1:10, t2:5, t3:5 | 0.04 |
| w4 | t1:8, t2:3, t3:5 | 0.12 |
| w5 | t1:8, t2:8, t3:5 | 0.42 |
| w6 | t1:8, t2:8, t3:5 | 0.06 |
表选项
定义3 不确定性数据上的聚合查询??该查询返回所有可能世界实例的值以及对应的概率。
基于表 2，计数查询结果如表 4所示。
表 4 计数查询结果示例
| 计数 | W | P |
| 0 | w8 | 0.09 |
| 1 | w5, w6, w7 | 0.36 |
| 2 | w2, w3, w4 | 0.41 |
| 3 | w1 | 0.14 |
表选项
2 基本算法为方便描述，以不确定数据上的“求和”查询为例，给出基于动态规划思想的求解算法。
2.1 元组级不确定性假设当前元组级不确定性表T包含n条元组t1, t2, …, tn，val(ti)表示元组ti聚合属性的值的大小。动态规划的思想是依次计算每条元组，计算了j条元组时的结果用listj保存，列表listj中每一个元素包含了“和”(sum)以及概率(prob)。列表中元素顺序按照“和”从小到大排列。
2.1.1 初始状态起始列表list0=?，计算第一条元组t1时，分为2种情况：t1不成立，则sum=0，prob=1-p(t1)；t1成立，则sum=val(t1)，prob=p(t1)。将2种情况加入到列表中。
2.1.2 状态转移过程考虑一般情况，当计算了j条元组得到的listj，计算第j+1条元组tj+1时，分2种情况：1) tj+1不成立，对于listj中的每一个元素的sum值不变，概率值变为pi×(1-p(tj+1))，将这些新的结果写入到templistj, 1中；2) tj+1成立，对于listj中的每一个元素的sum值变为sumi+val(tj+1)，概率值变为pi×p(tj+1)，将这些新的结果写入到templistj, 2中。最后将stemplistj, 1和templistj, 2合并得到listj+1，合并原则：如果sum值相同的元素，则概率相加，合并后加入到listj+1中；否则，将剩余元素都加入到listj+1中。过程如图 1所示。
 |
| 图 1 状态转移过程 |
| 图选项 |
假设对列表不合并，则计算每一条元组时，一个临时列表会生成两个，最终会生成2n个列表，呈指数级增长。算法中将sum值相同的元素合并为一个，降低了时间复杂度，后面会具体分析。由于空间限制，此处省略DSUM伪代码。
定理1??DSUM算法的时间复杂度为O(avg×n2)，空间复杂度为O(avg×n)。
证明??由于val(ti)的值均为小整数，所有元组的平均大小为avg，因此sum的可能取值为[0, avg×n]之间的整数，即list的长度最大为avg×n+1，n条元组中每一条需要遍历一次list，因此，时间复杂度为O(avg×n2)。在计算每一条元组时，新的list只需要根据前一次的list计算，因此，只需要一个list即可，即空间复杂度为O(avg×n)。
2.2 属性级不确定性在属性级不确定性中，本文仍然以不确定数据上的“求和”查询为例，为了方便描述，假设每条元组中不确定性属性的值的个数都为β，该算法同样是基于动态规划的思想。
假设计算了j条元组时的列表为listj, 计算第j+1条元组tj+1时，tj+1有β种情况发生，每一种情况都用一个临时列表保存结果。将得到的β个列表合并得到listj+1，合并的原则仍然是将sum值相同的元素概率相加，成为新的元素加入到列表中, 并将那些sum值不同的元素直接加入到新的列表中。由于篇幅有限，本文省略算法的伪代码。
定理2??元组级不确定性模型中，DSUM算法的时间复杂度为O(βavg×n2)，空间复杂度为O(βavg×n)。
证明??证明过程与定理1证明类似，此处省略。
3 近似算法在传感器网络等实际的应用中，数据量n往往会特别大；另外，精确算法只能处理那些聚合值为小整数的数据，对于一些特殊应用，如包含小数或一些特别大的异常值等情况时，该算法的时间复杂度会大幅增加。为了解决这些问题，本文又提出了基于贪心和折半合并的近似算法。
3.1 相关定义3.1.1 查询结果的误差不确定性数据上的聚合查询结果是一个离散型概率分布，因此，需要度量真实结果的概率分布resulttruth和通过近似算法得到的结果的概率分布resultappro之间的差异。真实结果和近似结果的累积分布函数分别为CDFttruth和CDFappro，表示如下：
| $ {\rm{CD}}{{\rm{F}}_{{\rm{truth}}}}\left( \mathit{i} \right){\rm{ = }}\sum\limits_{{\mathit{j }}{{\rm{= sum}}_{{\rm{min}}}}}^\mathit{i} {{\rm{resul}}{{\rm{t}}_{{\rm{truth}}}}\left( \mathit{j} \right) \cdot {\rm{prob}}} {\rm{, }} $ | (2) |
| $ {\rm{CD}}{{\rm{F}}_{{\rm{appro}}}}\left( \mathit{i} \right){\rm{ = }}\sum\limits_{{\mathit{j}}{{\rm{ = sum}}_{{\rm{min}}}}}^\mathit{i} {{\rm{resul}}{{\rm{t}}_{{\rm{appro}}}}\left( \mathit{j} \right) \cdot {\rm{prob}}} . $ | (3) |
| ${\rm{resul}}{{\rm{t}}_{{\rm{error}}}}{\rm{ = max( CD}}{{\rm{F}}_{{\rm{truth}}}}{\rm{(}}\mathit{i}{\rm{) - CD}}{{\rm{F}}_{{\rm{appro}}}}{\rm{(}}\mathit{i}{\rm{) )}}{\rm{.}}$ | (4) |
3.1.2 ε近似在节2.1的精确求解算法中，每次计算一条元组，都需要遍历当前的列表list。因此，如果列表的长度越小，则算法的时间复杂度就越小，而列表list都是由上一轮计算得到的2个临时列表合并得到。在合并过程中，当2个临时列表包含sum值相同的项，则合并为一项; 若sum值相同的项越多，则合并的项就越多，得到的list长度就会越小。基于该思想，考虑将sum值相近的项也进行合并，这大大增加了合并的机会，从而使list的长度变小，提高计算效率。
定义5??ε近似。给定误差大小ε，对于列表list中的任意两项(suma, proba)和(sumb, probb)，如果(|sumb-suma|×probb)＜ε，则用(suma, proba+probb)近似代替这两项。
3.2 基于贪心的近似算法基于节3.1的讨论，计算每一条元组时，对当前列表近似化。将列表中元素划分为多个桶，每个桶有一个代表值，该值为当前桶中所有元素的近似值。
首先提出基于贪心的“和”的分布近似算法(greedy distribution sum, GDSUM)，如图 2所示。算法第1—8行与DSUM算法原理相同，不再赘述。第11—16行，对于当前的有序列表list，可以顺序遍历列表，如果当前元素和当前桶的代表值之间的误差小于指定误差ε，则将当前元素和代表值进行合并，并从列表list中删除该元素；否则，该元素将进入新的一个桶，并成为该桶的代表值。
 |
| 图 2 Greedy Distribution SUM算法 |
| 图选项 |
例1??如图 3所示，假设误差ε=0.2，左边为合并前的列表，从上往下遍历，初始时，桶的代表值为sum=0的元素，对于sum=1的元素，由于(1-0)×0.14＜0.2，因此，将该元素合并；同理，sum=2的元素也需要合并；对于sum=9的元素，由于(9-0)×0.06＞0.2，因此不能合并，该元素成为新的桶的代表值。依次计算，最终得到的新的列表list为右边部分，显然比合并前的列表list短。
 |
| 图 3 近似合并过程示例 |
| 图选项 |
算法复杂度，假设当前列表的长度为l，每一个桶平均合并的元素数量为b，则桶的数量为l/b，第i个桶中包含的元素为listi, 1, listi, 2, …, listi, b。根据之前的定义，该桶中每一个元素都能和桶代表元素合并，表示如下：
| $\begin{array}{l}{\rm{(lis}}{{\rm{t}}_{\mathit{i}{\rm{, }}\mathit{j}}} \cdot {\rm{sum - lis}}{{\rm{t}}_{\mathit{i}{\rm{, 1}}}} \cdot {\rm{sum)}} \cdot \\\;\;\;\;\;\;\;\;\;\;\;{\rm{lis}}{{\rm{t}}_{\mathit{i}{\rm{, }}\mathit{j}}} \cdot {\rm{prob}} \le \mathit{\varepsilon }{\rm{, }}\end{array}$ | (5) |
| $\left( {\mathit{j - }{\rm{1}}} \right){\rm{\cdot lis}}{{\rm{t}}_{\mathit{i}{\rm{, }}\mathit{j}}} \cdot {\rm{prob}} \le \mathit{\varepsilon }{\rm{, }}$ | (6) |
| $\mathit{\varepsilon }{\rm{/}}\left( {\mathit{j - }{\rm{1}}} \right) \ge {\rm{lis}}{{\rm{t}}_{\mathit{i}{\rm{, }}\mathit{j}}}{\rm{\cdot prob}}{\rm{.}}$ | (7) |
| ${\rm{bucke}}{{\rm{t}}_{\mathit{i}{\rm{, prob}}}} \le \mathit{\varepsilon }\sum\limits_{\mathit{j} = 1}^{\mathit{b} - 1} {{\rm{1/}}\mathit{j}} {\rm{.}}$ | (8) |
| ${\rm{1}} \le \frac{\mathit{l}}{\mathit{b}}{\rm{\cdot}}\mathit{\varepsilon }\sum\limits_{\mathit{j} = 1}^{\mathit{b} - 1} {{\rm{1/}}\mathit{j}} {\rm{.}} $ | (9) |
定理3??GDSUM算法的时间复杂度下界为O(n/λε)，空间复杂度下界为O(1/λε)，时间和空间复杂的上界与定理1相同。
证明??显然该近似算法的复杂度不会超过精确算法，所以复杂度上界为精确算法的复杂度。在计算每一条元组时，近似合并后得到的列表长度下界为1/λε，而共有n条元组，因此时间复杂度下界为O(n/λε)；算法中每轮迭代可以用同一个列表list，所以空间复杂度下界为O(1/λε)。
定理4??GDSUM算法的误差最大为λε。
证明??式(9)得到每个桶的误差最大为λε，根据结果误差的定义，易得最终结果的误差最大为λε。
3.3 基于折半合并的近似算法在基于贪心的近似算法中，由于将每个桶的最小值作为代表值，因此会导致近似结果的期望小于真实结果。因此，本文又提出了基于折半合并的“和”的分布近似(binary merge distribution sum, BMDSUM)算法。在贪心策略中，会顺序遍历列表；在折半合并中，每次先访问最中间的元素，并作为当前的代表值，然后合并该元素两边的元素，直到不能合并。这样剩下的未合并的元素被划分为2部分，然后对每一部分再执行刚才的折半合并过程，依次计算，直到所有元素都被计算为止。
定理5??BMSUM算法的时间复杂度下界为O(n/2λε)，空间复杂度下界为O(1/2λε)，时间和空间复杂度的上界与定理1相同。
证明??在基于贪心的近似算法中，是顺序遍历；基于折半合并的算法中，是从两边往中间合并，在最优情况下，合并后的项数是基于贪心算法的一半，因此时间和空间复杂度的下界均为基于贪心算法的一半。证明过程与定理2的证明类似，在此不赘述。
定理6??MSUM算法的误差最大为λε。
证明??与定理4类似。
通过上述分析，基于贪心和折半合并的近似算法有以下优点：1)降低了时间复杂度；2)处理各种复杂数据(如小数、特大的数等)时，该算法的时间复杂度较低; 3)保证能够控制结果的误差。
4 实验4.1 实验设置在元组级不确定性模型和属性级不确定性模型中，分别实现了精确求解算法和2种近似算法。软硬件环境：Windows 10操作系统，Intel(R) Core(TM) i5-2400处理器(3.1 GHz主频)，4 GB内存，实现语言为Java。
真实数据集，采用IIP(International ice patrol)监测数据库，使用方法可参考文[17]；合成数据集，使用python语言合成的数据。对于元组级不确定性模型，每条元组包含聚合属性值以及该条元组的概率；对于属性级不确定性模型，每条元组的聚合属性包含多个可能值以及对应的概率，聚合属性的值的数量为[2-6]均匀分布，值的大小呈正态分布，均值为10。
4.2 实验结果4.2.1 数据集大小对执行时间的影响本实验中设定误ε为0.01，元组条数分别为1 000、2 000、3 000、4 000和5 000条。对于真实数据集，图 4a所示为元组级不确定性模型下3种算法的执行时间，GDSUM和BMDSUM算法分别能比精确算法执行时间缩短15%和23%。图 4b为对应的属性级不确定性模型，近似算法的执行时间分别能缩短15%和22%。
 |
| 图 4 数据集大小对执行时间的影响和数据量对查询结果误差的影响 |
| 图选项 |
对于合成数据集，图 4c为元组级不确定性模型，GDSUM和BMDSUM算法分别能缩短执行时间21%和32%，同样地，图 4d为对应属性级不确定性模型，则执行时间分别能缩短18%和28%。
相比于真实数据集，在2种不确定性模型下，2种近似算法对于合成数据集的性能提升更明显，因为合成数据集中聚合属性的平均值更小，中间结果的可能值的范围更小，无论是精确求解算法还是近似算法，能够合并的都更多，因此效率更高。
4.2.2 数据量对查询结果误差的影响在本实验中，设定的误差ε为1%，图 4e和4f分别对应元组级不确定性和属性级不确定性模型，从图中可以看出，最终结果的误差基本不会随着元组数量增多而增大，并且都小于5%，与定理4和6相符合。因此，2个近似算法都具有较好的扩展性。
5 结论本文对不确定性数据上聚合查询的近似算法进行了深入的研究。由于可能世界的数量随着数据的数量呈指数级增长，因此高效的聚合查询算法至关重要。本文给出了基于动态规划的精确求解算法，以及基于贪心和折半合并的近似算法，并给出了算法的时间和空间复杂度以及结果的误差范围。通过在真实数据集和合成数据集上的实验，验证了算法的有效性。
参考文献
| [1] | DESHPANDE A, GUESTRIN C, MADDEN S. Using probabilistic models for data management in acquisitional environments[C]//Proceedings of the International Conference on Innovation Database Research. Asilomar, USA: Online Proceeding, 2005: 317-328. |
| [2] | PENG L P, DIAO Y L. Supporting data uncertainty in array databases[C]//Proceedings of 2015 International Conference on Management of Data. Melbourne, Australia: ACM Press, 2015: 545-560. |
| [3] | Ré C, SUCIU D. Approximate lineage for probabilistic databases[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 797–808. DOI:10.14778/1453856 |
| [4] | SINGH S, MAYFIELD C, MITTAL S, et al. Orion 2. 0: Native support for uncertain data[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. Vancouver, Canada: ACM Press, 2008: 1239-1242. |
| [5] | HUANG J W, ANTOVA L, KOCH C, et al. MayBMS: A probabilistic database management system[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. Providence, USA: ACM Press, 2009: 1071-1074. |
| [6] | WANG Y J, LI X Y, LI X L, et al. A survey of queries over uncertain data[J]. Knowledge and Information Systems, 2013, 37(3): 485–530. DOI:10.1007/s10115-013-0638-6 |
| [7] | ZHOU X, LI K L, ZHOU Y T, et al. Adaptive processing for distributed skyline queries over uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(2): 371–384. DOI:10.1109/TKDE.2015.2475764 |
| [8] | CICERI E, FRATERNALI P, MARTINENGHI D, et al. Crowdsourcing for top-k query processing over uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(1): 41–53. DOI:10.1109/TKDE.2015.2462357 |
| [9] | CHEN L, GAO Y J, LI X H, et al. Indexing metric uncertain data for range queries[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Australia: ACM Press, 2015: 951-965. |
| [10] | DALLACHIESA M, PALPANAS T, ILYAS I F. Top-k nearest neighbor search in uncertain data series[J]. Proceedings of the VLDB Endowment, 2014, 8(1): 13–24. DOI:10.14778/2735461 |
| [11] | JAYRAM T S, KALE S, VEE E. Efficient aggregation algorithms for probabilistic data[C]//Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. New Orleans: Society for Industrial and Applied Mathematics, USA: 2007: 346-355. |
| [12] | MURTHY R, IKEDA R, WIDOM J. Making aggregation work in uncertain and probabilistic databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8): 1261–1273. DOI:10.1109/TKDE.2010.166 |
| [13] | DALVI N, SUCIU D. Management of probabilistic data: Foundations and challenges[C]//Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Beijing, China: ACM Press, 2007: 1-12. |
| [14] | AGARWAL P K, KUMAR N, SINTOS S, et al. Range-max queries on uncertain data[C]//Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. San Francisco, USA: ACM Press, 2016: 465-476. |
| [15] | NATH S, GIBBONS P B, SESHAN S, et al. Synopsis diffusion for robust aggregation in sensor networks[J]. ACM Transactions on Sensor Networks, 2008, 4(2): 250–262. |
| [16] | ZENG K, GAO S, MOZAFARI B, et al. The analytical bootstrap: A new method for fast error estimation in approximate query processing[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird, USA: ACM Press, 2014: 277-288. |
| [17] | HUA M, PEI J, ZHANG W J, et al. Ranking queries on uncertain data: A probabilistic threshold approach[C]//Proceedings of the 27th International Conference on Management of Data. Vancouver, Canada: ACM Press, 2008: 673-686. |
