面向分布式图计算的平衡图划分算法

关注分布式图计算和迭代计算处理方法选择,对计算机技术应用和改善计算机性能等方面具有现实意义。传统算法计算分布式图时,切割率最小化与负载均衡性方面无法实现协调控制,且极易出现NP组合优化等系列问题。因此,以平衡图划分算法为手段,解决分布式图计算问题,重点研究平衡系数、切割边规模。扰动次数一定的条件下,引入Metis,结合平衡图划分算法,进行试验对比分析。通过对比可以发现,该算法下的分布式图割边率计算准确性高于Metis,可以满足分布式图的实际计算需求,这说明平衡图划分算法具有实践应用价值。     

基于小波变换的分布式隐私保护聚类算法

针对现有隐私保护聚类算法无法满足效率与隐私之间较好折中的问题,提出一种基于安全多方计算(SMC)与数据扰动相结合的分布式隐私保护聚类算法。各数据方用小波变换实现数据压缩和信息隐藏,并用属性列的随机重排来防止数据重构可能产生的信息泄露。该算法仅使用压缩重排后的数据参与分布聚类计算,因此计算量和通信量小,算法效率高,而多重保护措施有效保护了隐私数据。因小波变换具有高保真性,所以聚类精度受小波变换的影响较小。理论分析和实验结果表明,所提算法安全高效,在处理高维数据时全局F测量值和执行效率优于基于Haar小波的离散余弦变换(DCT-H)算法,解决了效率与隐私之间的折中问题。     

基于欺负算法的改进选举算法

欺负算法产生大量通信信息,时间开销大,占用系统资源过高,严重影响了分布式OLAP系统的性能。针对该问题,提出一种基于欺负算法的改进算法。该算法采用一对一的方式直接向性能最优的节点发送选举消息,以降低选举过程中产生信息的通信量和选举时间开销;并通过循环选举保证选举出系统的最优节点担任系统协调者。实验结果表明,该改进算法有效地降低了消息通信量,减少了时间开销,能更好的应用于分布式OLAP系统。     

基于边权约束法实现接触问题多约束图剖分

为提高接触问题并行计算的效率,分析内力计算和接触计算过程的并行性,提出基于边权约束法构造接触多约束图的方法,对比和分析多约束图剖分算法和双重区域剖分算法的负载平衡和通信性能.数值实验表明,在典型二维模型中多约束图剖分算法的负载平衡性能略低于双重区域剖分算法,但仍可将负载不平衡度控制在较好的范围内,简化并行计算的通信过程,减少总通信量并降低动态通信量比例.     

DK-Means——分布式聚类算法K-Dmeans的改进

随着网络的广泛应用,大量的数据将分布存在.由于网络带宽、站点存储量等一系列限制,分布式聚类分析成为具有挑战性的研究课题.人们已经提出了若干分布式聚类方法,但这些方法效率低下.对分布式聚类算法k-Dmeans进行改进,提出了分布式聚类算法Dk-means. 该算法只传送各站点的聚簇信息,有效降低了分布式聚类过程中的数据通信量.理论分析和实验结果表明,算法Dk-means的效率优于k-Dmeans,并且可达到与k-means等效的聚类质量.     

基于广度优先遍历加权图生成的启发式图分区

图分区质量极大程度上影响着计算机之间的通信开销和负载平衡, 这对于大规模并行图计算的性能是至关重要的. 然而, 随着图数据规模的越来越大, 图分区算法的执行时间成了一个不可避免的问题. 因此, 研究如何优化图分区算法的执行效率是有必要的. 本文提出了一个基于广度优先遍历加权图生成的启发式图分割方法, 该方法在实现较低的通信代价和较好负载平衡的同时, 只引入了少量的预处理时间开销. 实验结果表明, 本文的划分方法减少了复制因子, 降低通信开销, 并且引入的时间开销较小.     

基于并行约束规划的最大团识别研究

为提高大数据平台下大规模图例的最大团问题求解效率,提出一种基于并行约束规划的最大团识别算法.通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图,并将其分配给Spark集群中的计算节点,每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解,实现最大团问题的并行化处理.引入时间预测模型,设计基于任务运行时间预测模型的并行图划分方法,从而有效解决计算节点的负载均衡问题.实验结果表明,与基于BMC图划分策略的最大团并行识别算法相比,该算法具有更高的求解效率,可取得近似线性的加速比.     

伪多跳中继分布式一致性算法

为了提高分布式一致性问题的收敛速度, 减少节点间的通信成本, 本文提出一种分布式一致性算法. 新算法采用单跳通信, 利用非邻接节点的前状态信息进行节点状态更新. 本文证明了在无向通信拓扑下新算法的一致性收敛, 并分析计算了新算法的通信量以及收敛速度的变化. 通过理论分析和仿真验证, 结果表明新算法具有收敛速度快, 通信方式简单, 通信量少, 存在通信延时情况下通信数据不容易丢失等优点.     

重叠网格CFD并行计算的通信优化研究

介绍了重叠网格并行计算主从对之间通信量最小化方法,通过迷路算法将主网格点进行分类,在保证计算正确的前提下将主从间通信量降至最小;在嵌套重叠情况下的通信时序控制方面,提出了重叠关系有向图避免通信等待和重复插值;实验结果表明该重叠网格通信优化处理方法能得到较理想的并行效率。     

分布式信息网数据库管理系统的动态数据划分研究

