基于查询对象的路网Skyline查询中Why-not问题的研究

随着信息技术的高度发展,数据成为了重要的战略资源,如何利用大数据进行查询是众多学者的研究内容.与此同时,被查询对象在未被选择时,如何利用大数据使自己能够满足用户的查询要求也成为了重要的研究方向.在分析现有算法存在的不足的基础上,根据实际生活中查询的特点,对基于查询对象的路网Skyline查询中的why-not问题进行了研究,并针对此问题提出了属性优化算法.该算法包括修改why-not点的空间属性和非空间属性,以及修改查询中心的位置.考虑到实际情况,将时间属性单列而不是简单地将其作为非空间属性的一维.算法采用剪枝策略以提高效率.最后在真实路网数据和生成的兴趣点数据集上进行对比实验,结果表明在特定时间段同时修改空间、非时空属性的方法可以有效地解决此问题.     

一种改进的关联规则增量式更新算法

针对增量式更新关联规则算法FUP会产生大量候选项集和多次扫描数据库的问题,提出改进算法PFUP。该算法借鉴强频繁项集概念,利用强频繁项集连接生成小数量的候选项集,采用预剪枝策略减少对数据库的扫描次数。仿真实验表明,在数据库和支持度相同的情况下,PFUP算法的执行时间比FUP算法减少了50%左右。     

面向超图数据的最大独立集算法

超图是普通图的泛化表示, 在许多应用领域都很常见, 包括互联网、生物信息学和社交网络等. 独立集问题是图分析领域的一个基础性研究问题, 传统的独立集算法大多都是针对普通图数据, 如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题. 针对这一问题, 提出一种超图独立集的定义. 首先分析超图独立集搜索的两个特性, 然后提出一种基于贪心策略的基础算法. 接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合, 以精确剪枝策略缩小图的规模, 以近似剪枝策略加快搜索速度. 此外, 还提出4种高效的剪枝策略, 并对每种剪枝策略进行理论证明. 最后, 通过在10个真实超图数据集上进行实验, 结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.     

一种保持结点可达性的高效社会网络图匿名算法

为了保护社会网络隐私信息,提出了多种社会网络图匿名化技术.图匿名化目的在于通过图修改操作来防止隐私泄露,同时保证匿名图在社会网络分析和图查询方面的数据可用性.可达性查询是一种基本图查询操作,可达性查询精度是衡量图数据可用性的一项重要指标.然而,当前研究忽略了图匿名对结点可达性的影响,导致较大的可达性信息损失.为了保持匿名图中结点的可达性,提出了可达性保持图匿名化（reachability preserving anonymization,简称RPA）算法,其基本思想是将结点进行分组并采取贪心策略进行匿名,从而减少匿名过程中的可达性信息损失.为了保证RPA算法的实用性,针对其执行效率进行优化,首先提出采用可达区间来高效地评估边添加操作所导致的匿名损失;其次,通过采用候选邻居索引,进一步加速RPA算法对每个结点的匿名过程.基于真实社会网络数据的实验结果表明了RPA算法的高执行效率,同时验证了生成匿名图在可达性查询方面的高精度.     

一种基于图结构分解的图近似查询方法研究

图近似查询能够得到与查询图近似的结果集,相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率,提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解,对其建立图分解索引,利用查询图的最小生成树集得到满足阈值的生成树集,通过图标准编码在索引中快速定位,查找出所有可能的近似结果。实验结果表明,该算法能有效得到近似结果,提高查询速度。     

基于图的关联规则改进算法

关联规则挖掘是数据挖掘研究的最重要课题之一。基于图的关联规则挖掘DLG算法通过一次扫描数据库构建关联图,然后遍历该关联图产生频繁项集,有效地提高了关联规则挖掘的性能。在分析该算法基本原理基础上,提出了一种改进的算法—DLG#。改进算法在关联图构造同时构造项集关联矩阵,在候选项集生成时结合关联图和Apriori性质对冗余项集进行剪枝,减少了候选项集数,简化了候选项集的验证。比较实验结果表明,在不同数据集和不同支持度阈值下,改进算法都能更快速的发现频繁项集,当频繁项集平均长度较大时性能提高明显。     

基于文档属性单元松弛的XML近似查询方法

为解决普通用户对XML文档的近似查询问题,提出了一种基于文档属性单元松弛的XML近似查询方法.该方法将XML文档中的叶子结点和属性结点作为属性单元处理,基于一致集的概念导出最大集,生成最小非平凡函数依赖集,从而找出属性单元之间的近似函数依赖关系,进而求出近似候选码和近似关键字.在此基础上,根据属性单元支持度将属性单元按重要程度排列并据此对初始查询条件进行松弛,最不重要的属性单元最先松弛并且松弛程度最大.利用松弛后的查询条件对XML文档进行查询,可得到与初始查询条件近似的查询结果.实验结果和分析表明:提出的XML近似查询方法能够很好地满足用户的查询意图,具有较高的执行效率.     

大规模标签图中的动态Top-K兴趣子图查询

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性（NTF）索引和边特性（EF）索引的图拓扑结构特性（GTSF）索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。     

一种快速获取候选3项集的Apriori改进算法

为了解决Apriori算法中生成候选二项集不能剪枝、多次扫描数据库中对计算支持度不产生作用的项等缺点,提出了使用矩阵直接生成频繁二项集及候选三项集,使用链表删除对计算支持度不产生作用的数据的方法。通过设置不同的最小支持度将两个算法的运行时间进行对比,根据结果分析证明改进后的算法比Apriori算法执行效率高。     

一种应用于DaaS的物化视图候选集生成算法

针对DaaS数据中心建设中物化视图选择对候选视图集的新要求和传统MVPP方法的不足,提出一种新的候选视图集生成算法。该算法利用多操作变换规则进行查询优化,然后利用算法1和2进行关系融合。实验证明,该算法能够提高查询效率,压缩候选视图集,具有较高的可扩展性,符合应用需求。