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

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

演变图上的连接子图演变模式挖掘

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表明,挖掘结果在真实应用中具有实际意义.

大规模不确定图上的Top-k极大团挖掘算法

该文研究了从不确定图中挖掘出前k个出现概率最高的极大团的问题,提出了一种基于划分的高效并行算法.在该算法中,输入的大规模不确定图首先被划分为若干互不重叠的规模较小的子图,每个子图通过扩展邻居结点信息成为扩展子图.而后,应用改进后的分支界限搜索策略,并行挖掘各个扩展子图,以得到局部top-k结果.最后,归并所有的局部top-k结果,得到全局top-k极大团.同时,该文还提出了两种预处理策略,以提高算法效率.并且严格证明了算法的正确性.在多组不确定图数据集上的实验结果表明,算法具有很高的效率和很好的实用性.

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.

数据完整性的评估方法

随着信息技术的发展,数据的规模正在高速增长,数据中普遍存在质量问题.针对海量关系数据中普遍存在的数据不完整现象,研究了关系数据完整性度量问题.针对数据的完整性计算问题,提出了数据完整性计算模型,以及精确算法和基于均匀抽样的近似算法.理论分析证明了近似算法可以达到任意的精度要求,可以高效地对数据完整性进行计算.通过在DBLP数据上的实验验证了算法的有效性和高效性.

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

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

一种新的高效图聚集算法

图聚集是将一个大规模的图用简洁的并能有效反映原始图的结构和属性信息的小规模图来表示的技术.图聚集在图数据管理、分析和可视化中发挥着重要作用.图聚集方面现有研究结果还很少,也很不系统.其主要不足之处是:1)算法依赖于具体应用;2)算法仅考虑了图的某方面信息,如结构信息或属性信息;3)算法对用户提供的交互和反馈信息的约束很强.针对现有图聚集算法存在的主要不足,提出一种有向图新型图聚集算法,该算法采用一种新的聚集图质量函数,全面刻画了聚集图多样性、覆盖性、简洁性和实用性.该算法使用LSH(locality sensitive Hashing)技术和基于熵的划分技术,保证了聚集图的质量.在真实数据集上进行了大量的实验,验证了算法的有效性.

不确定图上期望最短距离的计算

研究了不确定图上的最短距离问题,提出了期望最短距离的概念,证明了该问题不存在多项式时间的算法.为了解决该问题,使用了随机采样技术获得不确定图的一些可能世界,在每个可能世界上计算有穷的最短距离,最后计算出平均值作为期望最短距离的估计值.为提高计算效率,使用了过滤条件来减少采样过程中采样的边数从而加快随机采样.在此基础上,提出了一种基于对称变量的、无偏的随机采样近似算法,并证明了与直接随机采样方法相比,该方法在不增加时间开销的同时能减小采样方差.通过真实数据上的实验表明,提出的算法在时间开销和采样方差上均明显好于直接随机采样方法.

异构信息网上的可达性查询

随着图数据规模的爆炸式增长,其形式也越来越复杂.异构信息网可建模成包含多种类型的顶点和多种类型的边的图.例如,文献数据库、在线购物网站等.首次研究异构信息网上的可达性查询问题.利用不同类型顶点之间的关系,查询2个顶点满足路径模式的可达性,该问题的时间复杂度是多项式的.然而在大规模的网络上,每次查询遍历一遍网络的时间开销也是不能容忍的.现有的可达性查询问题主要分为2类:k跳可达性查询和带有标签约束的可达性查询.但是这2种问题的算法都不能用于解决异构信息网上的可达性查询问题.因此,为了实现高效的在线查询,提出一种新的索引结构,通过路径模式的分解,预先计算部分路径模式的可达信息.当在线查询到来时,在路径模式的偏序图上,快速找到索引结构中存在的路径子模式,高效地计算查询结果.在真实和人工数据集上进行了大量实验,验证了算法的有效性.

从不确定图中发现K紧密子图

由蛋白质交互网络、社会网络及无线通信网络构成的图中存在许多不确定性。如何高效获取不确定图中有价值的信息,如蛋白质网络中关键的功能集团、社会网络中适于投放广告的团体及通信网络中应重点维护的区域等,具有重要的现实意义。从理论上证明了在不确定图中发现最紧密子图问题具有NP-Hard复杂性;基于树搜索策略提出了通过枚举解空间及剪枝获得最优解的算法TreeClose;针对树搜索算法TreeClose在处理大图时空间复杂度过高的问题,提出了基于贪心思想的2-近似算法GreedyClose。实验结果表明,通过上述算法可以高效快速地在不确定图中发现紧密子图,从而解决在实际应用中遇到的各种问题。

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.

基于图压缩的最大Steiner连通k核查询处理

研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1~2个数量级.

不确定图上的高效top-k近邻查询处理算法

图的不确定性普遍存在,研究不确定图的高效查询处理具有重要意义.文中提出了不确定图上一种新型查询——近邻查询.给定一个查询标签集R和距离约束σ,在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集.为解决该问题,文中首先提出了"可靠期望距离",然后基于可靠期望距离建立了高效的近邻关系图索引,将不确定图上的近邻查询等价地转化为近邻关系图上的团查询问题,最后使用树搜索算法解决近邻关系图上的团查询问题.理论分析和实验结果表明文中提出的算法能够高效地完成不确定图上的top-k近邻查询.

不确定图上的Top-k稠密子图挖掘算法

