不确定数据Top—K查询技术研究

黄玲玲　杨剀

摘要：高效的Top-K查询处理是不确定数据管理的一项重要技术。从确定性算法技术和近似算法技术两方面研究典型的不确定数据的Top-K查询算法，分析概率与分值的平衡方式，介绍统一化排序思想以及综合多种查询特征的新型查询方式，最后提出不确定性Top-K查询的研究方向及不确定性查询处理技术的研究热点。

关键字：不确定性数据；Top-K查询；确定算法技术；近似算法技术；排序函数；概率

中图分类号 TP311 文献标志码：A

0 引言

随着传感器网络和移动对象的应用，不确定数据无处不在，如传感器数据、RFID数据、隐私数据、LBS数据、Web应用数据等等。同时人们也逐渐认识到不确定数据处理带来的巨大价值。目前，不确定数据查询技术已经成为空间和移动数据库的前沿研究领域[1]。其中面向不確定数据库的Top-K查询处理在涉及大量数据交互方面的拓展应用则是一项高效基础重要技术[2]。面向确定数据库的Top-K查询的定义非常清晰，即返回Ranking函数值最大的K个元组。但是，由于不确定数据概率维度的存在，确定数据集上的Top-K查询算法无法直接应用到不确定数据集合上[3]。基于此，本文拟从确定性算法技术和近似算法技术两方面展开典型不确定数据的Top-K查询算法研究，同时分类综述近年来不确定数据Top-K查询的研究成果，并指出下一步的的挑战与发展方向。

1 典型不确定数据Top-K定义和算法研究

针对不确定性Top-K查询，学者们从多种应用需要以及设定侧面给出了不同的查询语义。其中U-TopK[4，5]、U-kRanks[4，6]、c-typical-Topk[7]、Global-TopK[8]、PT-K[9-11]、Expected Rank[12-13]等得到了广泛认同，而且可分别适用于不同的应用场景。与此同时，不确定查询算法随即进入了深度探索的研究完善阶段。对不确定查询处理的确定性算法技术的研究焦点就是如何利用查询语义的特点避免展开整个可能世界空间[4-5，7-10，12-13]，从而提高查询效率。

1.1 确定性算法技术

Re等人[14]较早地研究了概率数据库中的Top-K查询问题，阐述了通过SQL语句查询概率数据中概率值最大的Top-K元组，其元组的概率即为排序函数值。然而，多数不确定数据上的Top-K查询通常在可能的世界模型语义下聚集查询结果来排序概率数据以获取查询结果。

Soliman等人[4]针对不确定数据上的Top-K查询问题，首次研究提出了解决查询的不确定数据模型以及U-TopK查询和U-KRanks查询的定义。

概括来说，U-TopK查询返回一个长度为K的元组矢量，而且是在所有的可能世界中的发生概率为最大；U-KRanks查询返回在各个级别中出现的总概率最大的元组。Soliman证明了按分值排序读取记录可以使U-TopK查询和U-KRanks查询读取最少记录完成查询，并设计实现了可确保最优性的查询算法。因此，这2种查询方法就是将查询问题转化为状态空间搜索问题，研究转化为实例化最少的状态。各元组首先按照ranking函数从小到大进行排序，然后不断构造搜索空间，缩小空间的范围，最终获得查询结果。

在c-typical-TopK查询中也使用了状态空间扩展方法。当所求的Top-K具有最优子结构性质时，还可以采用动态规划的方法。动态规划的目标是发现求解Top-K问题的最优子结构性质。文献[7]中求解的c-typical-TopK和文献[5]中求解的Global TopK都表现出同样性质。

动态规划算法满足最优化原理，能够将求解的问题分解成若干个子问题（阶段），且下一个子阶段的求解依赖于上一个子阶段的运行结果，最终就是一句尾端子阶段的求解来依次求得其它阶段的输出解。

在确定性算法中，除了前文提到的状态空间方法和动态规划方法外，泊松二项递推的方法也是常用方法之一。

