一种边缘存储系统中面向相似数据共享的索引方法

1.本技术涉及数据处理技术领域，特别是涉及一种边缘存储系统中面向相似数据共享的索引方法、计算机设备和存储介质。


背景技术：

2.通过将计算和存储能力转移到网络边缘，边缘计算可以良好地支持计算密集和延迟敏感应用的部署。到目前为止，大约有数百zettabyte的数据分布在网络边缘。然而，如此庞大的数据目前还远远没有得到充分利用。根据希捷公司的报告，约68％的数据仍尚未得到良好利用。原因之一是缺乏跨边缘服务器的有效共享机制，零散存储的数据无法组织起来。为了弥补这一不足，研究人员致力于设计边缘数据共享系统作为边缘计算应用的基础服务。它精细地将用户端上传的数据跨边缘服务器分发，并使每个用户能够通过最近的代理服务器访问所有共享数据。也就是说，用户的数据请求首先上传到边缘数据共享系统中距离用户最近的边缘服务器，该服务器从其本地存储系统或其他边缘服务器中查询或插入数据。然而，数据查询可能会引起相当大的跨服务器通信开销和响应延迟。因此，我们需要以最低的查询成本和延迟处理这类数据请求。基于这一见解，最近的研究工作提出了一系列边缘数据共享方案，这些工作通过基于虚拟平面的索引机制交付数据，并在具有一定网络半径的系统下实现了0延迟。
3.然而，现有的边缘数据共享系统设计不能实现高效的相似性数据共享，即通过输入的高维特征查询请求，从在网络边缘分布存储的高维数据集中检索相似数据。实际应用中，相似数据共享是边缘应用的一个普遍而重要的要求。每个边缘服务器保存一些共享图像，并为附近的用户提供数据存储(插入)和检索(查询)服务。现有的边缘数据共享系统只能帮助用户找到具有确切标识符(如文件名)的所需图像。更通用的应用程序通常需要从整个网络边缘检索一组相似的图像。例如，具有人脸识别或行人重识别的大规模多摄像头监控系统，通过输入的照片识别给定人员在一段时间内的访问地点。现有的边缘数据共享系统只能找到精确的图像，而不能找到相似的图像。


技术实现要素：

