单图中的近似频繁子图挖掘算法

图数据的挖掘工作是数据挖掘工作中的重要组成部分,已经有许多人在这个领域进行了深入的研究.由于数据获取不可避免噪音数据,故在挖掘频繁图时考虑近似十分重要.然而许多此前的工作只考虑了子图间编辑距离(Graph Edit Distance,GED)的绝对值,而没有考虑子图间编辑距离与子图大小的相对关系.提出了一种在单图中进行近似频繁子图挖掘的新算法,并在计算近似程度时考虑当前子图的大小.该算法通过对近似频繁子图的大小上限进行预测,并通过局部反单调性进行剪枝,提高了算法的效率.实验表明,该算法能够挖掘出传统算法无法发现的近似频繁子图,且相比对比算法具有更好的时间性能.     

八邻域网格聚类的多样性XML文档近似查询算法

提出了一种基于八邻域网格聚类的多样性XML近似查询算法.首先给出了支持XML文档间语义距离计算的3种编辑操作代价模型,再利用XML文档间的语义距离建立XML文档的向量模型并设计基于八邻域网格的XML文档聚类算法,进而利用聚类过程中得到的物理和逻辑聚类中心对静态有序选择算法的查询评估策略进行优化,这样做只需定位聚类中心所在组群的局部范围,并在该范围内进行目标查询,而无需遍历整个XML数据库,从而快速返回满足用户需求的查询结果.经汽车外形智能化设计实验表明,所提算法的查询速度比静态有序选择算法平均提高了3~4倍.     

基于摘要图的不确定社会网络Top-k子图查询算法

针对不确定W eb社会网络的Top-k子图查询问题,以无向、顶点带标签及边赋权重的简单图为基本模型,设计了用来简洁描述社会网络并编码原始图信息的摘要图,提出了Top-k子图同构查询算法。针对真实和虚拟网络数据进行了大量实验,结果表明:基于摘要图的Top-k子图查询算法较VF2算法运算时间缩短;由于构建摘要图时的主要依据是顶点的标号,因此查询图的标号分布对查询性能有较大影响;顶点标号数目增加时该算法的查询性能呈类似指数形式提高,而VF2算法的查询性能没有受到较大影响;当数据图的顶点数量增大时,该算法与VF2算法相比,消耗时间的增长更缓慢;该算法在处理Top-k查询时体现出了稳定高效的性能。     

具有约束的极小生成子图的一个算法

针对实际中的一类连接问题建立了网络模型，给出了便于计算机实现的算法，即：通过依次收缩各边简化网络Ｇ＝ （ Ｖ，Ｅ，Ｗ） ，最终得到最小生成树；然后恢复各边和顶点，从而得到了此类问题的最优解。     

传感器网络空间关键字近似Top-k查询算法

提出了一种基于节点剪枝的Top-k査询算法.定义集合支配区域与剪枝规则,根据用户查询位置的变动,按照给定的剪切规则,对传感器网络节点进行剪枝处理,将符合规则的节点预先筛除,运用统计学抽样理论,设计了空间关键字近似Top-k查询算法.在2个真实数据集上进行验证.实验结果表明,该算法能够满足传感器网络环境中用户的需求,并且相比于边界距离增量算法(IBD)与基于改进的MW-Voronoi区域的空间关键字查询算法(MSK-uvr),其网络通信开销较低.     

Web数据库近似查询结果自动排序方法

针对Web数据库近似查询产生的多查询结果问题,提出了一种近似查询结果自动排序方法,该方法利用KL距离(Kullback-Leibler distance),PIR(probabilistic information retrieval)模型和查询历史(query history)来构建元组排序打分函数;打分函数根据结果元组中被查询指定的属性值对初始查询的满足度和未被查询指定的属性值与用户偏好的相关度来评估元组的排序分值.实验证明,提出的排序方法能够较好地满足用户需求和偏好,并具有较高执行效率.     

一种面向无向加权图的子图查询方法

随着图结构的大规模应用,图数据库上的查询已经成为图挖掘的研究热点。针对无向加权图,本文提出一种基于最短权值路径和拉普拉斯图谱的子图查询方法PSQuery。首先,PSQuery方法选取可表示数据图的高效特征属性;接着,对提取的特征属性按照哈希映射进行编码,将特征编码组合生成节点编码和图编码,并且基于图编码构建索引树;最后,通过实现过滤-验证框架得到结果集:按照提取特征的嵌套性质进行过滤生成候选集,再根据VF2算法进行验证得到最终的超图集合。实验结果表明,提出的方法加速了无向加权图数据库上的子图查询过程,提高了查询效率。     

高效的子空间可逆skyline查询算法

提出了一种高效的子空间可逆skyline查询算法RSQS.该算法采用基于分区的B+树对可逆Skyline进行计算,不同于传统的R-tree修剪方法;RSQS利用提出的几种修剪策略,包括相互修剪、预计算、尽早终止搜索等,采用过滤-精炼框架实现,能快速地修剪搜索空间,避免了大部分的I/O操作.实验结果表明:RSQS算法具有极高的修剪能力和很高的效率:在二维子空间中每个对象平均仅需与约1.2个其他对象比较.     

URSI:高效的子图同构查询算法

子图同构查询用于返回数据图中与给定查询图匹配的子图,是图数据管理中的核心问题。如果匹配策略不当、查询结点和数据结点之间大量的冗余枚举以及剪枝策略不当,都会引起查询中的冗余计算问题。本文首先将查询图转化为邻居等价类树并使用过滤条件生成候选区域;其次,通过对候选区域探测将区域中的结点进行排列组合得到结点匹配顺序,并对数据结点进行验证,得到查询图在数据图中的所有匹配的子图;最后给出了基于上述策略的URSI算法,并在真实的数据集上通过实验验证了所提算法的高效性。     

