基于特征类型概率剪枝查询的算法研究

占美星 范少帅 周鹏

摘 要：針对不确定对象的最近邻反向查询没有考虑多种特征类型而不能满足复杂的应用场景的问题，提出了基于限界剪枝和概率剪枝的多类型概率最近邻反向（Multiple types probabilistic nearest neighbor reverse，MTPNNR）查询算法。限界剪枝利用最小耗费来修剪不可行解或者非最优解对象;概率剪枝是基于概率分布模型和不确定对象分解的策略，根据概率各个阀值和剪枝的深度来控制需要剪枝的精度。与原始基于定义的算法相比较，MTPNNR查询算法在CPU资源开销方面有比较大的优势，能够完成在较大数据复杂等环境下的查询。基于实验结果显示，MTPNNR算法在离散型的数据集和不确定数据集上有比较好的查询效率。

关键词：不确定对象;最近邻反向查询;概率剪枝;限界剪枝

1 绪论

在数据集中，其不确定性是一个比较新的领域，并且一直受到许多关注和研究。Lian等人于2009年首次提出了的LC算法，[1]在LC算法中第一次研究了PRNN问题，对于不确定对象LC算法采用了连续的概率密度函数来表示，该算法采用了数据集中的可能模型，对于数据集的不确定区域划分为球形区域，当查询的结果大于该概率阀值则成为RNNs。

Cheema等人于2010年首次提出了CLWZP算法，[2]但该算法仅仅适合用于离散分布情况，并且采用了基于非平凡修建的规则和概率阀值的修剪算法，这样能够解决高维空间的不确定修剪不确定和收缩修剪区域的问题，比近似抽样算法具有更高效和更具有扩展性。

Emrich等人于2010年对MBRs的空间剪枝方法提出了最优的研究方法，而Bernecker等人于2010年对概率近似性排序研究了相关算法，[4]该算法提出了概率剪枝法来加速排除不确定对象的相似。[5]基于这些前提的研究，Bernecker等人于2011深入研究了PNNR查询，首次提出了概率修剪方法。[6]目前对确定数据集对象上多类型最近邻反向查询有一部分相关研究。[7-12]本文针对多个不同类型的不确定数据集对象，提出了MTPNNR查询的概念，并基于离散型不确定数据集对象模型提出了MTPNNR查询算法。

2 相关理论

2.1 基本概念

4.2 实验

本实验通过与base-MTPNNR算法相比较及逐步调整各输入参数来验证MTPNNR算法的有效性。MTPNNR算法与base-MTPNNR算法相比，对于概率提纯和过滤的上，采用了分层的概率剪枝，这样大大节省了计算所有概率特征线路和所有不确定数据集的实例。

图1比较了MTPNNR算法与base-MTPNNR算法的性能。如图所示，当FT=1时，其算法相差不大，查询时间基本相等。图2比较了基线算法和MTPNNR算法关于Ins查询性能。

图3描述了概率阀值对MTPNNR查询的效率影响。从图中可以看出MTPNNR的执行时间是随着τ值的增大而减小。这是由于较大的τ值会使互斥的最小概率1-τ的值减小，那么当MTPNNR概率阀值增大时，其搜索空间对象相应的随着被修剪的概率1-τ减小而减少，所以在概率剪枝计算时，是很快找到所需的修剪阀值，是的增快了剪枝速度。

图4-4是展示了MTPNNR算法对于Maxdep的查询性能分析的结果，从图中看到，随着Maxdep增大，可以明显的降低提炼步骤的CPU资源消耗。很显然对于Maxdep来说，提炼步骤是主要的资源瓶颈，这是因为对于较小的Maxdep值，每个在用于概率剪枝的不确定数据集对象的子区域集合是很小的，但是其分区很大。

经过本次实验可知，MTPNNR算法的查询性能是与各个输入参数有直接的联动关系，并且实验结果验证了MTPNNR查询算法的有效性，并且能够在较合理的时间段内完成相关查询和剪枝。

5 结语

本文提出了多类型概率最近邻反向查询MTPNNR算法。并且针对MTPNNR查询的需求，提出了SL-PFL和LL-PFL的特征概率修剪方法，从而整天提高了算法的空间查询和剪枝效率。其次是运用了限界剪枝方法，分层进行剪枝，最后通过计算概率剪枝的上下界的方法进行概率剪枝，最后通过实验，并且通过调整输入参数使得MTPNNR查询算法达到最优，并且实验结果验证了MTPNNR算法的有效性，能为不确定数据集对象上的多类型概率最近邻反向查询提供有意义的参考。

参考文献：

[1]Lian X，Chen L.Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data[J].The VLDB Journal，2009，18（3）：787-808.

[2]Cheema M A，Lin X，Wang W，et al.Probabilistic reverse nearest neighbor queries on uncertain data[J].IEEE Transactions on Knowledge and Data Engineering，2010，22（4）：550-564.

[3]Emrich T，Kriegel H P，Kroger P，et al.Boosting spatial pruning：On optimal pruning of MBRs[C].Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.New York：ACM Press，2010：39-50.

[4]Bernecker T，Kriegel H P，Mamoulis N，et al.Scalable probabilistic similarity ranking in uncertain databases[C].Proceedings of IEEE Transactions on Knowledge and Data Engineering.[s.l.]：TKDE Press，2010：1234-1246.