基于磁盘的数据图中三角形个数确定方法及相关设备

基于磁盘的数据图中三角形个数确定方法及相关设备
【技术领域】
1.本技术属于数据处理领域，特别涉及一种基于磁盘的数据图中三角形个数确定方法及相关设备。


背景技术：

2.随着互联网的产生和发展，各种移动应用运用而生，随之带来的是海量的数据。这些数据从人们的日常行为中产生，具有极高的分析价值。这些数据往往很容易通过图表的方式进行建模。将现实世界中的对象和关系抽象为点和边，从而建立关系图。这关系图进行高效的图结构分析具有重要的意义。
3.三角形计数，作为图结构分析算法的基础，是学者们长期以来的关注点。一旦对三角形计数算法做出改进，就能对大量的图分析算法提升。
4.互联网的快速发展，数据量呈几何级别增长，完全基于内存的三角形计数算法无法满足人们大数据量的需求，它们无法有效地处理存储在磁盘上的大图。


技术实现要素：

5.本技术提供一种基于磁盘的数据图中三角形个数确定方法及相关设备，可以减少在确定数据图中三角形个数时三角形的候选解，进而提高计算效率。
6.本技术第一方面提供了一种基于磁盘的数据图中三角形个数确定方法，包括：
7.确定目标数据图所对应的原始数据集；
8.根据所述原始数据集确定所述目标数据图中每个目标端点标识的度数；
9.根据所述每个目标端点标识的度数对所述目标数据图中的端点标识进行重排序，以得到所述目标数据图所对应的目标端点标识排序；
10.根据所述目标端点标识排序对所述原始数据集以及所述目标数据图进行调整，以得到目标数据集以及第一数据图；
11.根据所述目标数据集对所述第一数据图进行散列构建，以得到所述第一数据图所对应的散列结果；
12.确定所述第一数据图所对应的各个分区中每个分区的分区文件；
13.根据所述第一数据图所对应的散列结果以及所述每个分区的分区文件确定所述每个分区的分区伴随文件；
14.根据所述每个分区的分区伴随文件确定所述目标数据图中包含的三角形个数。
15.本技术第二方面提供了一种基于磁盘的数据图中三角形个数确定装置，包括：
16.第一确定单元，用于确定目标数据图所对应的原始数据集；
17.第二确定单元，用于根据所述原始数据集确定所述目标数据图中每个目标端点标识的度数；
18.重排序单元，用于根据所述每个目标端点标识的度数对所述目标数据图中的端点标识进行重排序，以得到所述目标数据图所对应的目标端点标识排序；
19.调整单元，用于根据所述目标端点标识排序对所述原始数据集以及所述目标数据图进行调整，以得到目标数据集以及第一数据图；
20.散列构建单元，用于根据所述目标数据集对所述第一数据图进行散列构建，以得到所述第一数据图所对应的散列结果；
21.第三确定单元，用于确定所述第一数据图所对应的各个分区中每个分区的分区文件；
22.第四确定单元，用于根据所述第一数据图所对应的散列结果以及所述每个分区的分区文件确定所述每个分区的分区伴随文件；
23.第五确定单元，用于根据所述每个分区的分区伴随文件确定所述目标数据图中包含的三角形个数。
24.本技术实施例第三方面提供了一种计算机设备，其包括至少一个连接的处理器、存储器和收发器，其中，所述存储器用于存储程序代码，所述处理器用于调用所述存储器中的程序代码来执行上述第一方面所述的基于磁盘的数据图中三角形个数确定方法的步骤。
25.本技术实施例第四方面提供了一种计算机存储介质，其包括指令，当其在计算机上运行时，使得计算机执行上述任一方面所述的基于磁盘的数据图中三角形个数确定方法的步骤。
26.相对于相关技术，本技术提供的实施例中，基于磁盘的数据图中三角形个数确定装置确定数据图中包含的三角形个数时，在三角形计数算法中提出了散列思想，对数据集进行散列构建，由此可以大大减少了在确定数据图中三角形个数时三角形的候选解，进而提高计算效率。
【附图说明】
27.图1为本技术实施例提供的三角形计数的示例图；
28.图2为本技术实施例提供的基于磁盘的数据图中三角形个数确定方法的流程示意图：
29.图3为本技术实施例提供的目标数据图的结构示意图；
30.图4为本技术实施例提供的第一数据图的结构示意图；
31.图5为本技术实施例提供的散列结构的确定方式的示意图；
32.图6为本技术实施例提供的分区伴随文件的示意图；
33.图7为本技术实施例提供的基于磁盘的数据图中三角形个数确定装置的虚拟结构示意图；
34.图8为本技术实施例提供的服务器的硬件结构示意图。
【具体实施方式】
35.下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本技术一部分实施例，而不是全部的实施例。
36.首先对本技术涉及的一些名词进行说明：
37.三角形：是一种完全图(即任意两点之间有边)。网络中三角形的数量可以反映网络的稠密程度和质量。
38.三角形计数：一条边的两个点如果有共同邻居，那么这三个点就构成了三角形结构，统计如此的三角形结构就完成了三角形计数算法，如图1所示，图1为本技术实施例提供的三角形计数的示例图。
39.下面从基于磁盘的数据图中三角形个数确定装置的角度对基于磁盘的数据图中三角形个数确定方法的进行说明，该基于磁盘的数据图中三角形个数确定装置可以为服务器，也可以为服务器中的服务单元，具体不做限定。
40.请结合参阅图2，图2为本技术实施例提供的基于磁盘的数据图中三角形个数确定方法的流程示意图，包括：
41.201、确定目标数据图所对应的原始数据集。
42.本实施例中，基于磁盘的数据图中三角形个数确定装置可以确定目标数据图所对应的原始数据集，如图3所示，图3为本技术实施例提供的目标数据图的结构示意图，该原始数据集格式为《src1,des1》,《src2,des2》,
…
,《srcn,desn》其中，src表示目标数据图中边的起点标识，des表示目标数据图中边的终点标识。
43.202、根据原始数据集确定目标数据图中每个目标端点标识的度数。
44.本实施例中，基于磁盘的数据图中三角形个数确定装置在确定原始数据集之后，可以根据原始数据集确定目标数据图中每个目标端点标识的度数，也即根据目标数据图中的边数据得到每个目标端点标识的度数，图3所示的目标数据图中各个端点标识id(此处以oldid对图3中各个端点标识进行说明)对应的度数如表1所示(表1中以端点标识id从小到大的方式排列为例进行说明)：
45.表1
46.oldiddegree(度数)122234445665758493104111
47.203、根据每个目标端点标识的度数对目标数据图中的端点标识进行重排序，以得到目标数据图所对应的目标端点标识排序。
48.本实施例中，基于磁盘的数据图中三角形个数确定装置在确定目标数据图中每个目标端点标识的度数之后，可以根据每个目标端点标识的度数对目标数据图中的端点标识进行重排序，以得到目标数据图所对应的目标端点标识排序。也即将目标数据图中的端点标识按度数由小到大的方式，将表1中的oldid进行重新编号，得到新端点标识与端点标识所对应的度数。若oldid的对应度数越小，那么其newid也对应的越小。根据表1中
idtodegree的数据，可以构建2个新的map——oldidtonewid和map——newidtodeg，其中，map——oldidtonewid如表2所示：
49.表2
50.oldidnewid12233546511697108794108111
51.map——newidtodeg如表3所示：
52.表3
53.newiddegree(度数)112232435464748495105116。
54.204、根据目标端点标识排序对原始数据图以及目标数据图进行调整，以得到目标数据集以及第一数据图。
55.本实施例中，基于磁盘的数据图中三角形个数确定装置在确定目标端点标识排序之后，可以根据该目标端点标识排序对原始数据图进行调整，进而得到目标数据集以及第一数据图，也即将《src,des》转化为《src
new
,des
new
》。如图4所示，图4为本技术实施例提供的第一数据图的结构示意图，为根据目标端点标识排序对图3所示的目标数据图进行调整后得到的数据图，该目标数据集为对该第一数据图所对应的数据集，该目标数据图如表4所示(为了描述简便，表4中并未将所有边的起点标识与终点标识进行展示，仅展示部分)：
56.表4
57.scr(起点标识)des(终点标识)1423
……
1011
58.需要说明的是，调整后的目标数据集中各条边的起点标识小于终点标识，也即src
new
《des
new
，并将《src
new
,des
new
》所对应的边重新写入data
new
中。
59.205、根据目标数据集对第一数据图进行散列构建，以得到第一数据图所对应的散列结果。
60.本实施例中，基于磁盘的数据图中三角形个数确定装置在得到目标数据集之后，可以根据该目标数据集对第一数据图中的每条边进行散列构建，以得到第一数据图所对应的散列结果，其中，该每条边包括一起点标识和一终点标识。下面进行具体说明：
61.确定第一数据图所对应的初始散列表；
62.确定目标起始点所对应的目标散列值，该目标起始点为目标数据集中的任意一个起始点；
63.根据目标散列值对初始散列表进行调整，以得到第一数据图所对应的散列结果。
64.下面结合图5对散列结果的确定进行说明，图5为本技术实施例提供的散列结果的确定方式的示意图：
65.基于磁盘的数据图中三角形个数确定装置首先从目标数据集中任意选择一条目标边，并通过如下公式确定目标起始点的目标散列值：
66.s＝(des+parmi*src)％bitsetsize；
67.其中，s为目标散列值，des为目标起始点所对应的终点标识，src为目标起始点的标识，parm1以及bitsetsize为预设值，i∈1,2,...,n，n为预设常数；以图4中的目标起始点的标识src＝10为例进行说明，终点标识des＝11,parm1＝3,parm2＝5,parm3＝7,bitset size＝9(此处parm以及bitset size的数值仅为举例说明，当然也还可以根据实际情况进行调整，具体不做限定),则bloomfilter中的(11+3*10)％9＝4,(11+5*10)％9＝6,(11+7*10)％9＝0,计算得到了4、6、0，该4、6、0即为目标起始点所对应的目标散列值；
68.并确定第一数据图所对应的初始散列表，该初始散列表中各个位数的散列值均为0；
69.最后根据目标散列值确定目标起始点在初始散列表中的目标位置，并根据该目标散列值调整目标位置的散列值，例如上述得到了目标散列值为4、6、0，0舍弃，目标散列值的目标位置为初始散列表中的第4位和第6位，同时由于4和6大于1，此时将初始散列表中的第4位的散列值调整为1，将初始散列表中的第6位的散列值调整为1，进而可以得到根据目标散列值调整后的初始散列表，依次类推可以根据目标数据集中的各个起始点对初始散列表进行调整，进而得到第一数据图所对应的散列结果。
70.需要说明的是，在进行散列构建时，可以在最大内存的限制下，计算出maxedgenum，也即在现有内存的条件下一次最多可以处理的边的数量。然后从data
new
中读取|maxedgenum|条边数据《src
new
,des
new
》到内存。将《src
new
,des
new
》数据记录到multimap《uint,uint》中。multimap《uint,uint》会根据各边的src
new
按从小到大的方式进行排序。将
排序好的||条边数据重新写到temp
file
中。之后针对各边的《rc,des》进行bloomfilter的散列构建。bloomfilter的散列构建如图5所示。完成data
new
的磁盘排序在磁盘上将生成data
sort
文件，data
sort
内的《rc,des》严格按src从小到大进行排序。
71.206、确定第一数据图所对应的各个分区中每个分区的分区文件。
72.本实施例中，基于磁盘的数据图中三角形个数确定装置为不同的边《rc,des》分配到哪个partition(分区)中做出了规定：
73.首先根据内存限制，计算出每个分区p能容纳的最大度数partitionsize。各个分区中的边《rc,des》必须满足∑des
deg
《partitionsize，也即边的度数之和要小于该分区能容纳的最大度数，才能保证各个分区p占用的内存不超过内存限制。
74.之后，基于磁盘的数据图中三角形个数确定装置可以确定每个分区所对应的最大度数以及第一数据图中每条边的度数，并根据每个分区所对应的最大度数以及每条边的度数确定每个分区的分区文件，每个分区中各条边的起点标识小于终点标识，且第一数据图中的各条边仅出现在各个分区中的一个分区内。
75.也即，根据建立分区界限的结果，可以知道根据内存限制，data
sort
可以分为|p|个区，同时可以确定每个分区p的des范围[
begin
,esid
end
]。
[0076]
读取data
sort
中的每条边《src,des》，并根据其des值，将其分配到对应的分区p中。在分配的同时构建srcpartitionlist。下面结合图4进行说明：
[0077]
假设有6个分区，每个分区的最大度数partitionsize为8，则可以得到每个分区对应的des范围如表5所示：
[0078]
表5
[0079]
分区iddes范围(终点标识id范围)11-425-637-849510611
[0080]
然后读取目标数据集，将目标数据中的各条边分配到不同的分区中，比如边《5,9》就根据des＝9分配到第4个分区，边《6.11》就分配到第6个分区。在分区的同时，建立srcpartitionlist(分区文件)，比如说《5,9》被分配到第4个分区，那么srcpartitionlist就记录了5这个点作为src点被分到了第四个分区，边《6，11》被分配到第6个分区，那么srcpartitionlist就记录了6这个点作为src点被分到了第六个分区。
[0081]
207、根据第一数据图所对应的散列结果以及每个分区的分区文件确定每个分区的分区伴随文件。
[0082]
本实施例中，基于磁盘的数据图中三角形个数确定装置可以确定目标起点标识所对应的第一邻接表，目标起点标识为目标数据集中的任意一个起点标识，目标邻接表为第一数据图中与目标起点标识相连的端点标识；并根据第一邻接表以及目标分区文件中的端点标识确定目标起点标识所对应的端点标识组合，目标分区文件为第一分区的分区文件，第一分区为所述每个分区中的任意一个分区；最后根据第一数据图所对应的散列结果对目
标起点标识所对应的端点标识组合进行测试，以得到每个分区的分区伴随文件。
[0083]
也即，从data
sort
中读取《src,des》，由于data
sort
中的《src,des》是按照src由小到大的方式进行排序的且只有src《des的边才会被记录到data
sort
中，所以id
t
作为src点的所有的边都会集中在一起，当所有id
t
作为src点的所有的边都被读取完成时，就能得到id
t
作为src点的邻接表adj
t_src
。
[0084]
之后，遍历所有的分区，在当前分区pi中，遍历adj
t_src
中的每一个元素,为了简化表述，下面将adj
t_src
简写为j，对j进行以下两个判断(规则)：
[0085]
若j在pi分区中曾经作为src点出现过，则将j加入j
list
；
[0086]
若j的j
id
满足j
id
∈pi′
s[desid
begin
,desid
end
]，则将j加入到ctripe的k中。这说明j在pi分区中曾经作为des点出现过。
[0087]
完成上述两个判断后，j
list
和k都已经构建完成。接下来利用bloomfilter对j
list
元素进行过滤。遍历j
list
的每一个元素j。每个j对k中的所有元素k分别进行bloomfilter测试。bloomfilter测试如下表示：
[0088]
针对单个元素k，如果存在《j,k》,j《kor《k,j》,k《j则应该所有的对应hash值位置都为1.若存在某个hash值位置不为1，则说明《j,k》,j《kor《k,j》,k《j不存在。
[0089]
针对所有的元素k。如果j对所有的元素k都不存在边，则说明《i,j,k》之间不可能存在三角形，则将j从j
list
中剔除
[0090]
完成上述的bloomfilter测试后，j
list
形成了j。ctripe的《i,j,k》都形成。将此ctripe加入到当前分区pi的companionfile中。
[0091]
当所有的id和分区都遍历完成时，各个分区的companionfile构建完成。
[0092]
为了便于理解，下面结合表6进行说明，表6显示了6个分区以及各个分区中包含的边的起点标识以及终点标识之间的对应关系：
[0093]
表6
[0094]
分区分区中包含边的起点标识以及终点标识1《1,4》《2,3》2《2,5》《3,6》《5,6》3《4,8》《7,8》4《5,9》《6,9》《7,9》5《4,10》《7,10》《8,10》《9,10》6《6,11》《7,11》《8,11》《9,11》《10,11》
[0095]
接下来以src＝7的情况为例建立companionfile
[0096]
当目标数据集读取到src＝7时，可以把起点标识为7的邻接表读出：neighbor(7)＝{8,9,10,11}；
[0097]
之后遍历各个分区，以遍历第5个分区为例进行说明，根据上述规则，当neighbor(7)遍历到8时，由于srcpartitionlist记录了8曾经作为src点被分到了5分区(《8,10》边)，所以把8加入到此时的j
list
中，同样的9也会加入到j
list
中，而neighbor(7)遍历到10时，由于10在5分区的desid范围内，所以10被加入到k中。此时的ctripe(端点标识组合)为《7,{8,9},{10}》。然后对《7,{8,9},{10}》做bloomfilter测试。bloomfilter测试就是利用在4.1.1.(3)中建立的bloomfilter散列，分别对《8,10》和《9,10》测试这两个边是否存在。由
于此时的ctripe为《7,{8,9},{10}》通过了bloomfilter测试，所以就把《7,{8,9},{10}》写入分区5的companionfile(分区伴随文件)中，如图6所示，图6为本技术实施例提供的分区伴随文件的示意图。
[0098]
208、根据每个分区的分区伴随文件确定目标数据图中包含的三角形个数。
[0099]
本实施例中，基于磁盘的数据图中三角形个数确定装置可以首先确定目标分区伴随文件中的起点标识以及终点标识，目标分区伴随文件为第二分区的分区伴随文件，第二分区为每个分区中的任意一个分区，并确定起点标识所对应的第二邻接表；将第二邻接表与终点标识进行交集计算，得到交集结果；最后根据交集结果确定目标数据图中包含的三角形个数。以步骤207中的例子进行说明，比如当读到分区伴随文件中的ctripe《7,{8,9},{10}》时，会遍历8和9，当遍历到8时，将8的邻接表neighbor(8)＝{4，7，10，11}与{10}做交集，得到{10},交集结果数量为1，即得到的三角形数量加一。当遍历到9时，将9的邻接表neighbor(9)＝{5，6，7，10，11}与{10}做交集，得到{10},交集结果数量为1，即得到的三角形数量再加一。如此类推，直到所有的companionfile的ctripe都遍历完成，进而得到目标数据图中包含的三角形个数。
[0100]
综上所述，可以看出，本技术提供的实施例中，基于磁盘的数据图中三角形个数确定装置确定数据图中包含的三角形个数时，在三角形计数算法中提出了散列思想，对数据集进行散列构建，由此可以大大减少了在确定数据图中三角形个数时三角形的候选解，进而提高计算效率。
[0101]
上面从基于磁盘的数据图中三角形个数确定方法对本技术进行说明，下面从基于磁盘的数据图中三角形个数确定装置的角度对本技术进行说明。
[0102]
请参阅图7，图7为本技术实施例提供的基于磁盘的数据图中三角形个数确定装置的虚拟结构示意图，该基于磁盘的数据图中三角形个数确定装置700包括：
[0103]
第一确定单元701，用于确定目标数据图所对应的原始数据集；
[0104]
第二确定单元702，用于根据所述原始数据集确定所述目标数据图中每个目标端点标识的度数；
[0105]
重排序单元703，用于根据所述每个目标端点标识的度数对所述目标数据图中的端点标识进行重排序，以得到所述目标数据图所对应的目标端点标识排序；
[0106]
调整单元704，用于根据所述目标端点标识排序对所述原始数据集以及所述目标数据图进行调整，以得到目标数据集以及第一数据图；
[0107]
散列构建单元705，用于根据所述目标数据集对所述第一数据图进行散列构建，以得到所述第一数据图所对应的散列结果；
[0108]
第三确定单元706，用于确定所述第一数据图所对应的各个分区中每个分区的分区文件；
[0109]
第四确定单元707，用于根据所述第一数据图所对应的散列结果以及所述每个分区的分区文件确定所述每个分区的分区伴随文件；
[0110]
第五确定单元708，用于根据所述每个分区的分区伴随文件确定所述目标数据图中包含的三角形个数。
[0111]
一种可能的设计中，所述散列构建单元705具体用于：
[0112]
确定所述第一数据图所对应的初始散列表；
[0113]
确定目标起始点所对应的目标散列值，所述目标起始点为所述目标数据集中的任意一个起始点；
[0114]
根据所述目标散列值对所述初始散列表进行调整，以得到所述第一数据图所对应的散列结果。
[0115]
一种可能的设计中，所述散列构建单元705确定所述目标起始点所对应的目标散列值包括：
[0116]
通过如下公式确定所述目标起始点所对应的目标散列值：
[0117]
s＝(des+parmi*src)％bitsetsize；
[0118]
其中，s为所述目标散列值，des为所述目标起始点所对应的终点标识，src为所述目标起始点的标识，parmi以及bitsetsize为预设值，i∈1,2,...,n，n为xxx；
[0119]
所述散列构建单元705确定根据所述目标散列值对所述初始散列表进行调整，以得到所述第一数据图所对应的散列结果包括：
[0120]
根据所述目标散列值确定所述目标边在所述初始散列表中的目标位置；
[0121]
根据所述目标散列值调整所述目标位置的散列值。
[0122]
一种可能的设计中，所述第三确定单元706具体用于：
[0123]
确定所述每个分区所对应的最大度数；
[0124]
确定所述第一数据图中每条边的度数；
[0125]
根据所述每个分区所对应的最大度数以及所述每条边的度数确定所述每个分区的分区文件，所述每个分区中各条边的起点标识小于终点标识，且所述第一数据图中的各条边仅出现在所述各个分区中的一个分区内。
[0126]
一种可能的设计中，所述第四确定单元707具体用于：
[0127]
确定目标起点标识所对应的第一邻接表，所述目标起点标识为所述目标数据集中的任意一个起点标识，所述目标邻接表为所述第一数据图中与所述目标起点标识相连的端点标识；
[0128]
根据所述第一邻接表以及目标分区文件中的端点标识确定所述目标起点标识所对应的端点标识组合，所述目标分区文件为第一分区的分区文件，所述第一分区为所述每个分区中的任意一个分区；
[0129]
根据所述第一数据图所对应的散列结果对所述目标起点标识所对应的端点标识组合进行测试，以得到所述每个分区的分区伴随文件。
[0130]
一种可能的设计中，所述第五确定单元708具体用于：
[0131]
确定目标分区伴随文件中的起点标识以及终点标识，所述目标分区伴随文件为第二分区的分区伴随文件，所述第二分区为每个分区中的任意一个分区；
[0132]
确定所述起点标识所对应的第二邻接表；
[0133]
将所述第二邻接表与所述终点标识进行交集计算，得到交集结果；
[0134]
根据所述交集结果确定所述目标数据图中包含的三角形个数。
[0135]
图8为本技术服务器的结构示意图，如图8所示，本实施例的服务器800包括至少一个处理器801，至少一个网络接口804或者其他用户接口803，存储器805，和至少一通信总线802。该服务器800可选的包含用户接口803，包括显示器，键盘或者点击设备。存储器805可能包含高速ram存储器，也可能还包括非不稳定的存储器(non-volatilememory)，例如至少
一个磁盘存储器。存储器805存储执行指令，当服务器800运行时，处理器801与存储器805之间通信，处理器801调用存储器805中存储的指令，以执行上述基于磁盘的数据图中三角形个数确定方法。操作系统806，包含各种程序，用于实现各种基础业务以及处理根据硬件的任务。
[0136]
本技术实施例提供的服务器，可以执行上述的基于磁盘的数据图中三角形个数确定方法的实施例的技术方案，其实现原理和技术效果类似，此处不再赘述。
[0137]
本技术实施例还提供了一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被计算机执行时实现上述任一方法实施例中与基于磁盘的数据图中三角形个数确定装置相关的方法流程。对应的，该计算机可以为上述基于磁盘的数据图中三角形个数确定装置。
[0138]
本技术实施例还提供了一种计算机程序或包括计算机程序的一种计算机程序产品，该计算机程序在某一计算机上执行时，将会使所述计算机实现上述任一方法实施例中与基于磁盘的数据图中三角形个数确定装置相关的方法流程。对应的，该计算机可以为上述的基于磁盘的数据图中三角形个数确定装置。
[0139]
在上述图2对应的实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。
[0140]
以上所述实施例仅用以说明本技术的技术方案，而非对其限制；尽管参照前述实施例对本技术进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本技术各实施例技术方案的范围。