支持多子串近似匹配的空间关键词查询算法

随着空间数据飞速增长,不仅POI(Point Of Interest)越来越密集,而且每个空间点的文本描述也越来越多,以往关键词近似查询算法中,不同长度的关键词需要不同的阈值相匹配,影响查询效率和查询结果.针对以上不足提出了支持空间多子串近似匹配的空间关键词查询算法,在该算法中不需要考虑阈值的改变,而是将编辑距离直接应用到索引结构中.通过真实数据进行实验,表明该算法在查询精准性和查询效率上都有较大的提高.     

面向异质可扩展标记语言文档的近似查询算法

提出了一种面向异质可扩展标记语言（XML）文档的近似查询算法（TPQR）．利用模式重写策略，通过对XML模式之间语义相似度及节点映射关系的求解，将原始查询树改写为多种XML模式下的重写查询树，从而解决了XML数据的多样性带来的查询语义缺失问题．将经变异操作序列得到的变异查询树精确地嵌入在XML数据树之中，即可将XML近似查询问题转变为多棵变异查询树的精确查询问题．在汽车外形智能化设计的实验中比较了TPQR算法和静态有序选择算法，结果表明，在查准率、查全率上，前者比后者分别提高了5％～10％和10%～30%．     

近似求解子问题的乘性Schwarz算法

提出求解线性互补问题的一个乘性Ｓｃｈｗａｒｚ算法，算法中子问题非精确求解，得到了单调收敛性及误差估计式。     

基于HITS算法的查询结果多样化方法

现有的查询结果多样化研究很难准确得到用户多样性需求并提供与用户查询各个方面需求相关的文档。针对这个问题,本文基于HITS算法的网页间链接分析特性,根据网页链接图直接计算查询结果列表中的文档可能满足用户多样性需求的程度,并将其应用到结果列表的重排序中以实现搜索结果多样性。在TREC大规模数据集合上的实验结果表明了该方法的有效性。     

子图配准的随机搜索算法

本文给出了一种子图配准的随机搜索算法。搜索过程是纵随机选择的起点开始的。该点由在(0,1)区间上均匀分布的假随机数所产生。这一搜索过程是朝向匹配点逐步地进行的。本算法的优点已经由试验所证实。试验是在窗口尺寸与图片尺寸的比值ξ=0.21的情况下进行的。     

一个具有语义优化的分布式查询处理算法

本文描述一个分布式关系数据库系统中具有语义优化的查询处理算法。算法的基本过程是:从原查询转换到查询图同时进行副本选择,得到T-图,经一般优化、语义优化,进而产生查询处理策略。优化的目标是总处理代价最小。语义变换过程应用了启发式的控制策略。     

Outlier-DivideConquer：近似聚集查询中离群分治取样算法

取样是一种通用有效的近似技术,利用取样技术进行近似聚集查询处理是决策支持系统和数据挖掘实现技术中的常用方法.如何正确有效地给出近似查询结果并最小化近似查询误差是近似查询处理的关键和目标.在深入研究近似聚集查询取样方法的基础上,本文提出了一个有误差确界且只需单遍扫描数据集的离群分治取样Outlier-DivideConq...     

基于因果图的一种近似推理算法

在因果图理论中,采用图形化和直接因果强度来表达知识和因果关系,它克服了贝叶斯网的一些不足,已经发展成了一个能够处理离散变量和连续变量的混合模型.但由于因果图的精确推理是NP难的,不能完全适应实际问题的需要,因此给出了一种近似推理算法,削减了因果图精确算法的步骤和需要的一些苛刻条件,使得计算的复杂度与事件的节点数同阶,并用具体例子说明了算法推理过程.     

面向大规模时态图的紧密子图维护算法

大规模图数据中的重要顶点与层级结构对于挖掘复杂网络（如社交网络、交通网络等）中有价值的信息具有重要意义.提出一种自顶向下的大规模时态图(k,h)-维护算法,对时态图中紧密度最高的前n层(k,h)-核,或满足自定义k,h值约束条件的核进行维护.首先提出识别(k,h)-最大层的方法 .当时态图中出现新的边时,为了定位当前时刻可能因新加入边导致核值需要更新的顶点的范围,提出候选插入子图与部分(k,h)-核的概念及相应的识别算法.针对加边情况,提出自顶向下的时态图(k,h)-核维护加边算法,根据部分(k,h)-核识别核值受加边影响的顶点并对其核值进行更新.针对当前时刻有已经存在的边被删除的情况,提出自顶向下的时态图(k,h)-核维护删边算法,对上一时刻的(k,h)-核做最小调整以得到当前时刻的核值.从理论上证明了算法的正确性,还在真实的时态图上设计了一系列对比实验.实验结果表明,在维护层数较少时下添加边,提出的核维护算法与其他对比算法相比,加速比可达几十倍;删边时,加速比也在1～2倍.提出的算法有良好的扩展性,对于增删不同数量的边和不同的(k,h)设置,都能保持较高的效率.     

支持增量图数据的超图查询算法研究

当前大部分图查询算法都是针对静态图数据,不适用于现实应用中不断更新的图数据。针对这一问题,提出支持增量图数据的超图查询算法。该算法将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果,算法在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算。通过分析证明,所提算法时间和空间复杂度不随数据图的增加而呈线性增长,节省了大量时间和空间代价。