Page 455 - 《软件学报》2025年第8期

3878 软件学报 2025 年第 36 卷第 8 期

实际上, 3 个方案的搜索时间主要受更新计数器值最小的关键词 (如前所述的 w 1 ) 所更新的文件数量的影响.
图中 RFBC 的搜索时间显然优于 BDXT 和 ODXT, 其原因如前所述, 当更新计数器数值固定时, ODXT 方案需要
在客户端通过模幂运算计算出更新计数器值最小的关键词所更新的所有文件与每个查询关键词对应的 xtoken, 在
服务端也要执行类似的操作, 因此 ODXT 方案的搜索时间要明显高于 BDXT 方案和 RFBC 方案. 而 BDXT 方案
需要在 ClientRound2 阶段筛选出更新计数器值最小的关键词所更新的所有文件, 计算这些文件与每个查询关键词
对应的两个 xtag, 并在 ServerRound2 阶段对这些 xtag 进行判断操作, 最后将判断结果返回给客户端, 客户端在
FinalOutput 阶段根据服务器返回的判断结果判断在更新计数器值最小的关键词所更新的所有文件中保留哪些文
件. 此过程需要客户端与服务器的多轮通信及多次筛选操作, 所以时间开销大于 RFBC. 而 RFBC 相较于 ODXT 不
需要复杂的模幂运算, 相较于 BDXT 无需多轮通信, 也无需多次筛选操作, 只需简单的计算出 token 并将其发送至
服务器端, 使用布隆过滤器的判断即可筛选出目标文件集合.
(5) 多关键词搜索时间开销
图 9 描述了不同关键词个数对搜索时间开销的影响. 从图 9 中我们可以看出, 在固定更新数据量的情况下, 随

着多关键词联合查询的个数逐渐增加, RFBC 和 BDXT 的搜索时间基本不变, 也就是说, 联合查询的关键词个数
对 RFBC 和 BDXT 没有影响. 同时, RFBC 的多关键词搜索时间不到 BDXT 的 1/2. ODXT 的搜索时间均高于
RFBC 和 BDXT, 且随着关键词个数的增加, ODXT 的查询时间逐渐增长. 其原因如上文所述, ODXT 需要对联合
查询中的关键词执行模幂运算, 因此造成了计算开销的上升.
图 10 则描述了不同关键词长度对搜索时间开销的影响. 我们以基准关键词的不同倍长度为测试变量 (×n 表
示 n 倍, n 为 1–8), 从图中我们可以看出, 在同样固定更新数据量的情况下, 随着联合查询中关键词的长度逐渐增
加, 3 个方案的搜索时间均基本不变, 也就是说, 联合查询的关键词长度对三者均无影响. 本文的 RFBC 在此种情
况下的搜索时间低于 BDXT 和 ODXT, 分别约为他们的 1/2 和 1/5.

70
RFBC
12
60 BDXT
ODXT
10
50 8
搜索时间 (s) 40 搜索时间 (s) 6 RFBC
BDXT
ODXT
30
20 4
10 2
0 0
2 3 4 5 6 7 8 9 10 ×1 ×2 ×3 ×4 ×5 ×6 ×7 ×8
5
关键词个数 (数据量为6×10 ) 5 关键词长度 (数据量为6×10 )
图 9 不同关键词个数的搜索时间开销 图 10 不同关键词长度的搜索时间开销

4.3 通信开销比较
我们主要通过比较 RFBC、BDXT 和 ODXT 在联合搜索过程中的通信开销来评估它们的通信效率. 与计算开
销的评估方法相似, 我们同样设置不同比例的不合理更新来观察其对搜索过程通信开销的影响. 实验结果如图 11
所示, 其中横坐标代表更新数量, 纵坐标代表搜索过程的通信开销. 显然, 随着更新数量的上升, 相应的通信开销也
随之上升, 但是随着不合理更新比例的增加, RFBC 的通信开销仍显著低于 BDXT 和 ODXT.
由于 RFBC 和 ODXT 仅需一轮通信就可得到联合搜索结果, 且客户端与服务器之间传输的数据较少, 而 BDXT
需要两轮通信才能完成联合搜索, 因此 RFBC 和 ODXT 的通信开销明显低于 BDXT. 具体来讲, RFBC 首先使用伪
随机函数计算出每个关键词对应的关键词令牌, 再计算出关键词对应的布隆过滤器的存储地址, 最后将关键词令