当不确定性数据库只存在记录级不确定性且并未提供生存规则时，可以将每条记录的出现与否视作实验的2种对立结果：n次实验代表数据库的n条记录。如PT-K查询和global-TopK查询都需要求解每条记录出现在Top-K中的概率。如果将记录按分值排序，记录t出现在Top-K中的概率可以理解为如下表述事件：在排队序列中，排位在t前的那些记录同时出现小于等于k-1个记录的概率，因此可以使用泊松二项分布的递推方法[2]。

记录级不确定数据库大致满足泊松二项分布的条件，在多种Top-K处理中都体现了泊松二项递推的思想[9-11，15-17]。当探知生存规则时，只要对生存规则设计具体处理，就可以将问题转化成简单情况。

由于不确定性Top-K查询处理建立在不确定数据模型和可能世界语义的基础上，而可能世界空间随着数据量成指数增长，由此则导致许多求解问题均具有NP难度。因此，近似算法应运而生，并能以较高的精确度大幅提升求解速度。

1.2 近似算法技术

文献[10]不仅提出了概率阈值PT-K查询定义，并针对此研究开发提出了高效的精确查询算法和快速的抽样近似查询算法。

在求取PT-K时，在可能世界空间改善可能世界实例。每取样一个可能世界实例，即对出现在Top-K中的记录ID控制加1。在样本足够多的情况下，记录的累计频度接近该记录的真实Top-K概率。

因此，在用户不需要完全精确答案的前提下，为了进一步提高查询效率，很多学者都采用近似的方法来处理不确定性Top-K查询，以牺牲少量精度的方式换取更高的处理效率[5，9-10，13，15-16，18]。

在不确定性Top-K的确定算法处理技术中，关键求解概率大多具有递减性质，并依赖一些其它的限制条件，在求解一些特定不确定性Top-K时，本来需要扫描所有记录，但是根据一些已知条件会发现某位置后的记录在解集中的可能性微乎其微，因此可以利用已知结果维护一个逐渐逼近真实值的阈值，使得求解为精确度非常高的近似解集。expected Rank Top-K[12-13]和global Top-K[8，19]就采用了逼近阈值的近似求解来支持设计实现的。

例如，在expected Rank 求解中，需要求解每个记录在所有可能世界的期望位置，再求取其中最好的k个。可按分值期望顺序扫描记录，不断更新已扫描记录的期望排位上限，并重新计算尾部记录排位下限。当有k个记录的排位上限大于尾部记录排位下限时算法结束，得到的结果将具有接近理想的近似程度。

Global-TopK则是使用记录分值排序表1和记录概率排序表2两个列表，扫描表1，并计算当前扫描记录的概率，利用表2和当前扫描记录来估算所有未见记录的global Top-K上限，设定阈值进行剪枝加速算法。

可见，阈值逼近通过扫描按特定顺序排列的记录，不断更新某些特定值以逼近停止条件。虽然在算法结构上没有明显改进，但是因为在保证一定精确度的前提下限制了扫描记录的数量，极大的縮短了求解时间，有时甚至可达数量级的变动，从而优势提升了查询效率。

除了阈值逼近以外，近似求解也可通过近似取样技术和近似计算技术而获取生成。近似取样技术采用随机采样技术（即蒙特卡罗—MonteCarlo方法[20]），保证了在具有巨大实例数目的可能世界中随机选取部分实际样本且样本达到一定数目的条件下，计算的概率能够比较接近于真实结果。近似计算技术则需要合理构建不确定数据的概率分布函数来计算概率的近似值，以此来最佳提升计算的效率，如泊松分布近似计算方法。

独立样本使用基本的蒙特卡罗方法产生，分值连续时，求解各种不确定性Top-K查询时需要在联合概率密度函数上进行积分运算，使用马尔可夫链的蒙特卡罗方法[21]，保证以高概率的方式取样到有效的可能世界，提高近似程度。如MS-TopK查询的蒙特卡罗取样方法[22]、PT-K查询的蒙特卡罗积分方法[23]、U-TopK查询的动态马尔可夫取样方法[24]。

