检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

节点与决策模式两段式映射的子图查询算法

高技术通讯 2010年第3期20卷 270-278页

作者：李先通李建中哈尔滨工业大学计算机科学与技术学院哈尔滨150001

针对大规模图集的子图查询问题,给出了一种基于节点与决策模式映射(NDFM)的索引结构——NDFM-Index,并在此索引结构的基础上提出了一种图集的子图查询算法。NDFM-Index利用图中关键节点所携带的结构信息以及邻居的标号分布,与决策模式... 详细信息

针对大规模图集的子图查询问题,给出了一种基于节点与决策模式映射(NDFM)的索引结构——NDFM-Index,并在此索引结构的基础上提出了一种图集的子图查询算法。NDFM-Index利用图中关键节点所携带的结构信息以及邻居的标号分布,与决策模式形成映射,从而不通过枚举直接得到查询图所包含的索引模式,得到更小的候选集。理论与实验的分析结果表明,该算法不但能避免索引筛选过程中对查询图子图的枚举过程,而且能显著地减小候选集尺寸,进而大大降低查询图与候选集之间的子图同构测试次数,提高查询效率。

关键词：图数据集图查询频繁模式决策模式节点向量

在线全文

学校读者我要写书评

暂无评论

XML数据流上的高效聚集算法

软件学报 2008年第8期19卷 2032-2042页

作者：王宏志李建中骆吉洲哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001

XML数据流的特点是所有元素和值仅允许扫描1次.针对XML数据流上的聚集问题,提出了高效的XML数据流聚集算法.这种算法不但能够有效地支持XML数据流上具有复杂结构聚集查询的处理,而且能够有效地支持具有递归结构XML数据流上的聚集查询处... 详细信息

XML数据流的特点是所有元素和值仅允许扫描1次.针对XML数据流上的聚集问题,提出了高效的XML数据流聚集算法.这种算法不但能够有效地支持XML数据流上具有复杂结构聚集查询的处理,而且能够有效地支持具有递归结构XML数据流上的聚集查询处理.理论分析和实验结果表明,算法能够有效地处理XML数据流上的聚集查询。并且具有很好的可扩展性.

关键词： XML数据流聚集算法

在线全文

学校读者我要写书评

暂无评论

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

计算机学报 2010年第2期33卷 215-230页

作者：刘勇高宏李建中哈尔滨工业大学计算机科学与技术学院哈尔滨150001

提出了一个新的研究问题:如何挖掘Top-K图模式,联合起来使某个意义度量最大化.利用信息论的概念,给出了两个具体问题的定义MES和MIGS,并证明它们是NP-难.提出了两个高效算法Greedy-TopK和***-TopK先产生频繁子图,然后按增量贪心方式选择... 详细信息

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

关键词：图挖掘图数据库频繁子图代表模式联合熵信息增益

在线全文

学校读者我要写书评

暂无评论

图结构XML文档上子图查询的高效处理算法

软件学报 2009年第9期20卷 2436-2449页

作者：王宏志骆吉洲李建中哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,... 详细信息

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.

关键词： XML 图子图查询查询处理

在线全文

学校读者我要写书评

暂无评论

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

软件学报 2010年第10期21卷 2477-2493页

作者：刘勇李建中高宏哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保... 详细信息

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

关键词：数据挖掘图挖掘图数据库频繁子图跳跃模式

无线传感器网络中一种近似Skyline查询处理算法

在线全文

学校读者我要写书评

暂无评论

软件学报 2010年第5期21卷 1020-1030页

作者：潘立强李建中骆吉洲哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001

由于无线传感器网络的能源有限,且在许多应用中Skyline查询的部分结果即可满足用户需求,提出了一种近似Skyline查询处理算法,在满足用户查询需求的前提下最大化地节省能量.该算法仅需无线传感器网络中的部分传感器节点回传其感知数据即... 详细信息

由于无线传感器网络的能源有限,且在许多应用中Skyline查询的部分结果即可满足用户需求,提出了一种近似Skyline查询处理算法,在满足用户查询需求的前提下最大化地节省能量.该算法仅需无线传感器网络中的部分传感器节点回传其感知数据即可计算出Skyline查询的一个近似结果集.由于该算法在处理查询时,每个传感器节点只需考察自身数据信息即可决定是否回传其感知数据,而无须与其他传感器节点的感知数据进行比较,因此可以避免大量的网内通信开销,从而节省网络能源.模拟环境下的大量实验结果表明,该算法可以根据用户的应用需求,节能地处理传感器网络中的近似skyline查询.

关键词：传感器网络算法 Skyline 查询处理近似查询

在线全文

学校读者我要写书评

暂无评论

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

软件学报 2009年第11期20卷 2965-2976页

作者：邹兆年李建中高宏张硕哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001

研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该... 详细信息

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

关键词：不确定图图挖掘频繁子图模式

在线全文

学校读者我要写书评

暂无评论

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

软件学报 2010年第3期21卷 401-414页

作者：张硕李建中高宏邹兆年哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001

提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检... 详细信息

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

关键词：图匹配子图同构预处理图索引

在线全文

学校读者我要写书评

暂无评论

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

软件学报 2010年第5期21卷 1007-1019页

作者：邹兆年高宏李建中张硕哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动态规划算法.模拟数据集上的实... 详细信息

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

关键词：演变图连接子图演变模式