基于确定图的频繁子图挖掘技术概述

化学信息学、生物信息学、医学和社会科学等领域的科学研究的迅速发展积累了大量的图数据,如何从复杂和庞大的图数据中挖掘出有效信息成为数据挖掘领域的热点。通过介绍现阶段图数据挖掘技术的进展,特别是确定图挖掘技术中有代表性的频繁子图挖掘技术研究,讨论并预测了频繁子图挖掘研究的发展趋势。     

从不确定图中挖掘频繁子图模式

研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3～5个数量级,有很高的效率和可扩展性.     

基于路径的频繁子图挖掘算法研究

图挖掘是数据挖掘的一个重要研究方向,而图挖掘主要集中在图数据集内频繁子图的挖掘。频繁子图挖掘技术的关键是建立有效机制减少冗余候选子图,以便高效计算和处理所需的频繁子图。提出了一种基于路径的频繁子图挖掘算法,该算法首先找出所有频繁边从而挖掘出频繁单路径,然后通过组合、双射和操作扩展出较多的频繁路径,再通过连接操作产生所有频繁子图候选集。通过定理证明了该算法的正确性和完整性,从理论上分析了该算法时间复杂度低于现有的算法,最后进行了2个图数据集实验,在候选集产生的数量和时间性能2方面验证了算法的优越性。     

Apriori算法用于频繁子图挖掘的改进方法

AGM算法最早将Apriori思想应用到频繁子图挖掘中。AGM算法结构简单,以递归统计为基础,但面临庞大的图数据集时,由于存在子图同构的问题,在生成候选子图时容易产生很多冗余子图,使计算时间开销很大。基于AGM算法,针对候选子图生成这一环节对原算法进行改进,减少了冗余子图的生成,使改进后的算法在计算时间上具有高效性;测试了在不同最小支持度情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间,提高了频繁子图的挖掘效率。     

从图数据库中挖掘频繁跳跃模式

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.     

利用MapReduce平台实现高效并行的频繁子图挖掘

频繁子图挖掘是数据挖掘领域的一个重要问题,并且有着广泛的应用。在Hadoop平台上实现了一种基于MapReduce的高效频繁子图挖掘算法Cloud-GFSG（cloud-global frequent subgraph）。该算法基于Apriori思想,在扩展边生成新的子图时,使用已经挖掘出的k-1阶的频繁子图生成k阶的频繁子图。同时,检查是否存在待扩展生成的子图,设定生成的频繁子图表示规则,保证了频繁子图信息的唯一性。较同类算法相比,该算法在挖掘频繁子图时更具通用性,并且在扩展边时避免产生大量的复制图,从而使得算法的正确性得以保证,且运行效率显著提高。     

频繁子图挖掘算法研究

图像能表达丰富语义,但增加了数据结构的复杂性和感兴趣子结构的挖掘难度。综合应用图论知识和数据挖掘的各种技术,对图像进行规范化编码,通过连接和扩展操作产生所有候选子图,引用嵌入集概念,计算候选子图的支持度和频繁度。提出频繁子图挖掘算法FSubgraphM,能从图数据库中挖掘频繁导出子图。     

一种改进的频繁子图挖掘算法

在大量的图数据集合中实现目标图的精确匹配是一项相当耗时的任务,为了提高检索效率,频繁子图挖掘逐渐受到广泛的研究。使用频繁子图挖掘可以去除那些与目标图极不相似的图,这样就减小了图的数据集合,从而使目标图检索变得更为快速。FFSM算法虽是一种较为有效的频繁子图挖掘算法,但在应用中存在占用大量存储空间的缺点。本文基于FFSM算法在数据预处理的基础上,将Recomputed Embedding技术整合于FFSM算法,利用改进后的算法建立索引分类。最后将新算法应用于化学虚拟合成系统的数据处理上,实验结果证明相对于FFSM算法其获得目标化合物的速度得到了显著提高。     

一种频繁子图挖掘算法

为减少频繁子图规范化检测的时间复杂度,对规范化邻接矩阵的相关性质进行分析。给出相关定理并证明其正确性,从而减少冗余候选子图的产生。在此基础上,提出一种频繁子图挖掘算法——FSM_CAM。实验结果证明,与现有频繁子图挖掘算法FSubGraphM相比,FSM_CAM算法的效率较高。     

基于联合意义度量的Top-K图模式挖掘

提出了一个新的研究问题:如何挖掘Top-K图模式,联合起来使某个意义度量最大化.利用信息论的概念,给出了两个具体问题的定义MES和MIGS,并证明它们是NP-难.提出了两个高效算法Greedy-TopK和Clus-ter-TopK.Greedy-TopK先产生频繁子图,然后按增量贪心方式选择K个图模式.Cluster-TopK先挖掘频繁子图的一个代表模式集合,然后从代表模式中按增量贪心方式选择K个图模式.当意义度量满足submodular性质时,Greedy-TopK能提供近似比保证.Cluster-TopK没有近似比保证,但比Greedy-TopK更高效.实验结果显示,在结果可用性方面,文中提出的Top-K挖掘优于传统的Top-K挖掘.Cluster-TopK比Greedy-TopK快至少一个数量级.而且,在质量和可用性方面,Cluster-TopK的挖掘结果非常类似于Greedy-TopK的挖掘结果.     

