高效前缀约简的三维Hilbert空间填充曲线编解码算法

3维Hilbert空间填充曲线(3D HSFC)的编码和解码效率对空间查询处理、图像处理等领域的应用举足轻重。现有的3维编解码算法独立编解码每一个点,忽略了Hilbert曲线的局部保持特性。为了提高编解码效率,该文设计了高效的3D状态视图,并提出一种新的前缀约简的3D HSFC编码算法(PR-3HE)和前缀约简3D HSFC解码算法(PR-3HD),这两个算法通过公共前缀的定义和识别、公共前缀约简及多种优化技术来最小化需要编码的阶数,从而提高3D HSFC的编解码效率。理论上证明:当编码或解码一个k阶的窗体(窗体内总共含有2k×2k×2k个点)时,PR-3HE平均每个点的编码阶数不超过2,PR-3HD平均解码阶数不超过8/7。相对于传统的基于迭代的方法,编解码时间复杂度从O(k)降低到了O(1)。实验结果表明,该文算法在模拟数据集和真实数据集上的表现显著优于现有算法。

基于形成性评价的软件工程课程导学探索

针对学生软件工程课程学习中主动性及针对性不足的现状,基于课程前期开展的基于混合式教学的课程导学、以直播为特征的课程在线导学相关实践,提出基于形成性评价的软件工程课程导学方法,并介绍导学设计与实践过程,最后通过导学情况对比数据说明教学效果。

一种基于Spark的频繁项集快速挖掘算法

如何在海量数据集中提高频繁项集的挖掘效率是目前研究的热点.随着数据量的不断增长,使用传统算法产生频繁项集的计算代价依然很高.为此,提出一种基于Spark的频繁项集快速挖掘算法(fast mining algorithm of frequent itemset based on spark,Fmafibs),利用位运算速度快的特点,设计了一种新颖的模式增长策略.该算法首先采用位串表达项集,利用位运算来快速生成候选项集;其次,针对超长位串计算效率低的问题,考虑将事务垂直分组处理,将同一事务不同组之间的频繁项集通过连接获得候选项集,最后进行聚合筛选得到最终频繁项集.算法在Spark环境下,以频繁项集挖掘领域基准数据集进行实验验证.实验结果表明所提方法在保证挖掘结果准确的同时,有效地提高了挖掘效率.

数据库中文查询对偶学习式生成SQL语句研究

针对当前中文NL2SQL(Natural language to SQL)监督学习中需要大量标注数据问题,该文提出基于对偶学习的方式在少量训练数据集上进行弱监督学习,将中文查询生成SQL语句。该文同时使用两个任务来训练自然语言转化到SQL,再从SQL转化到自然语言,让模型学习到任务之间的对偶约束性,获取更多相关的语义信息。同时在训练时使用不同比例带有无标签的数据进行训练,验证对偶学习在NL2SQL解析任务上的有效性。实验表明,在不同中英文数据集ATIS、GEO以及TableQA中,本文模型与基准模型Seq2Seq、Seq2Tree、Seq2SQL、以及-dual等相比,百分比准确率至少增加2.1%,其中在中文TableQA数据集上采用对偶学习执行准确率(Execution Accuracy)至少提升5.3%,只使用60%的标签数据就能取得和监督学习使用90%的标签数据相似的效果。

数据立方体与频繁项集的统一计算框架研究

