买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜浙江大学申请的专利一种基于树-图结构的高维空间向量动态最近邻搜索方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN118964364B 。

龙图腾网通过国家知识产权局官网在2025-03-14发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202411452938.7，技术领域涉及：G06F16/22；该发明授权一种基于树-图结构的高维空间向量动态最近邻搜索方法是由高云君;马瑞遥;朱轶凡;柳晴;罗程阳设计研发完成，并于2024-10-17向国家知识产权局提交的专利申请。

本一种基于树-图结构的高维空间向量动态最近邻搜索方法在说明书摘要公布了：本发明公开了一种基于树‑图结构的高维空间向量动态最近邻搜索方法，包括：获取高维空间向量集合，为所有向量对象构建全局树索引，并基于树索引的中间层级构建轻量化的层次图索引，完成树‑图结构的构建；获取待插入和待删除的向量对象，更新全局树索引和轻量级层次图索引，完成树‑图结构的动态插入和删除；利用树‑图结构进行高维空间向量对象的近似最近邻搜索或精确最近邻搜索，得到给定查询向量对象的k‑近邻对象。本发明能够显著降低索引构建成本，灵活地应对实时数据更新，并支持高效且通用的高维空间向量最近邻搜索。

本发明授权一种基于树-图结构的高维空间向量动态最近邻搜索方法在权利要求书中公布了：1.一种基于树-图结构的高维空间向量动态最近邻搜索方法，应用于人脸识别系统，所述高维空间向量动态最近邻搜索方法包括如下步骤：（1）获取高维空间向量集合，为集合中的所有向量对象构建全局树索引，并为全局树索引的第一层构建轻量级层次图索引，完成树-图结构的构建，具体实现过程如下：S11：获取高维空间向量集合、节点容量参数和图稀疏度参数，初始化全局树索引和轻量级图索引为空集；S12：任选一个未被访问的向量对象，按照M-树索引的策略为其创建叶条目，并将该向量对象作为叶条目的中心点；S13：按照M-树索引的策略，将叶条目插入到全局树索引中，全局树索引中每个节点所容纳的条目数量不超过节点容量参数；S14：重复步骤S12~S13，直至高维空间向量集中的所有向量对象均被插入到全局树索引中，即完成全局树索引的构建；S15：获取全局树索引的第一层，即叶条目所在层级上一层的所有条目；初始化轻量级层次图索引的入度半径表为空，所述入度半径表存储轻量级层次图上各顶点的入度边半径；S16：任选一个未被访问的第一层条目，按照HNSW层次图索引的策略将其中心点作为顶点，插入到轻量级层次图索引中，并更新入度半径表；所述轻量级层次图索引上每个顶点的最大邻居数由图稀疏度参数控制；S17：在轻量级层次图索引的底层处为所述顶点加入指针，指向全局树索引中该第一层条目所对应的叶节点；S18：重复步骤S16~S17，直至全局树索引第一层的所有条目均被插入到轻量级层次图索引中，即完成轻量级层次图索引的构建；S19：合并全局树索引和轻量级层次图索引，得到树-图结构；（2）获取待插入和待删除的向量对象，更新全局树索引和轻量级层次图索引，实现树-图结构的动态插入和删除；对于待插入的向量对象，实现树-图结构动态插入的具体过程如下：S21：获取待插入的向量对象，根据当前的树-图结构获取全局树索引的信息；S22：按照M-树索引的策略，为待插入的向量对象创建叶条目，并将该向量对象作为叶条目的中心点；S23：按照M-树索引的策略，将叶条目插入到全局树索引中；如果插入叶条目未导致全局树索引中叶节点的分裂，即全局树索引的第一层没有变化，则无需更新轻量级层次图索引，转至执行步骤S26；如果插入叶条目导致全局树索引中叶节点的分裂，即全局树索引的第一层产生新条目，则需要更新轻量级层次图索引，即执行步骤S24~S25；S24：根据当前的树-图结构获取轻量级层次图索引的信息，按照HNSW层次图索引的策略，将全局树索引第一层新条目的中心点作为顶点，插入到轻量级层次图索引中，并更新入度半径表；S25：在轻量级层次图索引的底层处为所述顶点加入指针，指向全局树索引中第一层新条目所对应的叶节点；S26：合并插入更新后的全局树索引和轻量级层次图索引，完成树-图结构的动态插入；对于待删除的向量对象，实现树-图结构动态删除的具体过程如下：S31：获取待删除的向量对象以及搜索候选集参数，根据当前的树-图结构获取全局树索引和轻量级层次图索引的信息；S32：利用当前树-图结构，以待删除的向量对象为查询对象，通过近似最近邻搜索以定位该查询对象；如果成功在树-图结构中找到该向量对象，则执行转至步骤S34；如果未能成功找到，则需要进一步利用范围搜索进行定位，即执行步骤S33；S33：以待删除的向量对象为中心，在全局树索引上执行半径为0的精确范围查询，以定位该向量对象；如果未能成功在全局树索引中找到该向量对象，则表示该向量对象不存在，立即终止删除操作；如果成功找到，则继续执行步骤S34；S34：根据M-树索引策略的删除规则，将成功定位的待删除向量对象从全局树索引中删除；如果删除该向量对象未导致全局树索引中叶节点下溢出，即全局树索引的第一层没有变化，则无需更新轻量级层次图索引，转至执行步骤S38；如果删除该向量对象导致全局树索引中叶节点下溢出，即全局树索引的第一层有条目被删除，则需要更新轻量级层次图索引，即执行步骤S35；S35：识别全局树索引第一层中被删除条目的中心即轻量级层次图索引中待删除的顶点，在轻量级层次图索引的底层处删除该顶点中指向全局树索引第一层中被删除条目所对应叶节点的指针；S36：以待删除的顶点为中心，在全局树索引中执行精确范围查询，半径为该顶点在入度半径表中所存储的入度半径，从而找到待删除的顶点在轻量级层次图索引中的所有入度边；S37：从轻量级层次图索引中删除该顶点及其对应的边，包括S36中获取的入度边以及直接在轻量级层次图索引中获取的出度边，并更新入度半径表；如果删除顶点和边后导致轻量级层次图索引中一些顶点的邻居数量减少，导致违反图的构造规则，则根据HNSW层次图索引的策略将这些邻居数量过少的顶点重新插入到轻量级层次图索引中；S38：合并删除更新后的全局树索引和轻量级层次图索引，完成树-图结构的动态删除；（3）利用树-图结构进行高维空间向量对象的近似最近邻搜索，得到给定查询向量对象的k-近邻对象，具体实现过程如下：S41：获取给定的查询向量对象、树-图结构、搜索候选集参数以及k-近邻参数；S42：根据树-图结构获取全局树索引和轻量级层次图索引的信息；S43：初始化搜索候选集为空集；S44：在轻量级层次图索引的顶层随机选择一个顶点作为搜索的入口起点；S45：从入口起点开始在当前层执行贪心搜索，不断扩展顶点的邻居，直至找到查询向量对象在当前层的近似1-近邻，搜索过程中令候选集长度为1；S46：将找到的近似1-近邻作为轻量级层次图索引下一层的入口起点；S47：重复步骤S45~S46，直到从轻量级层次图索引的顶层搜索到第一层；S48：以在第一层找到的近似1-近邻作为底层搜索的入口起点，在底层执行贪心搜索，并将搜索结果加入到搜索候选集中，候选集的长度为搜索候选集参数；底层搜索不仅包括直接访问底层上的顶点邻居，还包括访问由底层顶点所指向全局树索引中的叶节点；S49：从搜索候选集中找出与查询向量对象距离最近的k个近邻，作为最终的搜索结果；在人脸识别系统中，每个人的面部特征被转换为高维向量，通过比较这些向量以实现人脸识别和验证。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人浙江大学，其通讯地址为：310058 浙江省杭州市西湖区余杭塘路866号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。