基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.     

GC-MCR:有向图约束指导的并发缺陷检测方法

约束求解应用到程序分析的多个领域,在并发程序分析方面也得到了深入的应用.并发程序随着多核处理器的快速发展而得到广泛使用,然而并发缺陷对并发程序的安全性和可靠性造成了严重的影响,因此,针对并发缺陷的检测尤为重要.并发程序线程运行的不确定性导致的线程交织爆炸问题,给并发缺陷的检测带来了一定挑战.已有并发缺陷检测算法通过约减无效线程交织,以降低在并发程序状态空间内的探索开销.比如,最大因果模型算法把并发程序状态空间的探索问题转换成约束求解问题.然而,其在约束构建过程中会产生大量冗余和冲突的约束,大幅度增加了约束求解的时间以及约束求解器的调用次数,降低了并发程序状态空间的探索效率.针对上述问题,提出了一种有向图约束指导的并发缺陷检测方法 GC-MCR (directed graph constraint-guided maximal causalityreduction).该方法旨在通过使用有向图对约束进行过滤和约减,从而提高约束求解速度,并进一步提高并发程序状态空间的探索效率.实验结果表明:GC-MCR方法构建的有向图可以有效优化约束的表达式,从而提高约束求解器的求解速度并减少求解器的调用次...     

GC-MCR: Directed Graph Constraint-guided Concurrent Bug Detection Method

Constraint solving has been applied to many domains of program analysis and is further used in concurrent program analysis. Concurrent programs have been widely used with the rapid development of multi-core processors. However, concurrent bugs threaten the security and reliability of concurrent programs, and thus it is of great importance to detect concurrent bugs. The explosion of thread interleaving caused by the uncertainty of the execution of concurrent program threads brings some challenges to the detection of concurrent bugs. Existing concurrent defect detection algorithms reduce the exploration cost in the state space of concurrent programs by reducing invalid thread interleaving. For example, the maximal causal model algorithm transforms the state space exploration problem of concurrent programs into a constraint solving problem. However, it will produce a large number of redundant and conflicting constraints during constraint construction, which greatly prolongs the time of constraint solving, increases the number of constraint solver calls, and reduces the exploration efficiency of concurrent program state space. Thus, this study proposes a directed graph constraint-guided maximal causality reduction method, called GC-MCR. This method aims to improve the speed of constraint solving and the efficiency of the state space exploration of concurrent programs by filtering and reducing constraints using directed graphs. The experimental results show that the GC-MCR method can effectively optimize the expression of constraints, so as to improve the solving speed of the constraint solver and reduce the number of solver calls. Compared with the existing J-MCR method, GC-MCR can significantly improve the detection efficiency of concurrent program bugs without reducing the detection ability of concurrent bugs, and the test time on 38 groups of concurrent test programs widely used by existing research methods can be reduced by 34.01% on average.     

二分类图上的非冗余协同图模式挖掘算法

图模式广泛应用于构建高效图分类模型的特征空间识别．协同图模式是一种内部节点高度相关的图结构,与普通图模式相比,协同图模式具有更高的区分能力,从而更加适用于分类模型的特征选择．文中研究了从二分类图中挖掘非冗余协同图模式的问题,通过限制协同图模式的区分能力远远高于其所有子图模式的非冗余性质,大幅度减少了挖掘结果的数量,同时保留了具有强区分能力的协同图模式．由于协同图模式理论上必须检测其所有子图是否满足约束条件,挖掘它们非常具有计算挑战性．基于非冗余协同图模式的多种特性,提出相对应的削减规则;通过对区分能力的边界估计,提出两个快速检测非冗余协同图模式方法,在此基础上给出了一种高效的深度优先挖掘算法 GINS．大量真实与合成数据集上的实验结果表明,GINS 算法明显优于其他两个代表性算法,作为图分类模型的分类特征时,非冗余协同图模式获得了较高的分类精度．     

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

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

并发程序执行技术的一类工程实现

从工程实例出发，具体分析了在工程上普遍存在的一类问题：即在没有任务操作系统支持下如何实现多任务的技术。以一个监控系统为例，分析了其在ＤＯＳ环境下的实现方法。     

线程池技术在并发服务器中的应用

线程池技术能有效减少多线程环境中资源的消耗,可以提高系统的处理能力。因此现在的服务器程序中大量应用该技术,可以最大程度的利用系统的资源,消除系统因频繁创建、销毁线程而带来的系统开销。文章就利用线程池技术来解决并发服务器中客户端频繁对服务器端请求服务这一应用场景,分析了线程池的工作原理,并做了仿真测试,证明了线程池在应用中确实有比较好的效果。