对加密数据的高效相似性查询（二）

? 四、 实验评估

主要对实验从检索和性能两方面进行评估：

1.由于使用了LSH算法，可以用平均检索率和查询点q的平均距离来衡量。

记wq 是文档Di中的单词，使用转换函数得到p(wq)和p(q)，计算dist(q,Di),这里的dist是Jd(p(wq),p(q)).设D是文档集合，RDq是对q进行检索得到的集合，Ddkq是距离q为dk的数据的集合，则检索率和平均检索率有如下定义：

当查找到的数据点满足度量标准时，在给定的距离阈值内检索率会很高，即这些数据点会有很高的概率共享一个桶。

记RmDq是共享m个桶的检索到的数据点，平均距离有如下定义：

当m越大时数据点共享到相似的桶的几率更高，所以距离会逐渐变小。

2.设ADN-OR的LSH哈希函数族有参数k和l（哈希函数的个数和混合哈希函数的个数），数据项个数nd和特征个数nf，对搜索时间和协议数据进行评估。

搜索时间是在搜索请求和数据索引的定义之间的时间。

协议数据是指在客户端和服务器之间传输的数据的数量，数据包括陷门，加密的位向量和文档标号。

随着k的增加搜索时间和协议数据都会不断减小，随着l的增大他们会相应增大，这是由于相应的数据索引在相应的减小或增大导致的结果。同样当nd增加时，搜索时间和协议数据会相应增大，nf的变化基本不影响算法性能。

总之基于LSH的安全索引实现对加密数据的可索索对称加密方案中检索效率是比较高的，并且在Curtmola严格的自适应语义安全定义下对方案的安全性进行了证明并确保了安全性。