数据立方体和频繁项集挖掘分别是数据仓库和数据挖掘领域的重要技术,已开展了大量的相关研究工作,取得了较好的进展.数据立方体和频繁项集挖掘依据各自的数据单元和项集构造了类似的代数格(Lattice)结构;数据立方体的等价类上界单元与频繁项集挖掘的闭项集也是相对应的.如果能够论证二者的统一性,则可以为彼此提供更广泛的研究思路,有利于两种技术的相互促进,如:在数据库中利用冰山立方体计算实现频繁项集挖掘来避免数据迁移、利用频繁项集挖掘算法优化数据立方体计算等.之前的工作没有将二者系统地结合起来研究,也没有建立二者之间较为完整的联系.本文在深入研究数据立方体的计算和频繁项集挖掘的过程后,将二者有效地结合在一起,提出了统一的计算框架,给出了二者众多计算性质和方法之间的映射关系,进行了相关概念泛化,具体地建立了冰山立方体、浓缩立方体和商立方体等主要数据立方体计算与相应频繁项集挖掘方法的对应关系.通过算法和实验进一步论证统一计算的有效性:(1)将频繁项集挖掘事务集导入关系数据库,用冰山立方体计算方式进行频繁项集挖掘,从而在数据库中用标准的或扩展的SQL可以实现对关系表进行频繁项集挖掘;(2)验证了浓缩立方体与频繁项集挖掘的统一性并对比了计算效率;(3)将基本表转换为频繁项集挖掘事务集,引入高效的频繁项集挖掘算法LCM计算商立方体,以提升数据立方体计算效率.在公开的真实数据集和人工合成的数据集上验证二者结合、统一计算的正确性,通过改变元组数、维数和倾斜度进行对比验证有效性.实验发现,在大数据集上可令时间效率提升高达92%.

基于强化学习的数据库多属性索引推荐

传统关系型数据库通过人工方式进行索引推荐,已无法适应日益增长的数据需求,而机器学习技术可以有效地解决数据库索引选择问题。针对以往仅在静态数据库下进行索引推荐且无法及时更新索引配置的局限性,提出了一种基于强化学习算法实现为数据库数据动态变化情况下的一组工作负载推荐最佳多属性索引配置的方法(multi-attribute index intelligent recommendation approach,MIRA)。在公开的TPC-H数据集上的实验结果表明,该方法不仅能有效地为一组工作负载推荐最佳的索引配置,而且优于自定义的比较基线和相关强化学习方法。

基于多线程并行强化学习的数据库索引推荐

建立索引是提高数据库性能的一个重要方法。目前随着强化学习算法的发展,出现了一系列使用强化学习解决索引推荐问题(index selection problem, ISP)的方法。针对现有的深度强化学习索引推荐算法训练时间长、训练不够稳定的问题,提出了一个基于A2C的索引推荐算法PRELIA。该算法加入负载索引扫描行数特征矩阵,并对奖励值进行归一化处理,旨在提高索引选择的准确性和效率,减少索引空间占用。在不同数据集上的实验结果表示,该算法可以在保证与比较算法相当的索引推荐质量的同时,推荐出的索引占用更小的存储空间,其训练时间比基线算法时间提高了4倍以上。

一种支持大规模数据的多维可视化分析框架

以Hadoop为代表的可扩展大规模数据库难以进行多维可视化分析。为此,设计基于B/S架构的可视化分析框架Bizard。数据模型通过封装底层数据接口以支持业界多维数据访问协议XMLA,从而在展现层易于接入支持XMLA的传统分析工具,同时采用视图物化技术提高分析性能,利用互联网技术丰富用户分析体验。实验结果表明,该框架能在高达千万条记录级的数据上进行多维可视化分析。

语义OLAP缓存技术研究

针对页面缓存,元组缓存,语义缓存等查询缓存技术不能充分利用OLAP较一般SQL查询所具有更强的语义和上下文相关性的特性,提出一种新的OLAP查询缓存技术语义OLAP缓存.该缓存模型只存储等价类所代表的集合信息,而不是大量单个数据单元或数据元组信息.随着查询过程的深入,缓存项的等价类范围动态更新,可在保持缓存大小不变的情况下,扩展等价类范围,从而回答更多查询并提高命中率.此外还提出根据缓存项间的上卷、下钻关系将缓存项连接在一起形成代数格结构,以方便剪枝,从而进一步缩小查找范围.实验结果充分证明了该缓存模型和算法的有效性.

