文章总结： 论文提出基于字典分区的高效精准多关键词排序搜索方案DPMRS，通过Word2Vec语义聚类将全局词典划分为子词典，构建字典分区向量空间模型（DPVSM）在不损失精度的前提下压缩向量维度，并设计双层搜索树索引（DSTree-index）将线性搜索转为对数级查询。实验表明该方案在保持100%检索精度的同时，索引存储空间更小，搜索效率较基线提升约40%，但需权衡更高的索引构建成本与动态更新局限性。 综合评分： 96 文章分类： 数据安全,云安全,解决方案,应用安全

论文研读与思考|DPMRS:基于字典分区的高效精准多关键词排序搜索方案在云计算中的应用

Yue Yue

玄枢战队-Arcane Hub

2026年3月19日 22:16 陕西

原文题目：Efficient and Accurate Dictionary Partition-Based Multi-Keyword Ranked Search Scheme in Cloud

原文作者：Zhangchen Li;Hua Dai;Yinfu Deng;Qian Zhou;Geng Yang;Xun Yi

期刊：IEEE Transactions on Cloud Computing

一、主要研究问题、目标及方法

1.1 核心研究问题与研究动机

在信息检索领域，传统的TF-IDF（词频-逆文档频率）向量空间模型被广泛使用，它将文档和查询转化为高维向量，并通过计算向量相似度，比如余弦相似度，来实现相关性排序。其核心计算公式如图1：

图1

（注：TF指词频，衡量一个词在单个文档中的出现频率；IDF指逆文档频率：衡量一个词在整个文档集合中的普遍重要性。TD-IDF值越高，通常认为该词对当前文档越重要、越有区分度）

在传统的非加密信息检索环境中，此模型因其相对简单的实现和不错的效果而被广泛采用。然而，当它应用于云环境中的隐私保护多关键字排序搜索时，它为整个文档集合词典中的每个唯一关键词都创建一个维度，导致生成的文档向量和查询向量维度极高。同时，由于单个文档仅包含少量关键词，这些向量极度稀疏。这种高维稀疏性带来了巨大的索引存储与计算开销，因为文档与查询的相关性分数需要通过大规模向量内积来计算，严重降低了搜索效率。

在已有研究中，EGMTS是一种基于字典分区的优化方法，但其在分区过程中忽略了关键词之间的语义关联；ML-RKS是一种基于文档聚类的优化方法，但未能有效降低向量维度，导致搜索效率存在局限。因此，论文的核心研究问题是如何克服传统TF-IDF模型在加密云数据搜索场景下的高维稀疏性瓶颈。

1.2 关键方法、模型及理论框架

论文提出了一种基于字典分区的加密更新多关键词排序搜索方案（DPMRS）及其增强版DPMRS+。包括以下几个方面：

（1）系统模型与问题定义

如图2所示，论文的系统模型基于典型的数据外包场景，包含数据所有者DO、云服务器CS和数据据用户DU三个实体，采用“诚实但好奇”的威胁模型，即CS会执行协议，但会试图从存储的加密索引和收到的搜搜请求中分析、推断出原始数据和用户查询的隐私信息。在此框架下，将研究目标形式化为一个隐私保护的多关键字排序搜索问题。

图2

（2）字典分区向量空间模型

首先设计了基于字典分区的向量空间模型（DPVSM），此模型不是为整个词典构建单一高维向量，而是引入了一个创新的预处理步骤：利用Word2Vec模型和余弦相似度来衡量关键词之间的语义关联，并通过二分k-means聚类算法，将全局词典划分为多个语义相关的子词典。每个子词典被设置为固定长度，缺失位置由无意义的“虚词”填充。

基于此划分，每个文档和查询请求都被表示为一组对应于这些子词典的低维子向量（文档子向量编码词频，查询子向量编码逆文档频率）。

从数学上严格证明在这种模型下，通过计算所有相关子词典上的子向量内积总和，所得的相关性分数与在原始高维TF-IDF向量空间模型中的计算结果完全等价。这就实现了在不损失准确性的前提下，对向量维度的根本性压缩，为后续所有高效操作奠定了基础。

（3）索引结构设计

在DPVSM模型之上，论文设计了两层递进的索引结构以实现高效、隐私保护的检索。

基准索引：字典分区关键词分布倒排索引（DPKD-index）是一种创新的倒排索引结构。它不仅为每个子词典维护一个身份向量用于快速定位，它还引入了“关键词块”的概念。在每个子词典内部，关键词被动态分配到多个块中，每个块与一个固定大小的文档列表相关联，其中，文档列表由真实文档和“虚文档”填充。

通过构造的“关键词块向量”和“文档子向量”列表，实现了两个目的：

①在检索时能快速判断一个块是否包含搜索关键词；

②通过均衡每个块关联的文档数量，有效隐藏了关键词的真实热度信息，防止云服务器进行频率分析攻击，从而增强了隐私保护。