在分布式信息网数据库管理系统中,数据是否被合理划分会影响系统的负载均衡以及节点之间的通信开销。为此,提出一种基于查询的动态数据划分算法。根据历史查询信息挖掘数据之间潜在的关联性,将关联性较大的数据动态调整到同一个处理节点上,使查询在较少的节点上处理完成,减少不必要的通信开销。实验结果表明,在保证系统负载均衡的情况下,该算法可减小通信开销,加快查询速度,优化分布式环境的整体性能。     

知识图谱划分算法研究综述

知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,...     

挖掘不确定频繁子图的改进算法的研究

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。     

GSO:基于图神经网络的深度学习计算图子图替换优化框架

深度学习在各种实际应用中取得了巨大成功,如何有效提高各种复杂的深度学习模型在硬件设备上的执行效率是该领域重要的研究内容之一.深度学习框架通常将深度学习模型表达为由基础算子构成的计算图,为了提高计算图的执行效率,传统的深度学习系统通常基于一些专家设计的子图替换规则,采用启发式搜索算法来优化计算图.它们的不足主要有:1)搜...     

一种多到一子图同构检测方法

提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

层次序列索引的大规模动态标签图子图查询

标签图常用于智能交通网、生物信息网等新兴领域的建模。子图查询作为图数据分析的关键问题，引起了研究者的广泛关注。对现有子图查询算法的研究发现，随着图数据规模增大且频繁更新，传统子图查询算法普遍存在查询效率低，存储开销大，忽略顶点标签信息等问题。为此，提出了一种支持大规模动态标签图子图查询的层次序列索引（Dynamic Hierarchical Sequence，DHS），该索引提取数据图中带有顶点编号的层次拓扑序列关系以实现子图查询；针对图的动态变化，提出了更新点拓扑扩展式索引维护策略，仅从局部变化顶点及边开始进行增量式更新，大大降低了重建索引造成的巨大开销；提出了基于DHS索引的子图查询方法，仅需将查询图与数据图的层次序列进行匹配即可获得候选集，并在其上利用关系匹配策略获得最终查询结果。实验证明提出的方法在保证高效查询的同时降低了索引的创建及维护时间，提高了子图查询效率。     

NODAR: mining globally distributed substructures from a single labeled graph

Data mining in structured and semi-structured data focuses on frequent data values. However, in graph data mining, the focus is on common specific topologies. Graph mining, although its ubiquity, is a difficult task since it requires subgraph isomorphism which is known to be NP-complete. In order to effectively prune the search space and thereby save computational time, a graph mining algorithm requires that the support measure of a pattern to be no greater than that of its subpatterns. This property of the support measure is referred to in the literature as the down-closure, anti-monotonicity or admissibility. Unfortunately, when mining a single labeled graph, simply counting the occurrences of a graph pattern may not have the down-closure property. For this, most existing approaches mine frequent substructures in a set of labeled graphs (called also the transactional setting) and few efforts have been devoted to mining frequent globally distributed substructures in a single labeled graph. In this paper, we propose a graph mining algorithm, called NODAR(Non-Overlapping embeDding based grAph mineR), for computing common and globally distributed substructures in a single labeled graph. NODAR adopts the Depth-First Search (DFS) strategy and is based on the SMNOES (Size of Maximum Non Overlapping Embedding Set) as support measure. The core idea of NODAR is to automatically extract frequent subpatterns; and thus without frequency computation thanks to the down-closure property of SMNOES. By adopting this strategy in the computation of frequent substructures, NODAR reduces the number of subgraph isomorphism tests needed to compute pattern frequencies. Experimental results on monograph and transactional graph databases; and comparison with well-known probabilistic and exact algorithms; prove the efficacy of NODAR.     

Querying massive graph data: A compress and search approach

Querying graph data is a fundamental problem that witnesses an increasing interest especially for massive graph databases which come as a promising alternative to relational databases for big data modeling. In this paper, we study the problem of subgraph isomorphism search which consists to enumerate the embedding of a query graph in a data graph. The most known solutions of this NP-complete problem are backtracking-based and result in a high computational cost when we deal with massive graph databases. We address this problem and its challenges via graph compression with modular decomposition. In our approach, subgraph isomorphism search is performed on compressed graphs without decompressing them yielding substantial reduction of the search space and consequently a significant saving in processing time as well as in storage space for the graphs. We evaluated our algorithms on nine real-word datasets. The experimental results show that our approach is efficient and scalable.     

基于邻域的大规模图数据动态分割算法

随着图数据的规模日益增大,出现大量以动态图数据为基础的分布式处理需求,划分问题在动态图数据分布式处理领域尤为重要. 对大规模动态图数据上的划分问题进行研究,根据图结构性质及动态图特点,提出并实现基于邻域的动态图分割算法. 算法分为静态切分和动态调整两个阶段,其中基于割边算法整合现有最优化策略提出了大规模图数据的静态切割算法. 在优化后的静态切割算法的基础上,根据图数据的动态扩张的特性提出动态分割算法. 根据迁移顶点所达到的最小负载值进行顶点迁移,并在此基础上进行性能及割边控制优化操作. 最后,改进算法在各类图数据集上进行了验证,验证的结果显示在平衡度和割边等指标上优化后的算法效果显著,提高了划分的合理性,并且在保证割边不增加的情况下提高了图分割的平衡度.     

大规模时序图中持续性稠密子图搜索算法研究

时序图是一种边上带有时间戳的图结构,其中边上的时间戳表示该边出现时间,即图随时间变化不断变化.图数据中的稠密子图挖掘问题具有非常强烈的现实意义.目前,时序图中大多数现有的工作都集中在稠密子图检测问题,该问题目标是找到时序图中所有的目标子图.然而,当时序图的规模过大时,这一问题将变得极其复杂且收效甚微.旨在研究在时序图中...