《表2 RI-MHT中不同算法的计算成本》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《云环境中基于相对索引散列树的数据审核方法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

下面将给出RI-MHT的计算成本，并与文献[3，6]进行比较。为简便起见，分析实验使用表1给出的符号。RI-MHT中每个算法的计算成本如表2所示。其中，n表示数据块总数；t表示质询数据块数量。上述三种协议的计算成本比较如表3所示。由表可知，所提协议的效率高于其他两个协议。文献[3]搜索数据块的计算时间较长，并根据块数量增长而呈线性变化，即O（n）。所提协议中，由于使用了先对索引字段，搜索一个节点的复杂度被降低为O（log n）。所提搜索算法的计算复杂度与在包括（2n-1）个节点的二叉搜索树[11]（BST）中搜索一个元素相似，而文献[3]则与线性搜索算法的计算复杂度相似。图4给出了所提协议在频繁数据改动中的性能。实验中对1 GB的文件进行更新，其中更新的块数量从100～1 000变化。由图可知，随着被改动块数量的增加，文献[3]计算成本增加的速率高于本文协议，而文献[6]则不支持数据动态操作。