高效索引：为了进一步提升搜索效率，论文将DPKD-index优化为双层搜索树索引(DSTree-index)。

上层搜索树是一个二叉树，其叶子节点指向各个子词典，内部节点的向量是其子节点向量的逻辑或，用于从全部子词典中快速筛选出包含查询关键词的少数相关子词典。下层搜索树则是为每个子词典独立构建的二叉树，其叶子节点对应子词典内的关键词块，功能类似上层树，用于在该子词典内快速定位包含查询关键词的特定块。这种树形结构将搜索过程中的线性遍历转化为对数级的路径搜索，极大地缩减了检索时间。

（4）DPMRS与DPMRS+

基于上述模型与索引，论文构建了两个具体的搜索方案，图3给出了DPMRS完整框架，展示了从子词典生成、密钥生成、索引构建、陷门生成到安全搜索的全过程。其算法如下：

GenSD：用于获取子词典；

GenKey：用于生成密钥；

BuildInde：生成加密索引和加密文档

GenTrapdoor：根据查询请求生成陷阱门；

Search：用于实现多关键词排序搜索并返回结果。

图3

基线方案DPMRS：完整地实现了DPVSM模型和DPKD-index。

其工作流程包括：DO执行词典分区、生成密钥、构建并加密DPKD-index；DU根据查询生成加密的搜索请求（陷门）；CS利用加密索引和陷门，通过安全内积计算，遍历相关子词典和关键词块，计算所有候选文档的相关性分数，并返回top-k结果。

增强方案DPMRS+：在DPMRS的基础上，用DSTree-index替代了DPKD-index。

核心改进在于搜索算法方面，CS在接收到陷门后，首先在上层搜索树进行快速剪枝，直接定位到相关子词典；随后在对应子词典的下层搜索树中再次快速定位到含有关键词的具体块。

二、主要发现、结论及创新点

2.1 核心结果与主要发现

在索引存储方面，由于字典分区向量空间模型有效压缩了向量维度，所构建的索引占用的存储空间小于基线方案。

在搜索精度方面，DPVSM模型在数学上严格保证了与传统TF-IDF模型的等价性，方案能够实现100%的检索精度，确保了结果的准确性。

在搜索效率方面，基准方案DPMRS通过维度压缩和结构化索引，显著降低了计算开销；采用双层搜索树索引的增强方案DPMRS+，通过将对索引的线性遍历转化为对数级查询路径，实现了搜索时间的进一步缩减。

该方案在提升在线搜索阶段效率的同时，也增加了离线预处理阶段的时间成本。

2.2 作者得出的关键结论

研究提出了一种基于字典分区的高效多关键词排序搜索方案，适用于云计算环境。该方案采用字典分区向量空间模型，既能压缩向量维度以加速相关性评分计算，又可确保评分结果的准确性。

通过构建基于字典分区的关键词分布倒排索引，提出了基准搜索方案。为提升搜索效率，创新性地采用双层搜索树索引结构，并提出增强型搜索方案DPMRS+。安全分析表明，该方案能有效保护索引数据与搜索过程中的隐私信息。实验结果表明，在索引存储容量、搜索精度及搜索效率等关键指标上，本方案均优于现有技术。

2.3 创新点

●提出基于词典分区的向量空间模型（DPVSM），该模型可压缩向量维度，从而在不影响计算结果的前提下加速相关性分数的计算，其计算结果与传统TF-IDF向量空间模型相当。

●提出一种基于词典分区的关键词分布倒排索引（DPKD-index），该方法利用DPVSM和关键词块。基于DPKD-index，研究提出了一种名为DPMRS的基准方案，旨在实现高效且隐私保护的多关键词排序搜索。

●通过采用基于所有子词典及其内部结构的树状索引，研究将DPKD索引优化为双层搜索树索引（DSTree-index）。在此基础上，提出了一种增强型搜索方案 DPMRS+，该方案显著提升了搜索效率，但树形索引结构增加了存储开销。

三、研究方法及相关数据

3.1 研究设计与实验设置

论文形式化定义了系统模型、威胁模型和安全目标，并完整构建了从DPVSM、DPKD-index到DSTree-index，以及从DPMRS到DPMRS+的方案流程。

通过形式化的安全游戏和分析，证明了方案能够抵御选择明文攻击和统计攻击，满足设定的隐私保护要求。

通过对比实验，评估了方案在各项性能指标上的表现。实验设置了包括文档数量、查询关键词数、返回文档数、词典分区参数、关键词块大小等在内的多种变量，以全面测试方案的鲁棒性和可扩展性。

3.2 数据集特点

论文选用了纽约时报数据集，这是信息检索领域广泛使用的真实数据集，规模庞大，包含超过100万篇真实的新闻文档，文本内容丰富，关键词分布自然，能够模拟实际云存储环境中的文档集特点。使用此类公开的标准数据集，保证了实验的可重复性和可比性，也使实验结果更具说服力和现实参考价值。