该文研究了从不确定图上挖掘top-k稠密子图的问题.由于图数据具有内生不确定性,确定图上稠密子图的定义和挖掘算法在不确定图上均不适用.因此,该文提出了不确定图上期望稠密度的概念,并给出了其在多项式时间内的计算方法.基于此,该文定义了不确定图中导出子图之间的一种偏序关系.利用该偏序关系,将不确定图中的导出子图有效地组织成一棵搜索树.该文严格证明了此搜索树中可以完整无重复地覆盖不确定图上的所有导出子图.据此,该文提出了针对此搜索树的一种分支界限搜索算法DS,用于精确挖掘top-k稠密子图.该文还提出了不相交top-k稠密子图的概念,并给出了一种基于束搜索的启发式近似搜索算法LS.在多组数据集上的实验结果表明,文中提出的DS算法具有很高的效率和很好的扩展性,可用于处理大规模图数据.启发式近似搜索算法LS可以快速发现不相交top-k稠密子图.

嵌入式数据库SQLite上多版本并发控制的设计与实现

针对嵌入式数据库SQLite并发性能较低的问题,提出了一种基于多版本并发控制(MVCC)的并发控制设计。首先,设计了SQLite数据库的以提交的写事务为依据的版本划分方式,重新设计了数据记录的头部字段并以此划分了记录在不同版本访问下的可见性;然后,在SQLite原有结构基础上修改了增、删、查、改等操作与索引结构使得该数据库能在MVCC下工作;最后,对于老旧版本数据提供了一种手动的回收机制。通过实验对比测试了在该设计下的SQLite-MVCC数据库与SQLite数据库的性能区别,发现在并发度较高的状态下SQLite-MVCC数据库在相同时间内可多完成70%以上的事务。实验结果验证了所提设计可以有效提高SQLite的并发性能,使得该数据库可以应对并发情况下的需求。

历史图上基于CSR结构的PageRank算法

近年来,学者们对静态图的研究越来越全面、深入,已经形成了完善的理论体系。但是,对于生活中的一些应用问题,如社交网络中不断变化的关系等,使用静态图表示此类动态变化的关系似乎显得有些乏力。而历史图可以表示动态的变化。PageRank算法是用于衡量网页重要程度的算法,而网络中不断有网站新建或删除,这样的网络用历史图来表示更为合适,因此考虑在历史图上利用CSR(Compressed Sparse Row)结构实现PageRank,使得程序能够给出几个目标时间上各网站的评分,进而能够提供网站评分的变化情况,给出网站影响力趋势的预测。在Wekipedia提供的网页互相连接的Hyperlink networks数据集上,将所提方法与在链表上实现PageRank算法做比较,结果显示其性能大大优于使用链表的结构,并且随着数据规模和目标时间规模的增大,其优势将会越来越明显。

不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图。在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法。

基于物理操作级模型的查询执行时间预测方法

查询执行时间预测(Query Performance Prediction,QPP)是数据库系统中一个重要的研究问题。当数据库系统中存在并发执行的事务时,现有的QPP方法无法在不改变数据库查询性能的前提下建立准确的QPP模型。为此,提出了一种基于物理操作的查询执行时间预测新方法,该方法以查询的物理操作为单位建立单元预测模型,根据查询计划将单元预测模型组合为完整的QPP模型,把能够刻画数据库系统并发状态的统计信息纳入模型的输入特征。所提方法只须使用DBMS提供的基本手段即可获取构建模型所需的数据库统计信息,无须改变DBMS,也不会影响数据库系统上原有工作负载的执行。实验结果表明,所提方法无论在OLTP还是OLAP应用中,在不同的查询计划和并发度下的预测准确性均高于其他对比方法。

Spark GraphX上的SPARQL查询处理算法

资源描述框架(resource description framework,RDF)由于其表示的灵活性和天然的图数据模型而变得越来越流行。与此同时,RDF数据的数据量也在以惊人的速度增长。由于数据量的增长,在单机上存储和查询RDF数据变得越来越不方便,从而激发了分布式存储查询的需求。学术界在分布式存储查询系统,例如Hadoop、Spark上已经做了大量的工作。基于Hadoop的分布式存储查询方式的主要缺点是中间结果需要被写回磁盘,从而产生大量的I/O操作。提出了一种新的在Spark Graph X上进行SPARQL查询评估的方法SQX,将RDF数据视为一个带标签的属性图,提出了一种新的查询计划生成方案并且通过图并行的方式实现SPARQL查询评估。SQX采用了一种"查询树匹配"+"结果过滤"的方法。针对每一个SPARQL查询,产生相应的查询树和约束条件。在每一轮的超级步中,查询树中的多条边可以被并行处理,对迭代执行完毕后的结果进行过滤,满足约束条件的将作为最终的结果。实验结果表明,算法能够有效处理SPARQL查询并且具有良好的可扩展性。

时态图上图模式匹配研究综述

图数据模型是一种通用且已经得到广泛应用的可以处理数据对象间复杂关系的数据模型。然而,现有的大多数研究只关注静态图数据的结构或者顶点和边上的属性,忽略了现实中数据的一个重要特征即时态信息。忽略了时态信息将导致错过很多的有价值的信息,甚至得到错误的信息。作为图研究领域中重要的研究内容之一,图模式匹配问题的研究也需要考虑时态信息。考虑到图模式匹配研究的重要性以及时态信息对数据的重要性,本文根据时态图的快照模型、边流模型和区间模型以及时态图数据的时序性、持续性和演化性对时态图上图模式匹配问题进行了全面地综述,并总结了现有工作的不足。