ERSearch:一种高效的子图查询算法

子图查询是图数据库研究中的一个重要问题,许多方法基于“过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌入关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比,ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.     

图数据中频繁模式挖掘算法研究综述

 本文对图数据中的频繁模式挖掘算法进行了综述.依据算法的特性和数学基础对算法进行了分类,主要集中于算法的求解思想和不同算法之间的关系的比较,并对一些著名的算法进行了详细的分析和讨论.基于算法的特性,比较了各种算法适用的范围以及应用领域.最后,讨论了频繁模式挖掘的最新进展及未来的研究方向.     

SCBT-index:基于谱编码的子图索引算法

随着图模型规模的扩大,单机算法难以适应大规模数据集下的子图查询.而现有的分布式算法基于无索引的简单遍历,join过程容易出现内存溢出,而且查询图分布异常时易出现负载不均衡.提出了一种基于谱编码的二叉索引树（SCBT-index）,首先对数据图中的顶点谱编码,根据编码信息构建二叉索引树.然后对查询图使用最小查询计划进行分解,最后join过程使用3个剪枝策略：基于拓扑结构的预剪枝、序列化join和基于分布式下的join优化.实验结果表明,SCBT-index在图集下的综合性能优于现有主流算法,单图下的查询时间为现有算法的1/2到1/4.     

频繁子图挖掘研究综述

归纳了频繁子图挖掘方法的处理流程,分析评价了频繁子图挖掘的典型算法:广度优先搜索和深度优先搜索的频繁子图挖掘算法,概述了频繁子图挖掘研究的平台--图模型及其产生器,并对频繁子图挖掘方法未来研究方向进行了展望.     

频繁子图挖掘算法gSpan的设计与实现

由于大部分图挖掘算法都需要利用频繁子图,频繁子图挖掘逐渐成为了数据挖掘领域中的热点研究内容.目前,很多高效的频繁子图挖掘算法已经被提出.其中,gSpan算法是目前公认的最好的频繁子图挖掘算法.然而,在化合物数据集上,还可以利用化合物的特殊结构进一步优化gSpan算法的性能.文献利用了化合物分子结构的对称性和原子类型分布...     

一种基于极大完全子图的最大频繁项集并行挖掘算法

提出一种基于极大完全子图的最大频繁项集并行挖掘算法PMFIM,通过遍历由频繁2-项集构成的用邻-接矩阵表示的图,寻找图的极大完全子图,从而由极大完全子图顶点序列实现对项集的划分,即挖掘子任务的划分.在同类算法中,将找到的最大频繁项划分为局部最大频繁项集LMFI、可能最大频繁项集PMFI和邻接项集的最大频繁项集的超集SMFI,减少了该类算法合并最大频繁项集的开销,并对算法进行了实现和优化.     

聚合查询重写的MiniCon算法

研究了聚合查询的重写问题。提出了一种聚合查询的重写算法，借用了MiniCon算法的思想，解决了在给定一个聚合查询和一组聚合视图的情况下，找到最大被包含重写的问题．证明了算法的正确性。     

一种用于生物网络数据的频繁模式挖掘算法

 频繁模式挖掘是生物网络数据分析中的一个核心问题,对于研究生物网络的组织结构和功能模块具有重要意义.本文提出了子图环分布的概念并构造了子图搜索算法,提高了搜索效率.其次设计了动态抽样算法计算子图频率,用于提高非穷举搜索的精度.利用4个真实生物网络数据进行仿真实验研究,验证了本文算法在效率和精度上相对于现有算法的优势.     

基于恒等子图搜索的点模式匹配算法

点模式匹配问题是计算机视觉和模式识别领域中的一个重要课题,但由于噪声、视场等因素始终难以完全解决.通过构建点模式关系图,把点模式匹配问题转化为关系图最大恒等子图搜索问题,由此给出图、子图、图同构和恒等、支持顶点对及支持顶点对集的概念并对它们满足的一些性质和定理进行了证明,最后提出了一种对最大恒等子图搜索的有效算法,在对...     

基于图论的频繁闭项集挖掘

利用了有向项集图来存储事务数据库中有关频繁项集的信息,提出了有向项集图的三叉链表式存储结构和基于有向项集图的频繁闭项集挖掘算法。不仅实现了事务数据库的一次扫描,减少了I/O代价,而且提高了数据结构的存储空间效率和频繁闭项集挖掘算法的执行时间效率。     

基于相容关系的XML索引机制

随着XML逐渐成为Internet数据表示与数据交换的标准,存储与查询XML数据变得日益重要.由于传统方法无法适应XML数据新的需求,使得XML索引成为一个挑战性的课题.到目前为止,已经出现了不少针对XML数据的索引方法.然而,在处理基于相对路径的查询上,缺少有效的解决办法.本文提出了一种基于相容关系的索引模式,结合XML文档拓扑结构的自身特点,能够有效地处理基于相对路径的查询.这种模式的主要特点包括:(1)利用XML数据的拓扑结构而不是XML文档的模式(DTD或XML Schema)来进行相对路径到绝对路径的转换;(2)对拓扑结构进行基于相容关系的数字方式编码,能够快速确定对应结点的依赖关系.实验证明这种方法在处理基于规则路径表示(尤其是相对路径)的XML查询时具有更高的效率.     

Query Acceleration of Graph Databases by ID Caching Technology

In this paper, we approach the design of ID caching technology (IDCT) for graph databases, with the purpose of accelerating the queries on graph database data and avoiding redundant graph database query operations which will consume great computer resources. Traditional graph database caching technology (GDCT) needs a large memory to store data and has the problems of serious data consistency and low cache utilization. To address these issues, in the paper we propose a new technology which focuses on ID allocation mechanism and high-speed queries of ID on graph databases. Specifically, ID of the query result is cached in memory and data consistency is achieved through the real-time synchronization and cache memory adaptation. In addition, we set up complex queries and simple queries to satisfy all query requirements and design a mechanism of cache replacement based on query action time, query times, and memory capacity, thus improving the performance furthermore. Extensive experiments show the superiority of our techniques compared with the traditional query approach of graph databases.