基于PC集群的并行数据仓库架构

针对数据仓库规模不断增长而导致难以确保即席查询分析性能的问题,提出一种构建在PC集群上的并行数据仓库架构——HDW,采用Google的GFS和Bigtable技术进行分布式存储管理,采用MapReduce技术进行并行联机分析处理,为前台应用程序提供遵循XMLA规范的统一接口。在18个节点的集群上进行实验,结果表明,HDW系统扩展性好,能快速处理至少千万条元组的数据。

在PC集群上的封闭立方体计算

封闭立方体是联机分析处理中一种有效的数据立方体压缩技术,但封闭立方体的并行算法目前很少有相关文献研究。提出了一种简单而实用的解决方案,即基于MapReduce计算框架,在非共享内存的PC集群上对封闭立方体进行分布式的预计算和查询。相关实验表明,本方法能快速处理千万级的数据,具有较好的线性加速比,而且能够更大地压缩数据立方体存储空间。

不确定性信息条件下系统可靠性分析

在系统可靠性分析中,参数不确定性的正确表达是评价系统稳定与否的先决条件。然而,在实际情况中,影响系统可靠性的参数分布往往缺乏严格的规律性,即便参数大体符合某种分布,也存在漂移现象,采用传统方法处理这类不确定性,存在信息丢失问题。为此引入概率盒理论,提出一种新的不确定性信息条件下系统可靠性分析方法。首先对各个不确定参数进行概率盒建模;其次,将各参数概率盒等信度离散,结合系统可靠性方程计算笛卡尔积,进而得到系统可靠性概率盒模型;最后,以零点为边界划分出风险区和稳定区,并通过积分计算面积定量地分析系统的可靠性。实验以悬臂梁系统为分析对象,与传统方法进行对比分析,实验结果表明,该方法不仅有效而且提高了准确性。

基于MapReduce的封闭立方体并行计算方法

封闭立方体是一种非常有效而重要的数据立方体压缩技术,目前还缺乏对其并行算法的研究.为此,文中提出一种采用C-Cubing方法并通过MapReduce并行模型进行并行化的新方法.该方法首先在Map过程中对各个数据分块计算出数据单元的代表元组和封闭掩码,然后在Reduce过程中进行聚合以获得封闭单元.实验结果表明,文中方法能有效地提高在大数据集上计算封闭立方体的速度.

Spark环境下基于综合权重的不平衡数据集成分类方法

不平衡数据分类经常面临样本严重不平衡、少数类样本分类精度低的问题,随着数据规模增大,分类效率也成为了瓶颈问题.针对以上问题,本文结合spark高效的数据处理能力,提出了一种Spark环境下基于综合权重的不平衡数据集成分类方法.该方法首先依照多数类样本中每类样本的权重以及少数类样本量获得的综合权重进行采样,并与少数类样本组成平衡规模的训练数据集;其次,采用基于相关性的特征选择方法选择最优的特征子集,并对随机森林算法进行改进优化以及利用其获得子分类器.最后在Spark环境下,以UCI数据集进行实验验证.实验结果表明本文方法不仅提高了整体分类精度,而且提升了分类效率.

一种基于协同过滤和混合相似性模型的推荐算法

针对推荐系统协同过滤方法中存在的数据稀疏和冷启动等问题,提出一种基于协同过滤和混合相似性模型的推荐算法。该算法首先计算用户在不同项目间的相似性,然后结合项目特性和标签信息权重来描述用户、项目、特性和标签之间的关系;其次,设定用户偏好因子和不对称因子调整不同用户间的评分偏好;最后,结合用户间相似性、项目综合权重,以及评分偏好构建混合相似性模型,并加入用户时间权重信息解决项目冷启动问题。在公开的MovieLens数据集上的实验表明,该算法在各种评估指标上比其他相关方法获得更显著的结果。

龙胆属5种植物的同工酶比较