3.3 性能评估

论文分别从索引构建与更新、索引存储性能、搜索精度以及搜索效率四个方面对方案进行了全面评估，并通过与现有方案EGMTS、ML-RKS的对比，验证了方案。表1给出了相关参数设置，其中n表示F中的文档总数，|Q|为搜索关键词数量，k为返回文档数量，β为分区参数，ω为关键词分布参数，ψ为预留参数。

（1）索引构建与更新评估

该部分评估方案在数据上传前的预处理开销，如图4所示，（a）中显示四种方案的索引构建时间均随文档数量增长而延长，这是因为文档量的增长会导致关键词数量、聚类时间、向量维度及其他相关因素的增加；（b）和（c）表明，尽管关键词分布和分区参数存在差异，DPMRS和DPMRS+的索引构建时间仍保持稳定；（d）显示随着预留参数的增大，DPMRS和DPMRS+的索引构建时间均会延长。这是因为预留参数的增加会导致子向量维度增大，从而使得目标向量的生成和加密时间延长。

图4

由于需要进行词典的语义聚类并构建多层索引结构，DPMRS和DPMRS+方案的索引构建时间高于EGMTS和ML-RKS等基线方案，DPMRS+的构建时间曲线通常最高，因为它需要构建更复杂的树形索引。该评估证实，本方案的设计权衡在于以更高的、一次性的预处理成本，换取显著降低的、反复发生的在线搜索成本。

图5展示了不同参数下索引的更新时间，随着文档数量、预留参数和更新文档数量的增加，索引更新时间会相应延长。这是因为文档数量增多、预留参数提升以及更新频率提高时，需要遍历更多子词典和数据块，生成更高维度的向量，或替换更多向量。

图5

（2）索引存储器性能评估

主要来衡量加密索引在云服务器端所占用的存储空间。图6（a）-（d）显示，与EGMTS和ML-RKS相比，DPMRS和DPMRS+的索引空间更小。这归因于DPMRS和DPMRS+中DPVSM的使用，它在压缩向量的同时减少了子向量的数量，从而减小了索引的总体大小。此外，由于DPMRS+使用了二叉商搜索树，其索引空间略大于DPMRS。

图6

（3）搜索精确度评估

论文通过理论证明了DPVSM模型与原始TF-IDF模型的等价性，并通过实验进行了验证。

图7

图7表明，DPMRS和DPMRS+的搜索结果均展现出高精度。EGMTS的精度低于100%的原因在于，部分与查询Q相关的文档未被纳入候选文档范围，这些相关文档因此未对排名产生影响，ML-RKS也是一样的情况。但DPMRS和DPMRS+在参数调整过程中，所有相关文档均会被视为候选文档。

（4）搜索效率评价

这部分是评估方案在线性能的关键，主要衡量返回Top-k相关文档所需的搜索时间。如图8（a）-（I）中所示，与EGMTS相比，DPMRS可节省约20%的搜索时间成本，DPMRS+可节省约40%的搜索时间成本。由于DPMRS和DPMRS+采用DPVSM技术，查询相关子字典的规模得以缩减，从而减少了搜索过程中所需的浮点运算量，进而缩短了搜索时间。

图8

四、论文的局限性、未来方向及潜在影响

4.1 研究的不足与限制因素

在离线处理阶段，由于需要基于语义对全局词典进行聚类，并且构建多层索引结构，导致方案的索引构建时间显著长于一些简单的基线方案。

为了达到更高的搜索效率，增强方案DPMRS+采用了复杂的树形索引结构，这使得它难以支持高效的动态更新，比如文档的插入、删除等操作，限制了其在文档频繁变动的场景下的应用。

4.2未来研究方向

  研究更轻量、更快速的聚类算法或分区策略，以降低索引构建的开销；设计支持高效动态更新的树形或其它索引结构，增强方案的实用性。

同时可以将字典分区的核心思想扩展到更复杂的搜索场景，比如支持模糊搜索、语义搜索或范围查询。

4.3 适用范围及潜在影响

研究主要适用于需要在云环境下对加密数据进行高效、准确的多关键字排序搜索的场景，例如加密的企业邮件系统、隐私保护的云盘文档检索、医疗或金融领域的合规数据查询等。

研究提出的DPVSM模型和DSTree-index结构为可搜索加密领域提供了新的技术思路，采用的“通过分区和聚类压缩维度”的思想可以被借鉴到其他高维稀疏数据处理的隐私计算任务中。该方案还为云服务提供商设计既能保护用户数据隐私，又能提供高效检索服务的产品，提供了一种可行的技术路径，有助于在数据安全和数据效用之间取得更好的平衡。

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：玄枢战队-Arcane Hub Yue Yue《论文研读与思考|DPMRS:基于字典分区的高效精准多关键词排序搜索方案在云计算中的应用》