4.基于此，有必要针对上述技术问题，提供一种能够实现高效的相似性数据共享的边缘存储系统中面向相似数据共享的索引方法、计算机设备和存储介质。
5.一种边缘存储系统中面向相似数据共享的索引方法，所述方法包括：
6.获取待搜索的边缘存储系统和终端用户的数据项；边缘存储系统中包括多个边缘服务器；
7.构建prophet架构，prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；虚拟平面的任意两个虚拟坐标之间的距离可以表示数据相似度或网络延迟；
8.根据边缘服务器的虚拟坐标，利用hnsw算法和德劳内三角网构造边缘服务器间的
转发图；
9.在虚拟平面中为每个边缘服务器构造索引结构，根据索引结构和转发图构建边缘服务器的转发表；
10.在线阶段给定待操作数据项，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除。
11.在其中一个实施例中，将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示，包括：
12.在每个边缘服务器上根据深度学习的方法对数据项进行特征提取，并随机采样一部分特征上传到中心服务器，得到数据项的特征空间；
13.根据分组修剪算法将特征空间划分为多个子区域，得到子区域集；
14.利用p稳态分布生成两个d维正交投影向量，使数据特征距离强相关于投影后的虚拟坐标距离，根据两个d维投影向量将子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标；
15.根据hnsw算法在子区域集的质心上构建用于子区域检索的数据结构；
16.根据子区域集的虚拟坐标，将虚拟平面上相邻的子区域聚合为一个超子区域，得到超子区域集；超子区域集中每个超子区域包含接近的特征数量；根据子区域集的虚拟坐标为超子区域集中的每个超子区域分配一个虚拟坐标，所有超子区域的虚拟坐标服从均匀分布；
17.利用多维尺度分析理论获取边缘服务器的虚拟坐标，根据边缘服务器的虚拟坐标将邻近的边缘服务器进行聚合，得到多个节点簇；节点簇中所有虚拟坐标的质心作为节点簇的虚拟坐标。
18.在其中一个实施例中，索引结构由虚拟坐标和索引范围组成；在虚拟平面中为每个边缘服务器构造索引结构，包括：
19.根据超子区域的虚拟坐标和节点簇的虚拟坐标进行计算，得到超子区域和虚拟平面中最近集群的距离；
20.利用超子区域和虚拟平面中最近集群的距离确定每个节点簇的全覆盖条件，预先设置最小覆盖半径，根据全覆盖条件和最小覆盖半径构建每个节点簇的索引范围为其中表示全覆盖条件，表示最小覆盖半径；
21.将每个节点簇的索引范围划分为多个面积相等的环，每个环表示一个边缘服务器的索引范围；环的内半径和外半径分别为
[0022][0023]
其中，φi∈gg，gg表示簇，φi表示第i个边缘服务器，mi是φi的特征容量，mj是φj的特征容量，j表示第j个边缘服务器
[0024]
在其中一个实施例中，转发表ti是一个列表，其中每一项都是一个元组由网络标识符idj，虚拟坐标索引范围和网络延
迟γij组成。
[0025]
在其中一个实施例中，根据两个d维投影向量将子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标，包括：
[0026]
根据两个d维投影向量将子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标为
[0027]cp
＝cp，p＝[p1，p2]～ψ
p
[0028][0029]
s.t.|corr(diｓt，dist
p
)|＞δc[0030]
|corr(p1，p2)|＜δ
p
[0031]
其中，和分别表示子区域中心成对批量采样b的投影前后距离，c表示子区域的中心，p表示两个d维投影向量的集合，p1，p2均表示d维投影向量，ψ
p
表示稳态分布，阈值δc和δ
p
均表示阈值。
[0032]
在其中一个实施例中，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图，包括：
[0033]
将邻接矩阵γ＝{γ
ij
|i，j＝1...|φ|}中网络延迟γ
ij
初始化为无穷大构建初始化转发图，在边缘服务器虚拟坐标上分别构建hnsw图和dt图并添加到初始化转发图中，如果边缘服务器φi在所述hnsw图或dt图中是边缘服务器φj的邻居，则赋值γ
ij
＝γ
ji
＝||e
i-ej||，其中||e
i-ej||表示边缘服务器φi和边缘服务器φj之间虚拟坐标的距离，得到边缘服务器间的转发图。
[0034]
在其中一个实施例中，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除，包括：
[0035]
在特征xr上进行特征m-投影，得到虚拟平面中最接近xr的超子区域
[0036]
基于最近邻的索引范围在每个超子区域上执行贪婪路由，对每个超子区域进行超子区域检查，给定一个超子区域h，返回一个元组其中是索引范围涵盖h的服务器集合，是转发表中离超子区域h最近的服务器；其中，超子区域检查表示从转发表t中查找索引范围覆盖超子区域h的服务器φ
*
并从转发表t中找到虚拟平面中最接近目标超子区域h的服务器φ
*
；
[0037]
初始化一个包含所有执行特征请求的服务器集合φ
*
，如果不是一个空集，将其中最靠近超子区域h的服务器添加到集合φ
*
中，如果是一个空集，将元组添加到用于超子区域检查的列表中；列表在接收每个查询时被初始化为一个空列表，在处理完所有超子区域后，将中的元组按属性分组，得到一个元组集合其中每个元组由一个服务器和它的超子区域组成为
[0038]
对中的每个服务器执行待操作类型为超子区域检查的请求转发，并对φ中待操
作类型为特征查询的请求转发进行数据搜索。
[0039]
在其中一个实施例中，从源服务器φs开始，采用简单的贪婪路由查找目标节点φ表示所有维护请求数据特征的目标节点集合；
[0040]
在特征xr上进行特征m-投影，得到特征xr所在的超子区域h及虚拟坐标h；
[0041]
对每个超子区域进行超子区域检查，当采用基于最近邻的索引范围时，返回虚拟坐标最接近数据虚拟坐标h的服务器φ
*
，如果φ
*
是源服务器φs，执行相应的特征操作；否则，执行请求转发到服务器φ
*
，其待操作类型为超子区域检查，直到φ
*
等于φs；
[0042]
当采用基于环覆盖的索引范围时，源服务器φs将请求转发到转发表中的超级节点服务器执行超子区域检查，在转发表中找到所有的目标节点，然后转发特征插入\删除请求，同时服务器将请求转发给所有其他超级节点以执行同样的对应操作；所有目标节点φd是所有超节点的并集。
[0043]
一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现以下步骤：
[0044]
获取待搜索的边缘存储系统和终端用户的数据项；边缘存储系统中包括多个边缘服务器；
[0045]
构建prophet架构，prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；虚拟平面的任意两个虚拟坐标之间的距离可以表示数据相似度或网络延迟；
[0046]
根据边缘服务器的虚拟坐标，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图；
[0047]
在虚拟平面中为每个边缘服务器构造索引结构，根据索引结构和转发图构建边缘服务器的转发表；
[0048]
在线阶段给定待操作数据项，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除。
[0049]
一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现以下步骤：
[0050]
获取待搜索的边缘存储系统和终端用户的数据项；边缘存储系统中包括多个边缘服务器；
[0051]
构建prophet架构，prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；虚拟平面的任意两个虚拟坐标之间的距离可以表示数据相似度或网络延迟；
[0052]
根据边缘服务器的虚拟坐标，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图；
[0053]
在虚拟平面中为每个边缘服务器构造索引结构，根据索引结构和转发图构建边缘服务器的转发表；
[0054]
在线阶段给定待操作数据项，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除。
[0055]
上述一种边缘存储系统中面向相似数据共享的索引方法、计算机设备和存储介
质，首先构建prophet架构，prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；虚拟平面的任意两个虚拟坐标之间的距离可以表示数据相似度或网络延迟；根据边缘服务器的虚拟坐标，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图；在虚拟平面中为每个边缘服务器构造索引结构，根据索引结构和转发图构建边缘服务器的转发表；在线阶段给定待操作数据项，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除。本技术通过对于每个边缘服务器，prophet构造一个索引结构，通过索引结构判断一个特征是否应该或已经存储在边缘服务器中。每个边缘服务器都有自己的索引结构，并在维护其索引范围内的特征。数据查询、插入请求和删除请求都可以定向到维护所需特征或其相似特征的服务器。在插入一个数据项时，它的特性可以被传递到多个目标服务器，以实现较低的查询延迟，离线阶段通过分析网络状态和特征空间为每个边缘服务器构造索引结构，在线阶段通过索引结构以简单而高效的方式响应数据请求，通过这种方式，本技术只需要访问少量几个边缘服务器来查找相似数据，而不是所有服务器，进而实现高效的相似性数据共享。
附图说明
[0056]
图1为一个实施例中一种边缘存储系统中面向相似数据共享的索引方法的流程示意图；
[0057]
图2为一个实施例中prophet架构的示意图；
[0058]
图3为一个实施例中数据投影过程示意图；
[0059]
图4为另一个实施例中邻近节点聚合示意图；
[0060]
图5为一个实施例中计算机设备的内部结构图。
具体实施方式
[0061]
为了使本技术的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本技术进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本技术，并不用于限定本技术。
[0062]
在一个实施例中，如图1所示，提供了一种边缘存储系统中面向相似数据共享的索引方法，包括以下步骤：
[0063]
步骤102，获取待搜索的边缘存储系统和终端用户的数据项；边缘存储系统中包括多个边缘服务器。
[0064]
步骤104，构建prophet架构，prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；虚拟平面的任意两个虚拟坐标之间的距离可以表示数据相似度或网络延迟。
[0065]
prophet用虚拟平面的坐标表示服务器索引结构，其中距离不仅反映数据相似度，还反映了服务器间的延迟。特征空间中的相似数据和网络空间中的相邻服务器应该表示为接近的虚拟坐标，以支配相邻的单元格。如图2所示，数据投影将特征空间划分为子区域，然后将其投影到虚拟平面上均匀分布的超子区域。边缘服务器投影通过服务器之间的成对延
迟来获得服务器的虚拟坐标。最终通过数据边缘关联确定索引结构。
[0066]
步骤106，根据边缘服务器的虚拟坐标，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图。
[0067]
hnsw算法用于高效子区域级检索，相似性边缘数据共享系统需要确保使用尽可能少的转发条目(即索引结构)进行交付。德劳内三角网(dt图)可以实现这一目标。但是dt需要更多的覆盖跳路由到目标服务器，因此本技术将hnsw和dt结合使用来构建转发关系，只通过覆盖跳和转发表项进行保证交付，提高了转发效率。
[0068]
步骤108，在虚拟平面中为每个边缘服务器构造索引结构，根据索引结构和转发图构建边缘服务器的转发表。
[0069]
步骤110，在线阶段给定待操作数据项，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除。
[0070]
离线阶段向每个服务器返回一个子区域级hnsw、一个超子区域投影模块和该服务器的转发表。数据的虚拟坐标由投影模块和hnsw获得。转发表指导在线阶段的请求转发。针对某一请求，源边缘服务器提取特征，通过hnsw获取与请求最接近的m个子区域，得到数据的虚拟坐标。接下来，通过检查转发表中的索引结构，源边缘服务器定位到下一跳，并向其发送网络标识符(mac/ip)、特征及虚拟坐标。请求将通过多跳到达目标服务器。它可以简单地通过转发表上贪婪路由来实现，即每一跳中，从转发表中选择距离目标虚拟坐标最近的服务器转发。目标服务器最后执行特征查询或插入，并将结果返回给源服务器进行聚合。
[0071]
上述边缘存储系统中面向相似数据共享的索引方法中，首先构建prophet架构，prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；虚拟平面的任意两个虚拟坐标之间的距离可以表示数据相似度或网络延迟；根据边缘服务器的虚拟坐标，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图；在虚拟平面中为每个边缘服务器构造索引结构，根据索引结构和转发图构建边缘服务器的转发表；在线阶段给定待操作数据项，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除。本技术通过对于每个边缘服务器，prophet构造一个索引结构，通过索引结构判断一个特征是否应该或已经存储在边缘服务器中。每个边缘服务器都有自己的索引结构，并在维护其索引范围内的特征。数据查询、插入请求和删除请求都可以定向到维护所需特征或其相似特征的服务器。在插入一个数据项时，它的特性可以被传递到多个目标服务器，以实现较低的查询延迟，离线阶段通过分析网络状态和特征空间为每个边缘服务器构造索引结构，在线阶段通过索引结构以简单而高效的方式响应数据请求，通过这种方式，本技术只需要访问少量几个边缘服务器来查找相似数据，而不是所有服务器，进而实现高效的相似性数据共享。
[0072]
在其中一个实施例中，将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示，包括：
[0073]
在每个边缘服务器上根据深度学习的方法对数据项进行特征提取，并随机采样一部分特征上传到中心服务器，得到数据项的特征空间；
[0074]
根据分组修剪算法将特征空间划分为多个子区域，得到子区域集；
[0075]
利用p稳态分布生成两个d维正交投影向量，使数据特征距离强相关于投影后的虚拟坐标距离，根据两个d维投影向量将子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标；
[0076]
根据hnsw算法在子区域集的质心上构建用于子区域检索的数据结构；
[0077]
根据子区域集的虚拟坐标，，将虚拟平面上相邻的子区域聚合为一个超子区域，得到超子区域集；超子区域集中每个超子区域包含接近的特征数量；根据子区域集的虚拟坐标为超子区域集中的每个超子区域分配一个虚拟坐标，所有超子区域的虚拟坐标服从均匀分布；
[0078]
利用多维尺度分析理论获取边缘服务器的虚拟坐标，根据边缘服务器的虚拟坐标将邻近的边缘服务器进行聚合，得到多个节点簇；节点簇中所有虚拟坐标的质心作为节点簇的虚拟坐标。
[0079]
在具体实施例中，离线阶段通过虚拟平面上的坐标实现数据边缘关联。第一个是将数据投影到虚拟平面如图3所示，其核心思想是确保相似数据投影后在虚拟平面上相邻。
[0080]
特征提取是多媒体检索的第一步，用来表示向量空间中的数据相似度。目前，为了获得更好的检索精度，人们提出了各种基于深度学习的方法。这里，我们假设将特征提取部署在边缘端，以获得更短的网络延迟、更轻的流量负载和更好的隐私性。与云端卸载延迟相比,边缘服务器能够以足够低的延迟有效地进行特征提取。
[0081]
收集一个特征子集(约10％)，将该特征空间划分为大量子区域，其中心为然后计算特征出现在每个子区域ci∈c中的概率wi。prophet引入了分组修剪算法进行区域提取，具有较高的精度和较低的内存和计算成本。
[0082]
在特征空间中相邻的子区域质心在投影后在虚拟平面中也应相邻。为此，利用p稳态分布ψ
p
生成两个d维投影向量p＝[p1，p2]，其中pi＝[a
1i
...a
di
]
t
。可以得到子区域c的虚拟坐标c
p
，如公式c
p
＝cp；p＝[p1；p2]～ψ
p
，对于两个子区域ci；cj∈c，a0||c
i-cj||
p
(a0～ψ
p
)和p.(c
i-cj)具有相同的分布。因此投影前的距离||c
i-cj||
p
与投影后的距离p.(c
i-cj)相关。概率分布ψ
p
在p＝1时为柯西分布，p＝2时为高斯分布。
[0083]
然而，随机投影向量不能保证投影前后距离的强相关性。我们通过如下公式定义的优化问题来解决这一问题
[0084][0085]
s.t.|corr(dist；dist
p
)|》δc[0086]
|corr(p1；p2)|《δ
p
[0087]
其中和是子区域中心成对批量采样的投影前后距离。该优化保持了投影后的特征相似度，使投影向量近似正交。阈值δc和δ
p
分别设置为0.05和0.75。该问题可用粒子群算法来解决。
[0088]
通过p稳态分布ψ
p
投影向量，投影坐标c
p
服从分布ψ
p
，如图3所示。但是，为确保负载均衡，数据应该被投影到均匀分布。此外，过多的子区域会影响查询效率，因为我们需要
检索与查询最近的m个子区域，并检查每个服务器的索引范围以进行目标定位。因此，我们将一些相邻的子区域聚合为一个超子区域，并以均匀分布为每个超子区域分配一个虚拟坐标。每个超子区域具有大约相等数量的负载平衡特性。如图3所示，我们首先将虚拟平面的x轴分割为个切片h
x
[i]是投影子区域c
p
的一个子集。对与所有子集h
x
，式的值大致相等，其中wi是子区域ci的权值。然后对每个切片h
x
，用同样的方法将其分成个切片，得到个超子区域虚拟坐标计算为其中ηi是均匀分布中的一个随机变量。
[0089]
为了获得给定特征的虚拟坐标，第一步是找到最近的m个子区域。这里我们采用hnsw算法，因为它在查询精度和效率上都具有前所未有的优势。它生成所有子区域质心的层次化小世界图，其中每个顶点的邻居个数具有恒定的上界。hnsw的查询是一个自顶向下的迭代过程，其复杂度为对数复杂度
[0090]
为了充分利用低延迟边缘计算，prophet需要只从附近的服务器获得准确的检索结果，而不访问远程服务器。关键的挑战是通过延迟矩阵分析所分配的虚拟坐标来反映服务器的网络延迟。
[0091]
本技术利用多维尺度分析理论来获得可以反映服务器网络延迟的虚拟坐标。给定延迟矩阵θ＝{θ
ij
|i，j＝1...|φ|}(θ
ij
是从服务器φi到服务器φj的延迟)，等式b＝ee
t
需要求解，其中e是|φ|个点(边缘服务器)的虚拟坐标矩阵，b＝{b
ij
|i，j＝1|φ|}是一个构造的目标矩阵，如公式
[0092][0093]
然后对矩阵b作为b＝qλq
t
进行特征值分解，得到边缘服务器的坐标为prophet选择e矩阵的前两列作为最终的虚拟坐标矩阵注意，ei∈e表示本文中的虚拟坐标。
[0094]
此外，可以通过稀疏的延迟矩阵确定服务器虚拟坐标。有时获取完整的延迟矩阵θ是不切实际的。因此，本技术提出了一种基于地标节点的针对稀疏延迟矩阵的服务器虚拟坐标构建方案。本技术得到地标服务器的延迟矩阵并得到它们的虚拟坐标然后计算向量δu，即方阵中所有列的平均值。对于每个非地标节点的服务器如果有它到所有地标节点的延迟向量δa，它的虚拟坐标e可以通过获得。
[0095]
prophet将邻近的边缘服务器聚合成一个簇，以在增强负载平衡的同时避免不必要的冗余，如图4所示。一些服务器可以通过同一个交换机连接，因此在虚拟平面中有相邻的坐标。在节点聚合之前，与半径覆盖有很大的重叠，需要覆盖整个虚拟平面，导致不必要的冗余。如果将超子区域与最近的服务器相关联，一些服务器将不能很好地利用。聚合后，
相邻的服务器具有具有相同虚拟坐标的环形索引范围。这样可以避免不必要的冗余。定义一个无向图g＝{g
ij
|i，j＝1...|φ|}，其中g
ij
＝1表示服务器φi与φj相邻。给定一个服务器虚拟坐标的距离矩阵f＝{f
ij
|i，j＝1...|φ|}，其中，f
ij
＝||e
i-ej||，如果f
ij
《α(α是一个预定义的阈值)，在无向图g中添加一个从i到j的链接。然后，从每个顶点g∈g开始执行广度优先搜索(bfs)，并将所有经过的顶点从g移动到一个节点簇gg。完成后，得到一些节点簇，表示为集合并计算节点簇gg的质心作为gg聚合后的虚拟坐标。
[0096]
在其中一个实施例中，索引结构由虚拟坐标和索引范围组成；在虚拟平面中为每个边缘服务器构造索引结构，包括：
[0097]
根据超子区域的虚拟坐标和节点簇的虚拟坐标进行计算，得到超子区域和虚拟平面中最近集群的距离；
[0098]
利用超子区域和虚拟平面中最近集群的距离确定每个节点簇的全覆盖条件，预先设置最小覆盖半径，根据全覆盖条件和最小覆盖半径构建每个节点簇的索引范围为其中表示全覆盖条件，表示最小覆盖半径；
[0099]
将每个节点簇的索引范围划分为多个面积相等的环，每个环表示一个边缘服务器的索引范围；环的内半径和外半径分别为
[0100][0101]
其中，φi∈gg，gg表示簇，φi表示第i个边缘服务器，mi是φi的特征容量，mj是φj的特征容量，j表示第j个边缘服务器
[0102]
在具体实施例中，prophet通过虚拟坐标将数据和服务器关联起来。首先，综合考虑延迟、冗余和负载平衡等因素，来确定每个服务器的索引范围，虚拟平面的覆盖面积。本技术提出了两个方法：基于加权最近邻的索引范围和基于环覆盖的索引范围。基于加权最近邻的索引范围将数据特征分配到加权虚拟距离最近的服务器，以实现最小冗余。但是，服务器的虚拟坐标可能不服从均匀分布，导致负载不平衡。通过基于环覆盖的索引范围，每个服务器φi维护一个以其虚拟坐标ei为中心的环状区域作为φi的索引范围，其中分别是环的内半径和外半径。必须确保每个超子区域至少可以被一个索引范围覆盖。因此，首先需要计算每个节点(或节点簇)的全覆盖条件。对于每个超子区域h，计算即h与虚拟平面中最近集群的距离，其中是集群的质心。这样，每个簇是离超子区域子集最近的，gg的全覆盖条件为我们定义了最小覆盖半径以利用更多的服务器资源获得更高的查询效率。因此gg的索引范围是其中mi是φi的特征容量，β是一个规范化因子。然后，对于每个簇gg，将其索引范围划分为多个面积相等的环。每个环表示服务器φi∈gg的索引范围，内半径和外半径为
[0103][0104]
最后每个边缘服务器根据自身的虚拟坐标和索引范围确认自身的索引结构。在其中一个实施例中，转发表ti是一个列表，其中每一项都是一个元组由网络标识符idj，虚拟坐标索引范围和网络延迟γ
ij
组成。
[0105]
在具体实施例中，根据索引结构和转发图，prophet为每个服务器φi构造转发表ti。转发表ti是一个列表，其中每一项都是一个元组由网络标识符idj，虚拟坐标索引范围和网络延迟γ
ij
组成。对于每个服务器φi，首先添加一个元组然后，如果对于任意服务器φj∈φ有γ
ij
《max，则在ti中添加一个元组对于所有服务器执行相同的操作，最终完成转发表构建。
[0106]
边缘数据共享系统应该能够适应系统运行时数据和服务器节点的动态性。其中，对于数据分布的动态性，可以部分地微调索引范围，利用空闲服务器来分担工作负载。为了实现动态服务器节点接入，可以通过地标节点计算新加入服务器的虚拟坐标，然后通过德劳内三角网的随机增量构建算法或hnsw的数据插入算法来更新转发表。此外，对于动态节点移除，空闲邻居节点可以临时承担被移除节点的任务。
[0107]
在其中一个实施例中，根据两个d维投影向量将子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标，包括：
[0108]
根据两个d维投影向量将子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标为
[0109]cp
＝cp，p＝[p1，p2]～ψ
p
[0110][0111]
s.t.|corr(dist，distp)|＞δc[0112]
|corr(p1，p2)|＜δ
p
[0113]
其中，和分别表示子区域中心成对批量采样b的投影前后距离，c表示子区域的中心，p表示两个d维投影向量的集合，p1，p2均表示d维投影向量，ψ
p
表示稳态分布，阈值δc和δ
p
均表示阈值。
[0114]
在其中一个实施例中，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图，包括：
[0115]
将邻接矩阵γ＝{γ
ij
|i，j＝1...|φ|}中网络延迟γ
ij
初始化为无穷大构建初始化转发图，在边缘服务器虚拟坐标上分别构建hnsw图和dt图并添加到初始化转发图中，如果边缘服务器φi在所述hnsw图或dt图中是边缘服务器φj的邻居，则赋值γ
ij
＝γ
ji
＝||ei-ej||，其中||e
i-ej||表示边缘服务器φi和边缘服务器φj之间虚拟坐标的距离，得到边缘服务器间的转发图
[0116]
在具体实施例中，由于在所有|φ|个服务器之间的索引同步太复杂用一个服务器来维护所有服务器的索引结构是不切实际的。此外，数据插入需要找到索引范围覆盖请求的所有目标服务器，而数据查询需要几个附近的服务器来覆盖几乎所有相似的功能。因此，本技术将hnsw和德劳内三角网(delaunay triangulation，dt)结合起来，构造服务器间的转发图，保证了路由长度短，转发条目少的情况下发送。将转发图表示为邻接矩阵γ＝{γ
ij
|i，j＝1...|φ|}，其中γ
ij
初始化为一个足够大的常数。如果希望服务器φi的转发表保持服务器φj的索引结构，则将γ
ij
赋值为它们之间虚坐标的距离||e
i-ej||。由于hnsw的目标定位覆盖跳低，在服务器虚拟坐标上用hnsw构造基本转发图。如果服务器φi是hnsw图中φj的邻居，则赋值γ
ij
＝γ
ji
＝|ei－ej||。由于hnsw在理论上不能保证交付，以同样的方式在转发图γ中添加一个dt图。此外可以将少量服务器分配为超级节点。每个普通节点维护至少一个超级节点的索引结构，而每个超级节点维护所有其他超级节点和指向它的普通节点的索引结构。
[0117]
在其中一个实施例中，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除，包括：
[0118]
在特征xr上进行特征m-投影，得到虚拟平面中最接近xr的超子区域
[0119]
基于最近邻的索引范围在每个超子区域上执行贪婪路由，对每个超子区域进行超子区域检查，给定一个超子区域h，返回一个元组其中是索引范围涵盖h的服务器集合，是转发表中离超子区域h最近的服务器；其中，超子区域检查表示从转发表t中查找索引范围覆盖超子区域h的服务器φ
*
并从转发表t中找到虚拟平面中最接近目标超子区域h的服务器φ
*
；
[0120]
初始化一个包含所有执行特征请求的服务器集合φ
*
，如果不是一个空集，将其中最靠近超子区域h的服务器添加到集合φ
*
中，如果是一个空集，将元组添加到用于超子区域检查的列表中；列表在接收每个查询时被初始化为一个空列表，在处理完所有超子区域后，将中的元组按属性分组，得到一个元组集合其中每个元组由一个服务器和它的超子区域组成为
[0121]
对中的每个服务器执行待操作类型为超子区域检查的请求转发，并对φ中待操作类型为特征查询的请求转发进行数据搜索。
[0122]
在其中一个实施例中，从源服务器φs开始，采用简单的贪婪路由查找目标节点φ表示所有维护请求数据特征的目标节点集合；
[0123]
在特征xr上进行特征m-投影，得到特征xr所在的超子区域h及虚拟坐标h；
[0124]
对每个超子区域进行超子区域检查，当采用基于最近邻的索引范围时，返回虚拟坐标最接近数据虚拟坐标h的服务器φ
*
，如果φ
*
是源服务器φs，执行相应的特征操作；否则，执行请求转发到服务器φ
*
，其待操作类型为超子区域检查，直到φ
*
等于φs；
[0125]
当采用基于环覆盖的索引范围时，源服务器φs将请求转发到转发表中的超级节
点服务器执行超子区域检查，在转发表中找到所有的目标节点，然后转发特征插入\删除请求，同时服务器将请求转发给所有其他超级节点以执行同样的对应操作；所有目标节点φd是所有超节点的并集。
[0126]
在具体实施例中，特征m-投影是指无论是插入、删除还是查询数据，第一步都是提取数据特征并找到超子区域。为了获得一个特征的超子区域，需要通过子区域级hnsw检索m个最接近的子区域这一步的计算复杂度为计算投影坐标对于每个投影坐标在其x轴和y轴坐标上通过二分搜索找到其超子区域。最后，计算的所有m个超子区域的唯一集合特征m-投影的计算复杂度为
[0127]
超子区域检查是指给定转发表t和超子区域的虚拟坐标h，超子区域检查用于两个任务：i)从转发表t中查找索引范围覆盖超子区域h的服务器φ
*
；ii)从转发表t中找到虚拟平面中最接近目标超子区域h的服务器φ
*
。注意，当采用基于最近邻的索引时，这两个任务是相同的，即等价于查找服务器φ
*
。当采用基于环的索引范围时，需要遍历转发表t中的每一项，并根据选择满足覆盖条件的服务器子集其中是服务器的虚拟坐标，φ
t
是在转发表t中包含的服务器集合。然后，返回元组{φ
*
，φ
*
}。复杂度为其中|t|是转发表t的长度。
[0128]
请求转发用于将待操作类型和所需内容转发到其他服务器。待操作类型可以是超子区域检查或特征操作(包括插入、删除或查询)。如图2(prophet架构图)所示，超子区域检查(转发到经过节点)需要请求特征、源服务器id(发起请求的服务器id)和超子区域。特征操作(转发到目标节点)不需要超子区域。然后，接收请求的服务器作为操作类型执行相应的操作。
[0129]
特征操作(插入、删除、查询)是指目标服务器执行与待操作类型对应的特征操作。如图2(prophet架构图)所示，一旦源服务器插入或删除数据，目标服务器应该插入或删除对应的数据特征并返回一个ack到源服务器。对于特征查询，目标服务器应返回数据id以及查询到的top-k特征的距离。如果采用hnsw作为近似k近邻算法，则插入/查询复杂度为其中|χi|是服务器φi上存储特征的数目。
[0130]
在一个实施例中，为了利用边缘计算来减少查询延迟，prophet通过将一个子区域投影到多个超子区域来提供特征副本的支持。为每个超子区域h构建r(r》1)个副本以减少到目标服务器的平均虚拟距离。对于每个虚拟坐标为h＝(h
x
，hy)的超子区域h，其副本的虚拟坐标为
[0131][0132][0133]
在具体实施例中，如果支持特征副本，给定一个请求的特征特征m-投影操作将返回多个超子区域的副本。对于数据的插入或删除，需要处理每一个副本，而对于
数据查询，只需要处理离源边缘服务器最近的副本。
[0134]
应该理解的是，虽然图1的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图1中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。
[0135]
在一个实施例中，提供了一种计算机设备，该计算机设备可以是终端，其内部结构图可以如图5所示。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口、显示屏和输入装置。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统和计算机程序。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现一种边缘存储系统中面向相似数据共享的索引方法。该计算机设备的显示屏可以是液晶显示屏或者电子墨水显示屏，该计算机设备的输入装置可以是显示屏上覆盖的触摸层，也可以是计算机设备外壳上设置的按键、轨迹球或触控板，还可以是外接的键盘、触控板或鼠标等。
[0136]
本领域技术人员可以理解，图5中示出的结构，仅仅是与本技术方案相关的部分结构的框图，并不构成对本技术方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。
[0137]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本技术所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(rom)、可编程rom(prom)、电可编程rom(eprom)、电可擦除可编程rom(eeprom)或闪存。易失性存储器可包括随机存取存储器(ram)或者外部高速缓冲存储器。作为说明而非局限，ram以多种形式可得，诸如静态ram(sram)、动态ram(dram)、同步dram(sdram)、双数据率sdram(ddrsdram)、增强型sdram(esdram)、同步链路(synchlink)dram(sldram)、存储器总线(rambus)直接ram(rdram)、直接存储器总线动态ram(drdram)、以及存储器总线动态ram(rdram)等。
[0138]
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
[0139]
以上所述实施例仅表达了本技术的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。因此，本技术专利的保护范围应以所附权利要求为准。