综上所述可知，确定性算法一般要比近似算法复杂程度高，而近似算法通过少量精度损失却可大幅提升查询效率。

2分值与概率的平衡研究

Li采用规范Kendall距离[15]对比同一数据集上的5种不确定性Top-K返回的结果，发现各语义返回结果差异显著，有些结果甚至完全相反。究其原因，主要有2点，分别是：记录的概率和Ranking函数分值。

通常有3种方式来处理分值和概率这两大因素：

1）先进行分值排序再求取概率，如U-TopK。但是在利用分值求得所有的Top-K序列后，再将概率作为唯一的衡量标准，将导致弊端纷显，因而应将分值重新纳入考量范畴。

2）先求取概率，再进行分值排序，如文献[5]中指出在位置概率U-iRanks的基础上根据Top-K位置上记录的位置概率总和最大来进行优化，利用二分图匹配的方式找出最优排序。但是这种平衡方式可能使得到的结果序列在任何可能世界均不存在，并且也不是所有场景都能使用概率总和最大化目标的求解方式。

3）同时综合考虑概率和排序，如global TopK和Expected Rank。

分值与排序的平衡方式一直是不确定数据Top-K查询的重要研究问题。事实上，在平衡概率和分值时，各种不确定性Top-K语义根据不同的应用需要，分别设定了各自的权衡标准，满足各自应用部分的排序要求。Li等人[15]在分析各种排序函数定义缺点的基础上，尝试研究统一化排序，把概率数据库上的Top-K查询问题看成多目标化问题，并且提出一种通用的处理框架和带有2种参数的排序函数PRFw和PRFc。参数的选取直接关系分值与概率的平衡，而且不同的参数的设置使用户能够灵活改变查询结果。

然而由于缺少显式的选择函数和参数描述，需要用户定义合适的排序函数及参数是很困难的。裴建等人[25]提出概率Skyline查询的概念以检索Skyline概率大于某个阈值的不确定对象，避免了用户定义排序函数。但是可能导致无法控制返回结果的数目，因此，用户还是需要设置具体概率阈值。

为了解决概率阈值难于设置的问题，研究尝试将Top-K查询与其它查询方式联合起来，配置支持拓展开发。文献[26]将Top-K查询与Skyline相结合，提出概率Top-K支配（PTD）查询的定义，使其具有Skyline查询和概率排序查询的优点，能够获得针对某个查询点具有最大支配能力的k个不确定对象。文献[27]将传统的聚集查询与Top-K查询相结合，提出排序-聚集查询的概念，通过建模空间搜索问题、引入具有保证性的空间搜索算法和流水线的处理框架，部分枚举解空间快速获得查询结果。这种综合多种查询特征的新型查询方式可以获得多种查询的优势，使得查询结果更有利于实际应用。

3 结束语

综合国内外不确定性Top-K查询的研究现状以及最新研究成果，如何开发高效的查询处理方法、如何平衡分值与概率、如何设计满足不同应用环境的新型查询语义依然是未来研究的重要方向。此外，由于很多现实应用领域数据环境的不确定性和复杂性，例如分布式系统、高维数据库、数据流等，使得在这种环境下的不确定性Top-K查询正日趋现实具体与复杂。分布式系统中如何降低交互程度[28-30]、不确定数据流上Top-K查询时间维的处理[31-32]、高维数据库因维度提高而带来的Top-K语义变化和查询效率问题将成为研究焦点。因此，分布式环境下不确定数据查询方法[33-34]、基于流数据环境下不确定数据查询方法[35-37]、基于高维数据库的不确定查询算法[30，38-41]亦可能成为未来持续研究热点。

参考文献：

[1] 蒋涛，高云君，张彬，等. 不确定数据查询处理[J]. 电子学报，2013，41（5）：966-976.

