论文部分内容阅读
图的最小生成树在网络设计,VLSI以及道路交通建设等领域中有着重要的应用价值。在现实应用中,随着系统复杂性的提高,不确定性数据频繁出现在各种领域中。当图数据中存在不确定性因素时,传统的最小生成树不能适用在某些应用场景中。例如,无线传感网络中的通信链路存在断链的可能,交通网络中某些路段也存在一定的不通行概率,在这样的图数据中获得的最小生成树通常也是不确定的。因此,基于不确定图数据研究最小生成树相关问题具有重要的理论意义与应用价值。本文面向图结构不确定的图数据研究最小生成树查询相关问题。具体地,图的任意边的边权是一个二元组(W,P),其中W表示边的代价权,P表示边存在的概率,W在边存在时有效,在该不确定图上快速查询P-TopK最小生成树是本文的研究目标。本文首先提出了基于多维分组组合过滤的查询算法(CA_MG)来解决该问题。CA_MG算法是在现有的动态组合过滤算法(CA_Dyn)的基础上改进的,针对CA_Dyn中对组合分组过多而导致过滤性能差的特点,提出了多维分组的概念,并给出了一种基于多维分组过滤的策略。此外,考虑到算法中对所有组合判树以及计算最小生成树概率这两个过程时间消耗较大,于是提出了一种基于环匹配的优化策略,该策略预处理出图中所有环并对环建立索引,使得上述两个过程可以简化为在索引上匹配环的过程。实验表明,CA_MG算法在现有的基于组合过滤的算法中,具有最好的性能,加入环匹配优化的CA_MG算法也有相应的性能提升。事实上,所有基于组合过滤的查询算法都存在因为组合数量较多而导致查询性能偏低的特点。CA_Dyn和CA_MG虽然通过对组合进行分组而过滤掉了一部分组合,但组合的局部有序性仍然使得过滤能力受限。基于以上分析,本文提出了基于上界树过滤的查询算法(FA_KMUBT)。具体地,首先给出了最大上界树以及K大上界树的概念及其计算方法,然后提出了在若干棵全局有序的上界树中查询P-TopK最小生成树的方法,该方法由于候选空间较小,具有较强的过滤能力。实验表明,FA_KMUBT在所有算法中具有最高的查询性能。考虑到该问题的计算规模较大,本文在CA_MG算法的基础上提出了一种简单但有效的并行查询P-TopK最小生成树的方案。在该方案中,首先提出了组合划分的概念,在进一步分析了多维分组的性质之后,提出了一个基于多维分组的组合划分算法,可以有效地将组合空间划分成近似均匀的若干分区。通过将每个分区交由不同的处理机并行计算,然后汇总所有分区的局部计算结果得到最终查询结果。实验表明,并行的CA_MG算法由于相对均匀的数据划分和较小的通信开销,其性能随着处理机个数的增加而增加明显。