技术特征：
1.一种基于磁盘的数据图中三角形个数确定方法，其特征在于，包括：确定目标数据图所对应的原始数据集；根据所述原始数据集确定所述目标数据图中每个目标端点标识的度数；根据所述每个目标端点标识的度数对所述目标数据图中的端点标识进行重排序，以得到所述目标数据图所对应的目标端点标识排序；根据所述目标端点标识排序对所述原始数据集以及所述目标数据图进行调整，以得到目标数据集以及第一数据图；根据所述目标数据集对所述第一数据图进行散列构建，以得到所述第一数据图所对应的散列结果；确定所述第一数据图所对应的各个分区中每个分区的分区文件；根据所述第一数据图所对应的散列结果以及所述每个分区的分区文件确定所述每个分区的分区伴随文件；根据所述每个分区的分区伴随文件确定所述目标数据图中包含的三角形个数。2.根据权利要求1所述的方法，其特征在于，所述根据所述目标数据集对所述第一数据图进行散列构建，以得到所述第一数据图所对应的散列结果包括：确定所述第一数据图所对应的初始散列表；确定目标起始点所对应的目标散列值，所述目标起始点为所述目标数据集中的任意一个起始点；根据所述目标散列值对所述初始散列表进行调整，以得到所述第一数据图所对应的散列结果。3.根据权利要求2所述的方法，其特征在于，所述确定所述目标起始点所对应的目标散列值包括：通过如下公式确定所述目标起始点所对应的目标散列值：s＝(des+parm
i
*src)％bitsetsize；其中，s为所述目标散列值，des为所述目标起始点所对应的终点标识，src为所述目标起始点的标识，parm
i
以及bitsetsize为预设值，i∈1,2,...,n，n为预设常数；所述根据所述目标散列值对所述初始散列表进行调整，以得到所述第一数据图所对应的散列结果包括：根据所述目标散列值确定所述目标边在所述初始散列表中的目标位置；根据所述目标散列值调整所述目标位置的散列值。4.根据权利要求1所述的方法，其特征在于，所述确定所述第一数据图所对应的各个分区中每个分区的分区文件包括：确定所述每个分区所对应的最大度数；确定所述第一数据图中每条边的度数；根据所述每个分区所对应的最大度数以及所述每条边的度数确定所述每个分区的分区文件，所述每个分区中各条边的起点标识小于终点标识，且所述第一数据图中的各条边仅出现在所述各个分区中的一个分区内。5.根据权利要求1所述的方法，其特征在于，所述根据所述第一数据图所对应的散列结果以及所述每个分区的分区文件确定所述每个分区的分区伴随文件包括：
确定目标起点标识所对应的第一邻接表，所述目标起点标识为所述目标数据集中的任意一个起点标识，所述目标邻接表为所述第一数据图中与所述目标起点标识相连的端点标识；根据所述第一邻接表以及目标分区文件中的端点标识确定所述目标起点标识所对应的端点标识组合，所述目标分区文件为第一分区的分区文件，所述第一分区为所述每个分区中的任意一个分区；根据所述第一数据图所对应的散列结果对所述目标起点标识所对应的端点标识组合进行测试，以得到所述每个分区的分区伴随文件。6.根据权利要求1所述的方法，其特征在于，所述根据所述每个分区的分区伴随文件确定所述目标数据图中包含的三角形个数包括：确定目标分区伴随文件中的起点标识以及终点标识，所述目标分区伴随文件为第二分区的分区伴随文件，所述第二分区为每个分区中的任意一个分区；确定所述起点标识所对应的第二邻接表；将所述第二邻接表与所述终点标识进行交集计算，得到交集结果；根据所述交集结果确定所述目标数据图中包含的三角形个数。7.一种基于磁盘的数据图中三角形个数确定装置，其特征在于，包括：第一确定单元，用于确定目标数据图所对应的原始数据集；第二确定单元，用于根据所述原始数据集确定所述目标数据图中每个目标端点标识的度数；重排序单元，用于根据所述每个目标端点标识的度数对所述目标数据图中的端点标识进行重排序，以得到所述目标数据图所对应的目标端点标识排序；调整单元，用于根据所述目标端点标识排序对所述原始数据集以及所述目标数据图进行调整，以得到目标数据集以及第一数据图；散列构建单元，用于根据所述目标数据集对所述第一数据图进行散列构建，以得到所述第一数据图所对应的散列结果；第三确定单元，用于确定所述第一数据图所对应的各个分区中每个分区的分区文件；第四确定单元，用于根据所述第一数据图所对应的散列结果以及所述每个分区的分区文件确定所述每个分区的分区伴随文件；第五确定单元，用于根据所述每个分区的分区伴随文件确定所述目标数据图中包含的三角形个数。8.根据权利要求1所述的装置，其特征在于，所述散列构建单元具体用于：确定所述第一数据图所对应的初始散列表；确定目标起始点所对应的目标散列值，所述目标起始点为所述目标数据集中的任意一个起始点；根据所述目标散列值对所述初始散列表进行调整，以得到所述第一数据图所对应的散列结果。9.一种计算机设备，其特征在于，包括：至少一个连接的处理器、存储器和收发器，其中，所述存储器用于存储程序代码，所述处理器用于调用所述存储器中的程序代码来执行权利要求1至6中任一项所述的基于磁盘
的数据图中三角形个数确定方法的步骤。10.一种计算机存储介质，其特征在于，包括：指令，当所述指令在计算机上运行时，使得计算机执行权利要求1至6中任一项所述的基于磁盘的数据图中三角形个数确定方法的步骤。

技术总结
本申请提供一种基于磁盘的数据图中三角形个数确定方法及相关设备，可以提高计算数据图中三角形个数时的计算效率。该方法包括：根据原始数据集确定目标数据图中每个目标端点标识的度数；根据每个目标端点标识的度数确定目标数据图所对应的目标端点标识排序；根据目标端点标识排序对原始数据集以及目标数据图进行调整，以得到目标数据集以及第一数据图；根据目标数据集对第一数据图进行散列构建，以得到第一数据图所对应的散列结果；确定第一数据图所对应的各个分区中每个分区的分区文件；根据第一数据图所对应的散列结果以及每个分区的分区文件确定每个分区的分区伴随文件；根据每个分区的分区伴随文件确定目标数据图中包含的三角形个数。包含的三角形个数。包含的三角形个数。


技术研发人员：李友焕 李梓铭 石沛凡 秦拯
受保护的技术使用者：湖南大学
技术研发日：2023.05.16
技术公布日：2023/8/14