技术特征：
1.一种边缘存储系统中面向相似数据共享的索引方法，其特征在于，所述方法包括：获取待搜索的边缘存储系统和终端用户的数据项；所述边缘存储系统中包括多个边缘服务器；构建prophet架构，所述prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；所述虚拟平面的任意两个虚拟坐标之间的距离可以表示数据相似度或网络延迟；根据边缘服务器的虚拟坐标，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图；在虚拟平面中为每个边缘服务器构造索引结构，根据所述索引结构和所述转发图构建边缘服务器的转发表；在线阶段给定待操作数据项，在所述待搜索的边缘存储系统根据所述转发表和虚拟坐标进行目标服务器定位以及对所述待操作数据项进行相似数据查询、数据插入和数据删除。2.根据权利要求1所述的方法，其特征在于，将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示，包括：在每个边缘服务器上根据深度学习的方法对所述数据项进行特征提取，并随机采样一部分特征上传到中心服务器，得到数据项的特征空间；根据分组修剪算法将所述特征空间划分为多个子区域，得到子区域集；利用p稳态分布生成两个d维正交投影向量，使数据特征距离强相关于投影后的虚拟坐标距离，根据所述两个d维投影向量将所述子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标；根据hnsw算法在子区域集的质心上构建用于子区域检索的数据结构；根据子区域集的虚拟坐标，，将虚拟平面上相邻的子区域聚合为一个超子区域，得到超子区域集；超子区域集中每个超子区域包含接近的特征数量；根据子区域集的虚拟坐标为超子区域集中的每个超子区域分配一个虚拟坐标，所有超子区域的虚拟坐标服从均匀分布；利用多维尺度分析理论获取边缘服务器的虚拟坐标，根据边缘服务器的虚拟坐标将邻近的边缘服务器进行聚合，得到多个节点簇；所述节点簇中所有虚拟坐标的质心作为节点簇的虚拟坐标。3.根据权利要求2所述的方法，其特征在于，所述索引结构由虚拟坐标和索引范围组成；在虚拟平面中为每个边缘服务器构造索引结构，包括：根据超子区域的虚拟坐标和节点簇的虚拟坐标进行计算，得到超子区域和虚拟平面中最近集群的距离；利用所述超子区域和虚拟平面中最近集群的距离确定每个节点簇的全覆盖条件，预先设置最小覆盖半径，根据所述全覆盖条件和最小覆盖半径构建每个节点簇的索引范围为其中表示全覆盖条件，表示最小覆盖半径；将所述每个节点簇的索引范围划分为多个面积相等的环，每个环表示一个边缘服务器的索引范围；所述环的内半径和外半径分别为
其中，φ
i
∈g
g
，g
g
表示簇，φ
i
表示第i个边缘服务器，m
i
是φ
i
的特征容量，m
j
是φ
j
的特征容量，j表示第j个边缘服务器。4.根据权利要求1所述的方法，其特征在于，所述转发表t
i
是一个列表，其中每一项都是一个元组由网络标识符id
j
，虚拟坐标索引范围和网络延迟γ
ij
组成。5.根据权利要求2所述的方法，其特征在于，根据所述两个d维投影向量将所述子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标，包括：根据所述两个d维投影向量将所述子区域集的质心强相关投影到虚拟平面上，得到子区域集的虚拟坐标为c
p
＝cp，p＝[p1，p2]～ψ
p
ｓ.t.|corr(dist，dist
p
)|＞δ
c
|corr(p1，p2)|＜δ
p
其中，和分别表示子区域中心成对批量采样的投影前后距离，c表示子区域的中心，p表示两个d维投影向量的集合，p1，p2均表示d维投影向量，ψ
p
表示稳态分布，阈值δ
c
和δ
p
均表示阈值。6.根据权利要求1所述的方法，其特征在于，利用hnsw算法和德劳内三角网构造边缘服务器间的转发图，包括：将邻接矩阵γ＝{γ
ij
|i；j＝1...|φ|}中网络延迟γ
ij
初始化为无穷大构建初始化转发图，在边缘服务器虚拟坐标上分别构建hnsw图和dt图并添加到所述初始化转发图中，如果边缘服务器φ
i
在所述hnsw图或dt图中是边缘服务器φ
j
的邻居，则赋值γ
ij
＝γ
ji
＝||e
i-e
j
||，其中||e
i-e
j
||表示边缘服务器φ
i
和边缘服务器φ
j
之间虚拟坐标的距离，得到边缘服务器间的转发图。7.根据权利要求6所述的方法，其特征在于，在所述待搜索的边缘存储系统根据所述转发表和虚拟坐标进行目标服务器定位以及对所述待操作数据项进行相似数据查询、数据插入和数据删除，包括：在特征x
r
上进行特征m-投影，得到虚拟平面中最接近x
r
的超子区域基于最近邻的索引范围在每个超子区域上执行贪婪路由，对每个超子区域进行超子区域检查，给定一个超子区域h，返回一个元组其中是索引范围涵盖h的服务器集合，是转发表中离超子区域h最近的服务器；其中，超子区域检查表示从转发表t中查找索引范围覆盖超子区域h的服务器φ
*
并从转发表t中找到虚拟平面中最接近目标超子区域h的服务器φ
*
；
初始化一个包含所有执行特征请求的服务器集合φ
*
，如果不是一个空集，将其中最靠近超子区域h的服务器添加到集合φ
*
中，如果是一个空集，将元组添加到用于超子区域检查的列表中；所述列表在接收每个查询时被初始化为一个空列表，在处理完所有超子区域后，将中的元组按属性分组，得到一个元组集合其中每个元组由一个服务器和它的超子区域组成为对中的每个服务器执行待操作类型为超子区域检查的请求转发，并对φ中待操作类型为特征查询的请求转发进行数据搜索。8.根据权利要求7所述的方法，其特征在于，所述方法还包括：从源服务器φ
s
开始，采用简单的贪婪路由查找目标节点φ表示所有维护请求数据特征的目标节点集合；在特征x
r
上进行特征m-投影，得到特征x
r
所在的超子区域h及虚拟坐标h；对每个超子区域进行超子区域检查，当采用基于最近邻的索引范围时，返回虚拟坐标最接近数据虚拟坐标h的服务器φ
*
，如果φ
*
是源服务器φ
s
，执行相应的特征操作；否则，执行请求转发到服务器φ
*
，其待操作类型为超子区域检查，直到φ
*
等于φ
s
；当采用基于环覆盖的索引范围时，源服务器φ
s
将请求转发到转发表中的超级节点服务器执行超子区域检查，在转发表中找到所有的目标节点，然后转发特征插入\删除请求，同时服务器将请求转发给所有其他超级节点以执行同样的对应操作；所有目标节点φ
d
是所有超节点的并集。9.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至8中任一项所述方法的步骤。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至8中任一项所述的方法的步骤。

技术总结
本申请涉及一种边缘存储系统中面向相似数据共享的索引方法。所述方法包括：构建Prophet架构，Prophet架构包括离线阶段和在线阶段，离线阶段通过分析网络状态和数据项的特征空间，分别将边缘服务器和数据项投影到虚拟平面以虚拟坐标的形式表示；根据边缘服务器的虚拟坐标，利用HNSW算法和德劳内三角网构造边缘服务器间的转发图；在虚拟平面中为每个边缘服务器构造索引结构，根据索引结构和转发图构建边缘服务器的转发表；在线阶段给定待操作数据项，在待搜索的边缘存储系统根据转发表和虚拟坐标进行目标服务器定位以及对待操作数据项进行相似数据查询、数据插入和数据删除。采用本方法能够实现高效的相似性数据共享。用本方法能够实现高效的相似性数据共享。用本方法能够实现高效的相似性数据共享。


技术研发人员：罗来龙 孙宇辰 郭得科 刘丽
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2023.03.07
技术公布日：2023/7/13