(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201810540034.8
(22)申请日 2018.05.30
(71)申请人 深圳大学
地址 518060 广东省深圳市南山区南海大
道3688号
(72)发明人 毛睿 胡梓良 刘开南 陆敏华
陆克中 罗秋明 雷海军 蔡晔
王毅 廖好 周池
(74)专利代理机构 深圳市恒申知识产权事务所
(普通合伙) 44312
代理人 袁文英
(51)Int.Cl.
G06F 17/10(2006.01)
G06F 9/50(2006.01)
(54)发明名称基于度量空间的支撑点并行枚举方法及装置(57)摘要本发明公开了一种基于度量空间的支撑点并行枚举方法及装置，该方法包括：调用消息传递接口，将待计算数据分发到M个节点，每个节点分配到一份数据集；控制该M个节点分别调用分叉函数，在每个节点内创建N个子进程，并将节点对应的数据集分配至N个子进程，使得每个子进程分配到一份子数据集，且N等于每个节点包含的GPU的个数，控制各M个节点内创建的N个子进程运行，通过N个子进程一对一控制相应节点内的N个GPU，利用GPU遍历对应子进程的子数据集中的数据，进行支撑点的并行枚举，并保存枚举结果。通过上述方式，能够有效实现支撑点的并行枚举，有效缩短支撑点枚举所消耗的时间，及 提高数据计算的性能。权利要求书2页 说明书6页 附图1页CN 108804383 A 2018.11.13
C N 108804383
A
1.一种基于度量空间的支撑点并行枚举方法，其特征在于，所述方法包括：
调用消息传递接口，将待计算数据分发到M个节点，每个节点分配到一份数据集，其中，M为正整数；
控制所述M个节点调用分叉函数，在每个节点内创建N个子进程，并将节点对应的数据集分配至N个子进程，使得每个子进程分配到一份子数据集，所述N为正整数，其中，每个节点都包含N个图形处理器GPU；
控制各所述M个节点内创建的N个子进程运行，通过所述N个子进程一对一控制相应节点内的N个GPU，利用所述GPU遍历对应子进程的子数据集中的数据，进行支撑点的并行枚举，并保存枚举结果。
2.根据权利要求1所述的方法，其特征在于，所述控制所述M个节点内的N个子进程运行，通过所述N个子进程一对一控制相应节点内的N个GPU，利用所述GPU遍历对应子进程的子数据集中的数据，进行支撑点的并行枚举，保存枚举结果，包括：
控制节点内的子进程运行，通过所述子进程控制所述GPU对所述子进程对应的子数据集进行遍历，对于
遍历到的查询对象，基于预设的参考对象、查询半径及支撑点判断所述查询对象的三角不等性，得到所述查询对象的三角不等性判断结果；并由所述GPU根据所述查询对象的三角不等性判断结果，得到所述查询对象的枚举结果； 从所述M个节点的N个子进程获取所述待计算数据的枚举结果，并保存，其中，子进程接收其控制的GPU反馈的所述子进程对应的子数据集中各查询对象的枚举结果。
3.根据权利要求2所述的方法，其特征在于，利用以下三角不等性公式进行三角不等性判断：
|d(q,p)-d(p,x)|>r，d(q,p)+d(p,x))<＝r
其中，d()表示距离函数，q表示遍历到的查询对象，p表示支撑点、x表示参考对象，r表示查询半径。
4.根据权利要求3所述的方法，其特征在于，所述得到所述查询对象的三角不等性判断结果，包括：
当所述查询对象满足所述三角不等性公式的任意一个不等式时，确定所述查询对象的三角不等性判断结果为：可直接查询；
当所述查询对象不满足所述三角不等性的任意一个不等式时，确定所述查询对象的三角不等性判断结果为：不可直接查询；
当无法确定所述查询对象是否满足所述三角不等性公式中的任意一个不等式时，则确定所述查询对象的三角不等性判断结果为：无法确定。
5.根据权利要求4所述的方法，其特征在于，所述由所述GPU根据所述查询对象的三角不等性判断结果，得到所述查询对象的枚举结果，具体包括：
对于三角不等性判断结果为无法确定的查询对象，所述GPU对所述查询对象进行距离计算，并将所述查询对象的距离计算次数加1，将所述查询对象的最后的距离计算次数作为所述查询对象的枚举结果。
6.一种基于度量空间的支撑点并行枚举装置，其特征在于，所述装置包括：
调用分配模块，用于调用消息传递接口，将待计算数据分发到M个节点，每个节点分配到一份数据集，其中，M为正整数；
控制处理模块，用于控制所述M个节点调用分叉函数，在每个节点内创建N个子进程，并将节点对应的数据集分配至N个子进程，使得每个子进程分配到一份子数据集，所述N为正整数，其中，每个节点都包含N个图形处理器GPU；
遍历枚举模块，用于控制各所述M个节点内创建的N个子进程运行，通过所述N个子进程一对一控制相应节点内的N个GPU，利用所述GPU遍历对应子进程的子数据集中的数据，进行支撑点的并行枚举，并保
存枚举结果。
7.根据权利要求6所述的装置，其特征在于，所述遍历枚举模块包括：
控制判断模块，控制节点内的子进程运行，通过所述子进程控制所述GPU对所述子进程对应的子数据集进行遍历，对于遍历到的查询对象，基于预设的参考对象、查询半径及支撑点判断所述查询对象的三角不等性，得到所述查询对象的三角不等性判断结果；并由所述GPU根据所述查询对象的三角不等性判断结果，得到所述查询对象的枚举结果；
获取保存模块，用于从所述M个节点的N个子进程获取所述待计算数据的枚举结果，并保存，其中，子进程接收其控制的GPU反馈的所述子进程对应的子数据集中各查询对象的枚举结果。
8.根据权利要求7所述的装置，其特征在于，所述判断控制模块利用以下三角不等性公式进行三角不等性判断：
|d(q,p)-d(p,x)|>r，d(q,p)+d(p,x))<＝r
其中，d()表示距离函数，q表示遍历到的查询对象，p表示支撑点、x表示参考对象，r表示查询半径。
9.根据权利要求8所述的装置，其特征在于，所述判断控制模块得到的所述查询对象的三角不等性判断结果，包括：
当所述查询对象满足所述三角不等性公式的任意一个不等式时，确定所述查询对象的三角不等性判断结果为：可直接查询；
当所述查询对象不满足所述三角不等性的任意一个不等式时，确定所述查询对象的三角不等性判断结果为：不可直接查询；
当无法确定所述查询对象是否满足所述三角不等性公式中的任意一个不等式时，则确定所述查询对象的三角不等性判断结果为：无法确定。
10.根据权利要求7所述的装置，其特征在于，所述控制判断模块具体用于：
控制节点内的子进程运行，通过所述子进程控制所述GPU对所述子进程对应的子数据集进行遍历，对于遍历到的查询对象，基于预设的参考对象、查询半径及支撑点判断所述查询对象的三角不等性，得到所述查询对象的三角不等性判断结果；对于三角不等性判断结果为无法确定的查询对象，由GPU对所述查询对象进行距离计算，并将所述查询对象的距离计算次数加1，将所述查询对象的最后的距离计算次数作为所述查询对象的枚举结果。
基于度量空间的支撑点并行枚举方法及装置
技术领域
[0001]本发明涉及大数据挖掘领域，尤其涉及一种基于度量空间的支撑点并行枚举方法及装置。
背景技术
[0002]目前，已经有一些支撑点选取算法，但是不同算法间的性能差别往往不大，用复杂的数学工具以很高的构建计算代价得到的支撑点带来的索引性能提升往往相对较少。[0003]随着数据量增大，将会出现计算量呈指数级上升，计算时间过长的问题，将影响到整个领域的研究进度，因此，研究一种计算时间短的支撑点枚举方式是目前亟待解决的问题。
发明内容
[0004]本发明的主要目的在于提供一种基于度量空间的支撑点并行枚举方法，旨在解决现有技术中支撑点枚举方法存在计算时间长的技术问题。
[0005]为实现上述目的，本发明第一方面提供一种基于度量空间的支撑点并行枚举方法，包括：
[0006]调用消息传递接口，将待计算数据分发到M个节点，每个节点分配到一份数据集，其中，M为正整数；
[0007]控制所述M个节点调用分叉函数，在每个节点内创建N个子进程，并将节点对应的数据集分配至N
个子进程，使得每个子进程分配到一份子数据集，所述N为正整数，其中，每个节点都包含N个图形处理器GPU；
[0008]控制各所述M个节点内创建的N个子进程运行，通过所述N个子进程一对一控制相应节点内的N个GPU，利用所述GPU遍历对应子进程的子数据集中的数据，进行支撑点的并行枚举，并保存枚举结果。
[0009]为实现上述目的，本发明第二方面提供一种基于度量空间的支撑点并行枚举的装置，包括：
[0010]调用分配模块，用于调用消息传递接口，将待计算数据分发到M个节点，每个节点分配到一份数据集，其中，M为正整数；
[0011]控制处理模块，用于控制所述M个节点调用分叉函数，在每个节点内创建N个子进程，并将节点对应的数据集分配至N个子进程，使得每个子进程分配到一份子数据集，所述N 为正整数，其中，每个节点都包含N个图形处理器GPU；
[0012]遍历枚举模块，用于控制各所述M个节点内创建的N个子进程运行，通过所述N个子进程一对一控制相应节点内的N个GPU，利用所述GPU遍历对应子进程的子数据集中的数据，进行支撑点的并行枚举，并保存枚举结果。
[0013]本发明提供一种基于度量空间的支撑点并行枚举方法，包括：调用消息传递接口，将待计算数据
分发到M个节点，每个节点分配到一份数据集，其中，该M为正整数；控制该M个
节点分别调用分叉函数，在每个节点内创建N个子进程，并将节点对应的数据集分配至N个子进程，使得每个子进程分配到一份子数据集，该N为正整数，且等于每个节点包含的GPU的个数，并控制各M个节点内创建的N个子进程运行，通过N个子进程一对一控制相应节点内的N个GPU，利用GPU遍历对应子进程的子数据集中的数据，进行支撑点的并行枚举，并保存枚举结果。相对于现有技术，通过将调用消息传递接口的方式，将待计算数据分发至M个节点，并继续分配至节点的N个子进程中，使得N个子进程能够并行运算，能够有效实现支撑点的并行枚举，有效缩短支撑点枚举所消耗的时间，且进一步通过子进程调用GPU，由于GPU本身具有多线程运行，并行能力强的特点，基于GPU进行并行枚举，能够进一步缩短支撑点枚举所需要的时间，有效提高数据计算的性能。
附图说明
[0014]为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0015]图1为本发明实施例中基于度量空间的支撑点并行枚举方法的流程示意图；[0016]图2为本发明实施例中基于度量空间的支撑点并行枚举装置的结构示意图。
具体实施方式
[0017]为使得本发明的发明目的、特征、优点能够更加的明显和易懂，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而非全部实施例。基于本发明中的实施例，本领域技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。[0018]请参阅图1，为本发明实施例中基于度量空间的支撑点并行枚举方法的流程示意图，包括：
[0019]步骤101、调用消息传递接口，将待计算数据分发到M个节点，每个节点分配到一份数据集，其中，M为正整数；
[0020]度量空间(Metric Space)是一种覆盖范围很广的数据类型的抽象，度量空间在数学中是指一个集合，并且该集合中的任意元素之间的距离是可以定义的。度量空间最大的优势在于其高度的普遍适用性，用户只需要提供距离函数就可以进行数据相似性搜索。在度量空间中，一般是先出支撑点，然后将数据到支撑点的距离作为坐标，因此，支撑点的好坏对于度量空间的数据管理分析的性能发挥着关键性的影响，本发明实施例即是要解决支撑点枚举过程中存在的计算时间长的问题。
[0021]在本发明实施例中，将进行大规模集下的多节点并行初始化，具体的，调用消息传递接口(Message passing interface，MPI)，通过该MPI将待计算数据分发到M个节点，每个节点都分配到一份
数据集，且该数据集的大小为dataset/M个数据，dataset表示待计算数据，也可称为原始数据，其中，待计算数据中包含了多个查询对象。
[0022]步骤102、控制所述M个节点调用分叉函数，在每个节点内创建N个子进程，并将节点对应的数据集分配至N个子进程，使得每个子进程分配到一份子数据集，所述N为正整数，
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议