[2] 李文凤， 彭智勇， 李德毅. 不确定性Top-K 查询处理[J]. 软件学报，2012，23（6）：1542-1560.

[3]郭长友，郑雪峰，高秀莲. 基于不确定理论的不确定性数据Top-k查询计算[J]. 计算机科学.2016，43（3）：225-230.

[4] SOLIMAN M A， LLYAS I F， CHANG K C C. Top-K query processing in uncertain databases[C]//

IEEE International Conference on Data Engineering. Washington： IEEE Computer Society Press， 2007. 896-905.

[5] SOLIMAN M A， LLYAS I F. Ranking with uncertain scores[C]//IEEE International Conference on Data Engineering. Washington：IEEE Computer Society Press， 2009：317-328.

[6] LIAN L， CHEN L. Probabilistic ranked queries in uncertain databases[C]//International Conference on EDBT.New York： ACM Press，2008： 511-522.

[7] GE Tingjian， ZDONIK S， MADDEN S. Top-K queries on uncertain data： on score distribution and typical answers[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. Rhode Island， USA：ACM，2009： 375-388.

[8] ZHANG X， CHOMICKI J. On the semantics and evaluation of Top-K queries in probabilistic databases[J]. Distributed and Parallel Databases， 2009， 26（1）：67-126.

[9] Hua M， Pei J， Zhang WJ， Lin XM. Ranking queries on uncertain data： A probabilistic threshold approach[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver， Canada：ACM， 2008. 673-686.

[10] Hua M， Pei J， Zhang W J， et al. Efficiently answering probabilistic threshold Top-k queries on uncertain data[R]//Burnaby：Simon Fraser University，2007.

[11] HUA M， PEI J. Ranking queries on uncertain data[J]. The VLDB Journal， 2011， 42（1）：9-32.

[12] CORMODE G， LI F， YI K. Semantics of ranking queries for probabilistic data and expected ranks[C]//IEEE International Conference on Data Engineering. Washington： IEEE Computer Society Press， 2009， 23（12）：305-316.

[13] JESTES J， CORMODE G， LI F， et al. Semantics of ranking queries for probabilistic data[J]. IEEE Transactions on Knowledge & Data Engineering， 2010，23（12）：305-316.

[14] RE C，DALVI N， DAN S. Efficient top-k query evaluation on probabilistic data[C] //Proc of Int Conf on Data Engineering（ICDE）. Piscataway，NJ：IEEE，2007：886-895.

[15] LI J， SAHA B， DESHPANDE A. A unified approach to ranking in probabilistic databases[J]. The VLDB Journal， 2011，20（2）：249-275.

[16] LI J， DESHPANDE A. Ranking continuous probabilistic datasets[J]. Proceedings of the Vldb Endowment， 2010，3（1-2）：638-649.

[17] YI K， LI F， KOLLIOS G， et al. Efficient processing of Top-k queries in uncertain databases[C]//IEEE International Conference on Data Engineering. Cancun， Mexico：IEEE，2008，20（12）：1406-1408.

[18] GE T， ZDONIK S. Handling uncertain data in array database systems[C]//IEEE International Conference on Data Engineering.Cancun， Mexico： IEEE， 2008：1140-1149.

[19] ZHANG X， CHOMICKI J. On the semantics and evaluation of Top-K queries in probabilistic databases[J]. Journal of Distributed and Parallel Databases， 2009，26（1）：67-126.

[20] KARP R M，LUBY M.Monte-carlo algorithms for enumeration and reliability problems[C]//24th Annual Symposium on Foundations of Computer Science （sfcs 1983）. Tucson， Arizona，1983：56-64.

[21] SOLIMAN M A， LLYAS I F，BEN-DAVID S.Supporting rankingqueries on uncertain and incomplete data[J].The VLDB Journal，2010，19（4）：477-501.

[22] RE C，DALVI N， SUCIU D. Efficient top-k query evaluation onprobabilistic data[C]//Proc of IEEE ICDE Conf. Istanbul，Turkey：IEEE Computer Society，2007：886-895.

[23] HUA Ming， PEI Jian， LIN Xue-ming. Ranking queries on uncertain data[J].The VLDB Journal，2011，20（1）：129-153.

[24] SOLIMAN M A， LLYAS I F，CHANG C C.Probabilistic top-k and ranking-aggregate queries[J].Acm Transactions on Database Systems，2008，33（3）：15-19.

[25] PEI J，JIANG B，LIN X，et al.Probabilistic skylines on uncertain data[C] //International Conference on Very Large Data Bases.Kohala coast， Hawaii：ACM，2015，38（1）：1-39.

[26] LIAN X，CHEN L.Top-k dominating queries in uncertain databases[C] // Proceedings of the 12th International Conference on Extending Database Technology： Advances in Database Technology.Saint Petersburg， Russia：ACM，2009：660-671.

[27] SOLIMAN M A，LLYAS I F， CHANG C C.Probabilistic top-k and ranking-aggregate queries[J].ACM Trans on Database Systems（TODS）.2008，33（3）：15-19.

[28] WANG G， YUAN Y， SUN Y， et al. PeerLearning： A content-based e-learning material sharing system based on P2P network[J]. World Wide Web， 2011，13（3）：275-305.

[29] LI F， YI K， JESTES J. Ranking distributed probabilistic data[C]//Acm Sigmod International Conference on Management of Data. Providence， RI， USA： ACM ， 2009：361-374.

[30] EL-DESOUKY A/， ALI H/， ABDUL-AZEEM Y M. Ranking distributed uncertain database systems： Discussion and analysis[C]//International Conference on Computer Engineering & Systems. Cairo， Egypt：IEEE，2010，54（1）：295-300.

[31] JIN C Q， YI K， CHEN L， et al. Sliding window Top-K queries on uncertain streams[J]. The VLDB Journal， 2010，19（3）：411-435.

[32] JIN C Q， GAO M， ZHOU A Y. Handling ER-Top K query on uncertain streams[M]// HUTCHISON D， KANADE T， KITTLER J， et al. Lecture Notes in Computer Science， Berlin Heidelberg：Springer ，2011，6587：326-340.

[33] LI Feifei，YI Ke， JESTES J. Ranking distributed probabilistic data[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of data.Rhode Island，USA：ACM，2009：361-374.

[34] DING Xiaofeng，JIN Hai. Efficient and progressive algorithms for distributed skyline queries over uncertain data[J].IEEE Trans on Knowl and Data Eng，2012，24（8）：1448-1462

[35] JIN Cheqing，YI Ke，CHEN Lei，et al. Sliding-window top-k queries on uncertain streams[J].The VLDB Journal，2010，19（3）：411-435.

[36] LIAN Xiang，CHEN Lei.Similarity join processing on uncertain data streams[J].IEEE Trans on Konwl and Data Eng，2011，23（11）：1718-1734.

[37] DING Xiaofeng， LIAN Xiang， CHEN Lei， et al. Continuous monitoring of skylines over uncertain data streams[J].Information Sciences，2012，184（1）：196-214.

[38] BESKALES G， SOLIMAN M A， IIYAS I F. Efficient search for the Top-k probable nearest neighbors in uncertain databases[J]. Journal Proc.of VLDB Endowment， 2008，1（1）：326-339.

[39] ZHANG Ying， ZHANG Wenjie， LIN Xuemin， Jiang B， Pei J. Ranking uncertain sky： The probabilistic Top-K skyline operator. In： Proc. of the Information Systems. 2011. 898915.

[40] LIAN X， CHEN L. Shooting Top-k stars in uncertain databases[J]. Journal of VLDB， 2011，20（6）：819-840.

[41] Wang C H. Top-K ranking with uncertain data [D]. Edmonton： University of Alberta， 2012.