Spark环境下基于频繁边的大规模单图采样算法

随着社交网络的流行,对其进行频繁子图挖掘的需求越来越强烈.大数据时代的到来,社交网络规模不断扩大,频繁子图挖掘工作变得愈发困难.在实际应用中,往往并不需要精确地挖掘出频繁子图,采样的方法在保证一定准确率的前提下能够显著提高频繁子图挖掘的效率.现有采样算法大多是根据节点的度进行采样,不适用于频繁子图挖掘.提出了一种基于频繁边的采样算法DIMSARI(distributed Monte Carlo sampling algorithm based on random jump and graph induction),在蒙特卡罗算法的基础上增加了根据频繁边进行随机跳的操作,并对其结果进行了图感应操作,进一步增加了算法的准确性,并在理论上证明了该方法的无偏性.实验结果显示:使用DIMSARI算法采样后进行频繁子图挖掘,准确性比现有其他的采样算法有较大的提高,在不同的采样率下采样后的子图的节点度都保持更小的归一化均方偏差.     

FSMBUS：一种基于Spark的大规模频繁子图挖掘算法

随着社交网络用户数的快速增加,大规模单图上频繁子图挖掘的需求越来越强烈.单机算法对大规模图的运行效率较低,难以支撑支持度较低的频繁子图的挖掘;现有的分布式环境下单图的频繁子图挖掘算法不支持子图增长模式的挖掘,它们所使用的Hadoop框架也不适合运行迭代式算法.提出了一种基于Spark的大规模单图频繁子图挖掘算法FSMBUS,通过次优树构建并行计算的候选子图,在给定最小支持度时挖掘出所有的频繁子图,并利用非频繁检测和搜索顺序选择实现优化,还设计了一种名为Sorted-Greedy的轻量级数据划分方法.实验结果表明,FSMBUS的效率要比现有单图上最新的算法快一个数量级,并支持更低最小支持度阈值以及更大规模图数据的挖掘,同时FSMBUS比其Hadoop的移植版要快2~4倍.     

基于Spark的大规模网络结构发现算法

当今社会处于大数据时代,现实中的网络数据越来越多,其结构复杂、规模庞大,有效分析其结构对了解、应用其提供的信息具有重要作用。基于混合模型的网络结构发现算法可挖掘网络中的多类型聚类结构,但不能有效处理大规模网络。基于Graph X图计算模型,提出基于Spark的大规模网络的结构发现算法LNSES,从存储空间和运行时间两方面提升算法效率。为减少网络结构发现算法存储大规模网络邻接矩阵内存耗费量,LNSES算法将边、节点及节点静态属性值进行分布式存储,边分区记录节点连边,可作为索引进行节点间参数传递。为提高网络结构发现算法效率,边分区和节点分区进行拉链操作产生索引结构;更新参数时,节点根据索引找到边分区上对应的边,并行实现节点参数更新。在真实和人工大规模网络数据集上的实验结果表明:LNSES在运行时间和网络结构识别准确度方面都要优于同类网络结构发现算法,可以对大规模网络中的结构进行挖掘分析。     

基于信息熵的子图匹配算法

子图查询是指输入一个图数据库和查询子图,输出图数据库中包含查询子图的图集合,它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式,此类测算模式在图中点数和连接边数呈指数分布时,会在少数节点上花费较多时间遍历其邻节点,导致查询算法效率低下。根据信息熵在信息度量中的作用,将条件信息熵作为启发式匹配的依据,提出了基于信息熵的子图匹配算法。实验表明,基于信息熵的子图匹配算法具有更高的查询效率,且在指数分布的数据集上效果更明显。     

基于Spark的大规模机器翻译系统研究

为提高大规模机器翻译准确率和翻译效率,基于EM分布式训练方法,提出基于Spark的大规模机器翻译方法。首先,在机器翻译模型的基础上对并行化训练方法和机器翻译系统框架进行分析,然后提出EM分布式并行算法和框架,针对短语翻译模型和层次翻译模型训练的特点,利用单机多线程工具MGIZA++构建完整的词对齐训练方法对短语翻译模型进行训练;最后通过实验验证提出算法对翻译模型的应用效果。实验结果表明,采用Align＿on＿MGIZA模型后,短语翻译速度比Chaski模型快了2倍,翻译速度显著提升,训练时间更短,仅用了该算法可以适用于短语翻译模型的高效准确翻译,说明系统性能优越,更具有效性。     

基于图连通支配集的子图匹配优化算法

在子图匹配过程中,随着图规模不断增长,匹配时间呈现指数爆炸的趋势.对此,提出一种基于图连通支配集的子图匹配优化算法VF-SMDS.根据贪心算法构建查询图的最小连通支配子图;通过代价模型计算最小连通支配子图节点的匹配代价,构建最优k查询节点匹配序列;通过支配节点的结构特征缩小查询节点搜索空间范围,在数据图中遍历到满足要求...     