为探明龙胆属植物种间亲缘关系,采用聚丙烯酰胺垂直凝胶电泳技术,对龙胆属红花龙胆Gentiana rhodantha、草甸龙胆G.praticola、翼萼龙胆G.pterocalyx、滇龙胆G.rigescens和头花龙胆G.cephalantha的过氧化物酶同工酶(POD)、超氧化物歧化酶同工酶(SOD)和淀粉酶同工酶(AMY)的酶谱和亲缘关系进行比较。结果显示:1)5种龙胆属植物的3种同工酶共显示29条酶带,其酶带数和相对迁移率不同,酶活性也存在差异;2)红花龙胆与翼萼龙胆的亲缘关系较近,滇龙胆与头花龙胆的亲缘关系也较近。5种龙胆的聚类分析结果与形态分类结果一致。

基于状态视图的高效Hilbert编码和解码算法

Hilbert曲线是高维降到1维的重要方法,具有较好的空间聚集和空间连续性,在地理信息系统、空间数据库、信息检索等方面有广泛的应用。现有Hilbert编码或解码算法未考虑输入数据对编码或解码效率的影响,因此将不同输入数据同等对待。为此,该文通过设计高效的状态视图并结合快速置位检测算法提出高效的免计前0的Hilbert编码算法(FZF-HE)和免计前0的Hilbert解码算法(FZF-HD),可快速识别输入数据前部为0而无需迭代计算的部分,从而降低迭代查询次数及算法复杂度,提高编解码效率。实验结果表明,FZF-HE算法和FZF-HD算法在数据均匀分布时效率稍高于现有算法,而在数据偏斜分布时效率远高于现有算法。

一种有效的加权图聚集算法

图聚集(图概括)技术是解决大规模网络的有效技术之一.现实生活中,这些图不仅规模大,而且边可能带有权重,当前图聚集算法很少或未考虑边的权重或边存在的概率等信息,导致聚集图与原图的误差大.为了提高加权图的图聚集的质量和效率,对加权图的图聚集算法进行了研究.为此引入超图邻接矩阵分组的权重值一致性来衡量边权重的一致性,定义压缩率衡量图聚集算法的空间效率,使用误差率衡量聚集图与原图的误差;通过控制图的误差率来控制图的压缩质量,并与现有图聚集算法进行了对比.实验论证了本文图聚集算法的有效性.

Dtrie-allpair:高效的集合T-覆盖连接算法

传统的T-覆盖连接算法会因生成的候选集庞大而导致系统性能降低,为此,文中提出了一种基于trie的动态索引结构——DTI结构,并构建了基于该结构的相似度连接算法——Dtrie-allpair算法.通过该算法可以直接得到allpair连接的结果,不产生任何候选集,有效解决了高候选集产生的问题,克服了传统算法因生成并验证候选集而带来的开销.文中还研究了数据库中记录的顺序及记录中元素顺序对Dtrie-allpair算法性能的影响,并在msweb、msnbc两个数据集下对Dtrie-allpair算法与All-pair、PPJoin算法进行对比.结果表明:Dtrie-allpair算法具有明显的优势,覆盖阈值较小时优势更明显;对msweb数据集,阈值为2时,Dtrie-allpair算法的效率相对于All-pair、PPJoin算法提高近两个数量级;通过对数据集进行频率降序和长度升序组合预处理可大幅降低Dtrie-allpair算法访问的trie结点数量,从而显著提升性能.

数据立方体格的图结构特性研究

数据立方体是数据仓库的核心数据模型,其对应的数据立方体格因保留上卷下钻的语义关系而有利于查询和导航。目前对数据立方体内部结构特性尚未展开系统的研究。为此,将数据立方体格视为图数据,研究数据立方体格的结构特性和解析模型。分析结果表明,不同于随机网络和复杂网络的模型,数据立方体格在度分布、聚集系数、平均最短路径等方面具有不同的结构特性。根据上述特性进一步建立数据立方体格的解析模型。