Spark环境下基于子图的异步迭代更新方法

全局同步计算模型简单易用,但是路障同步导致收敛速度变慢。以顶点为中心的异步迭代虽然提高了收敛速度,但在计算节点之间需要频繁发送信息。在Spark环境下提出一种基于子图的异步迭代更新方法。在子图之间建立异步消息通信连接后,子图能以异步方式发送数据块;通过多线程同步避免数据读写冲突,保证异步更新时顶点状态的一致性。在大规模样本数据集上分别从收敛结果、收敛速度和通信代价验证方法有效性。实验结果表明,与全局同步迭代相比,该方法有效提高了计算收敛速度。与顶点为中心的异步更新方式相比,该方法在收敛时间上略有增长,但是显著降低了通信开销。     

基于包含度的子图匹配方法

子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即：在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配（subgraph matching with inclusion degree,简称SMID）.该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树（DS-Tree）,以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法.     

大规模标签图中的动态Top-K兴趣子图查询

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性（NTF）索引和边特性（EF）索引的图拓扑结构特性（GTSF）索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。     

A subgraph matching algorithm based on subgraph index for knowledge graph

The problem of subgraph matching is one fundamental issue in graph search, which is NP-Complete problem. Recently, subgraph matching has become a popular research topic in the field of knowledge graph analysis, which has a wide range of applications including question answering and semantic search. In this paper, we study the problem of subgraph matching on knowledge graph. Specifically, given a query graph q and a data graph G, the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G. Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph. To accelerate subgraph matching on knowledge graph, we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph, called as F G q_T-Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph ( F G q_T), which reduces redundant calculations in advance. Another design is a multi-label weight matrix, which evaluates a near-optimal matching tree for minimizing the intermediate candidates. With the aid of these two key designs, all subgraph isomorphic mappings are quickly conducted only by traversing F G q_T. Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.     

基于邻域安全压缩的动态图增量子图匹配算法

针对目前最先进的增量子图匹配算法Symbi中的索引结构DCS中存在的信息冗余问题,提出了一种新的索引结构CDCS（compressed dynamic candidate space）,并提出了CDCS的更新算法INCCDCS来动态维护CDCS索引结构和匹配结果,最后提出了动态图的增量子图匹配算法CSymbi。该方法通过引入邻域信息约束,在构建和更新辅助结构的过程中过滤候选集,提高算法的求解效率。最后,在Netflow和LSBench数据集上进行验证,相较于现有方法,候选节点数量最高可以删减56%,候选边数量最高可以删减62%,有效缩减了计算空间并提高了算法的求解效率。     

基于RDF图结构切分的高效子图匹配方法

针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架（RDF）图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。     

Spark框架优化的大规模谱聚类并行算法

为解决谱聚类在大规模数据集上存在的计算耗时和无法聚类等性能瓶颈制约,提出了基于Spark技术的大规模数据集谱聚类的并行化算法。首先,通过单向循环迭代优化相似矩阵的构建,避免重复计算;然后,通过位置变换和标量乘法替换来优化Laplacian矩阵的构建与正规化,降低存储需求;最后,采用近似特征向量计算来进一步减少计算量。不同测试数据集上的实验结果表明：随着测试数据集的规模增加,所提算法的单向循环迭代和近似特征值计算的运行时间呈线性增长,增长缓慢,其近似特征向量计算与精确特征向量计算取得相近的聚类效果,并且算法在大规模数据集上表现出良好的可扩展性。在获得较好的谱聚类性能的基础上,改进算法提高了运行效率,有效缓解了谱聚类的计算耗时及无法聚类问题。     

基于SparkStreaming的海量GPS数据实时地图匹配算法

浮动车GPS数据作为交通信息处理的基础,随着被监控车辆数量的高速增长,产生了海量GPS数据,对地图匹配提出了高挑战,为了解决传统匹配方法难以满足匹配效率和精度的不足,提出一种针对于海量GPS数据的实时并行地图匹配算法,能够同时保证较高匹配精度和运算效率。构建一种面向实时数据流的高效、准确实时地图匹配算法,首先通过引入速度、方向综合权重因子对依赖历史轨迹的离线地图匹配算法进行重构,进而引入Spark Streaming分布式计算框架,实现地图匹配算法的实时、并行运算,大幅提升实时地图匹配效率。实验结果表明,该算法在复杂路段的匹配准确率较常规拓扑匹配算法提高10%以上,整体匹配准确率达到95%以上;在匹配效率方面,较同等数量的单机服务器可提高效率4倍左右。实验结果表明,该算法在由11台机器组成的计算集群上实现8 000万个GPS数据点的实时地图匹配,证明了该算法可以完成城市地区的实时车辆匹配。