基于HBase的列存储压缩策略的选择优化

大数据时代背景下,列存储数据库使用场景愈加增多,推动了列存储相关领域的研究进展。为解决现有列存储数据库压缩策略在压缩过程中遇到的数据离散程度大,分类粒度小,配套分类算法缺陷导致的学习成本高,压缩效率难以保证的问题,本文提出了一种基于排序的列区混合压缩策略,首先根据HBase特点设计了一种对各列数据进行排序的方法加强数据紧密度,然后根据数据特点分别使用混级区压缩策略和混级列压缩策略进行压缩策略推荐,在TPC-DS标准数据集上与前人策略进行比较,实验结果显示本文方法在压缩率、压缩/解压时间方面均有优异的表现,从而证明了本文方法的有效性。     

列存储数据库中压缩位图索引技术

为提高压缩码的利用率,提出一种适用于列存储数据库的压缩位图索引技术。定义反转、合并等操作,将所有计算的输入值与输出值格式化为位向量形式。通过活跃度衡量索引中位向量的复杂度,并对压缩位向量进行直接计算,优化where子句和group by子句在查询执行过程中的数据提取。在SSB数据集上的实验结果证明,该技术能提高29.7%~38.9%的压缩位图索引性能。     

一种列存储数据仓库中的数据复用策略

数据复用是数据仓库管理中节约存储空间、提高查询效率的重要手段.列存储技术将来自同一属性的数据连续存储,极大地提高了数据仓库等分析型应用软件的性能,同时增加了复用的可行性和灵活性.为此,提出了一种列存储数据仓库中的数据复用策略.首先,利用模式匹配技术发掘候选可复用列,排除大量无法复用的数据列,在此基础上对候选可复用数据进行筛选和过滤,大大降低复用数据检测的复杂度.针对确定的可复用数据,提出了基于列存储的复用实现策略,分别给出了原始数据列、压缩数据列及索引数据列的复用实现方法.最后提出了基于复用数据的查询实现技术.在大规模数据仓库基准数据集上的实验结果验证了数据复用策略在减少存储量、节省数据装载时间及提升查询性能方面的有效性.     

基于列存储机制下多维数据仓库模型的优化与研究

通过对分布式列存储机制下多维数据仓库模型的研究,考虑到多维数据仓库模型上的关联和聚集操作常常会引入大量的数据迁移,提出一种有效的列存储机制下多维数据仓库模型的优化方法即结合层次编码技术。采用维表层次全局域编码和维表层次局部域编码相结合的方式对传统星型模型维表中的层次信息进行二进制编码整合,将维表的层次信息压缩进事实表形成无连接星型模型,并针对新模型下的数据特征提出一种复合压缩策略,以期减少分布式列存储机制下的OLAP操作引入的数据迁移并降低数据存储空间,提升系统的查询性能。实验结果表明,该优化方法是可行且有效的。     

列存储数据区级压缩模式与压缩策略选择方法

压缩技术是列存储数据管理的重要研究内容之一.目前多数方法对同一列数据使用单一压缩方法进行压缩,忽略了数据的局部分布特性,极大地影响了压缩性能.该文提出一种区级压缩模式,并在此模式下提出基于学习的压缩策略选择方法.首先该文将数据列进一步划分为区,并分别定义相邻区信息与区所在列的统计信息为参照信息,进而通过学习参照信息与当前区之间的相似性和差异性进行策略推荐.最后该文对区进行局部学习从而对推荐压缩策略进行修正,保证压缩策略的有效性.在数据仓库基准数据集SSB上的实验结果验证了该文方法的有效性.     

列存储系统面向列的连接顺序优化研究

连接操作是影响列存储数据查询效率的重要操作之一,对于列存储系统中的连接操作优化,以往的研究工作大多专注于对数据组织结构的优化以及辅助物理结构的建立上,极少涉及逻辑层特别是早期的连接策略优化.为此,根据列存储数据的特点和分析型查询需求的特征,提出了一种新的列存储连接优化方法.该方法采用提早优化的策略,使用“事实表下推”的优化规则,并在多事实表查询条件下引入浓密树进行连接顺序决策,以较小的时空复杂度获得“最优”的连接执行顺序.使用代价估计模型对提出的连接策略优化方法进行了理论验证.同时,在大规模数据仓库基准数据集SSB上通过实验验证了提旱优化机制及下推规则的有效性.     

基于列存储的MapReduce并行连接算法

针对传统关系型数据库在对大数据进行操作时,系统性能严重下降、计算效率提升有限以及可扩展性差等问题,引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce并行连接算法。设计面向大数据的分布式计算模型,包括MapReduce分布式环境下的列存储文件格式MCF,采用协同定位策略实现对分布式存储的优化。使用分片聚集和子连接启发式优化方法,实现大数据在MapReduce分布式环境下并行连接算法。实验结果证明,在大数据分析处理中,该算法在执行时间和负载能力上有着较好的优化性能,同时具有良好的可扩展性。     

大数据环境下数据读取关键技术研究

针对大数据环境下数据读取面临的主要挑战,文中重点研究了分布式文件系统中数据读取关键技术。根据数据存放结构的不同,从数据加载、查询处理和存储空间利用三个方面分析比较行存储、列存储和行列混合存储的优缺点和面临的挑战,重点介绍列存储中涉及到的压缩和物化技术,具体分析了存储压缩中经常运用的行程编码算法、词典编码算法、位向量编码算法和元组重构中运用的延迟物化技术。通过分析现有技术存在的问题,探讨相关的解决方案,并展望了未来研究的发展方向。     

使用MapReduce构建列存储数据的索引

大数据的存储与分析是近年来数据库领域研究的热点,高效的索引技术是提高大数据查询分析性能的重要技术手段。在现有的数据存储模型及索引技术研究基础上,提出使用MapReduce构建列存储数据的索引。该索引技术结合MapReduce编程模型,先在Map阶段完成数据划分,然后在Reduce阶段完成数据的排序,最后在数据有序的Reduce节点上创建RB+树索引,从而减少索引创建时因为RB+树内部节点递归分裂而产生的昂贵代价和树的高度,提高数据查询的性能。通过在真实数据集上进行实验,验证了所提出方法的有效性。     

一个基于三元组存储的列式OLAP查询执行引擎

大数据与传统的数据仓库技术相结合产生了大数据实时分析处理需要（volume+velocity）,它要求大数据背景下的数据仓库不能过多地依赖物化、索引等高存储代价的优化技术,而要提高实时处理能力来应对大数据分析中数据量大、查询分析复杂等特点.这些查询分析操作一般表现为在事实表和维表之间连接操作的基础上对结果集上进行分组聚集等操作.因此,表连接和分组聚集操作是ROLAP（relational OLAP）性能的两个重要决定因素.研究了新硬件平台下针对大规模数据的OLAP查询的性能,设计新的列存储OLAP查询执行引擎CDDTA-MMDB（columnar direct dimensional tuple access-main memory databasequeryexecutionengine,直接维表元组访问的内存数据库查询执行引擎）.基于三元组的物化策略,使得CDDTA-MMDB能够减少内存列存储模型上表连接操作访问基表和中间数据结构的次数.首先,CDDTA-MMDB将查询分解为作用在维表和事实表上的子查询,如果只涉及过滤操作,子查询将生成<代理键,布尔值>二元组;否则,子查询生成<代理键,关键字,值>三元组.然后,只需一趟扫描事实表,利用事实表的外键映射函数直接定位相应三元组或者二元组,完成相应的过滤、连接或聚集操作.CDDTA-MMDB充分考虑了内存列存储数据库的设计原则,尽量减少随机内存访问.实验结果表明：CDDTA-MMDB是高效的,与具代表性的列存储数据库相比,比MonetDB 5.5快2.5倍,比C-store的invisible join快5倍;并且,CDDTA-MMDB在多核处理器上具有线性加速比.     

基于间隔链表改进的频繁项集挖掘算法

针对PrePost算法中需要建立复杂的前序和后序编码树(PPC-tree)和节点链表(N-list)的问题,提出一种基于间隔链表(I-list)改进的高效频繁项集挖掘算法。首先,该算法采用了比频繁模模式树(FP-tree)更加压缩的数据存储结构间隔编码的频繁模式树(IFP-tree),无需迭代地建立条件FP-tree;其次,该算法利用更简洁的I-list代替了PrePost中复杂的N-list,从而提高了建树和挖掘速度;最后,对于单分支路径的情况,该算法通过组合的方法,直接求得某些频繁项集,以提高算法的时间性能。实验结果表明:一方面,对于同一数据集在相同支持数下挖掘的结果相同,验证了改进算法的正确性;另一方面,无论在时间还是空间上改进算法的整体性能均比PrePost算法提高约10%;且对于稀疏型数据库或密集型数据库的挖掘都有较好的应用。     

基于三层存储模型的RFID数据压缩存储方法

针对物联网技术中亟待解决的海量数据存储问题,提出了一种基于射频识别(RFID)的三层数据存储压缩模型。该模型将数据分为当前数据层、临时数据层和历史数据层,利用每一层中数据的特点分别设计了相应的数据汇总算法,最终实现RFID数据的压缩存储。在该模型的基础之上,提出了针对路径的编码算法,用于对路径进行压缩存储。实验结果表明,该三层存储模型可以有效地压缩存储RFID数据,同时数据汇总算法具有较低的时间复杂度与较高的数据压缩比。     

基于谓词索引的海量数据压缩存储及数据操作算法

压缩数据库技术是海量数据管理的重要技术之一.利用海量数据自身及其数据操作的特点,提出了一种海量数据压缩存储结构.该存储结构将第二级和第三级存储器结合起来,以数据操作条件中的谓词为索引,在减少存储空间的同时有效地支持查询、删除和更新等数据操作.理论分析和实验结果表明,这种存储结构可以提高海量数据的存储效率和数据操作的性能.     

基于改进科学计算浮点数压缩算法的工业远程监控数据无损压缩方法

为解决大量工业远程监控数据在通用分组无线服务(GPRS)网络上的传输延迟问题,提出了基于改进科学计算浮点数压缩(FPC)算法的工业远程监控数据无损压缩方法.首先,根据工业监控数据中浮点数部分的特点对原FPC算法中的预测器结构进行改进,并将该改进算法作为浮点数部分的压缩算法; 然后,与区间编码相结合作为整个数据域的压缩方法.改进前后的浮点数部分压缩实验结果表明改进的FPC算法提高了预测器的预测精度,且在保持较高压缩效率的同时提高了压缩率.与通用无损压缩算法相比,所提算法提高了12%以上的平均压缩率,减少了38.5%以上的平均压缩时间,使得传输时间降低了23.7%以上,在传输数据量大且传输速率不高的情况下大大提高了监控的实时性.     

基于W学习的无线网络传输调度方案

针对无线网络的传输问题,提出了一种适用于无线网络的智能传输调度方案,在马尔可夫决策过程(MDP)的基础上构建了系统模型,通过W学习算法的引入,中继节点对缓存器储存状态及信道质量进行学习,从而在信息数据包的传输过程中智能地选择数据包传输对象及数据包传输方式来达到在节省能量损耗的前提下尽量减少数据包丢失的目的。通过状态聚合方法解决因状态空间过大而导致的维灾问题,同时采用了行动集缩减来以减少某些状态对应的行动数,利用这些简化方法可以发现逐次逼近法的存储空间压缩率为41%,W学习算法的存储空间压缩率为43%。最后,系统仿真结果表明,提出的传输调度方案可以在节省能耗的基础上尽量地传输数据,减少了数据包的丢失,同时采取的状态聚合法及行动集缩减在有效地简化计算的同时并没有影响算法的性能。     

基于小型Zynq SoC硬件加速的改进TINY YOLO实时车辆检测算法实现

针对TINY YOLO车辆检测算法计算量过大，且在小型嵌入式系统中难以达到实时检测要求的问题。利用小型Zynq SoC系统的架构优势以及TINY YOLO的网络权值中存在大量接近零的权值参数这一特点，提出硬件并行加速的改进算法，称为浓缩小型深度网络（Xerantic-TINY YOLO，X-TINY YOLO）车辆检测算法。首先对TINY YOLO中网络结构进行压缩；其次采用高效多级流水线、流水线内全并行的方式对卷积计算部分进行算法加速；最后提出与网络结构相配合的数据切割和传输方案。实验结果表明，X-TINY YOLO仅消耗50%的片内硬件资源，可在相对于GPU和CPU性价比更高更适合嵌入式场景的Zynq SoC系统上实现，且其检测速度达到24帧/s，满足车辆检测的实时性要求。     

一种基于循环神经网络的极化码BP译码算法

置信传播（BP）算法作为极化码最常用的软判决输出译码算法之一,具有并行传输、高吞吐量等优点,但其存在收敛较慢、运算复杂度高等缺陷。提出一种基于循环神经网络的偏移最小和近似置信传播译码算法。通过偏移最小和近似算法替代乘法运算,修改迭代过程中的消息更新策略,并运用改进的循环神经网络架构实现参数共享。仿真结果表明,相比传统BP译码算法,该译码算法在提升误码率（BER）性能的前提下,减少约75%的加法运算且收敛速度大幅提升,相比基于深度神经网络的BP译码算法,该算法在确保BER性能无显著下降的前提下,使用加法运算替代乘法运算,节省了约80%的存储空间开销。     

基于哈希学习的投票样例选择算法

随着数据的海量型增长，如何存储并利用数据成为目前学术研究和工业应用等方面的热门问题。样例选择是解决此类问题的方法之一，它在原始数据中依据既定规则选出代表性的样例，从而有效地降低后续工作的难度。基于此，提出一种基于哈希学习的投票样例选择算法。首先通过主成分分析（PCA）方法将高维数据映射到低维空间；然后利用k-means算法结合矢量量化方法进行迭代运算，并将数据用聚类中心的哈希码表示；接着将分类后的数据按比例进行随机选择，在多次独立运行算法后投票选择出最终的样例。与压缩近邻（CNN）算法和大数据线性复杂度样例选择算法LSH-IS-F相比，所提算法在压缩比方面平均提升了19%。所提算法思想简单容易实现，能够通过调节参数自主控制压缩比。在7个数据集上的实验结果显示所提算法在测试精度相似的情况下在压缩比和运行时间方面较随机哈希有较大优势。     

基于线性动态系统的视频压缩感知自适应改进

线性动态系统的视频压缩感知(CS-LDS)是指从随机采样数据中直接估计出模型参数,然而对所有视频帧采取同样的采样方式,使得采样数据存在一定的时间冗余.针对这一问题,结合自适应压缩采样技术提出了一种自适应的改进算法.首先,对视频信号建立线性动态系统(LDS)模型;然后,通过自适应压缩采样方法得到视频信号的采样数据;最后,通过采样数据估计出系统模型参数,实现视频信号的重构.实验结果表明,在不影响视频重构质量的条件下,所提方法相对于CS-LDS算法,不仅能够节省统一测量过程中20%~40%的采样数据,而且平均每帧能够节省0.1~0.3 s的运行时间.改进后的算法降低了采样数目与算法运行时间.     

基于中医方剂数据库的Top-Rank-k频繁模式挖掘算法

为降低中医（TCM）方剂频繁模式挖掘过程中对经验参数的依赖,提高挖掘结果的准确性,针对中医方剂的数据特点,提出一种基于带权无向图的Top-Rank-k频繁模式挖掘算法。该算法可以直接挖掘出频繁k-itemset（k≥3）而无需产生1-itemset和2-itemset,并随之快速回溯到核心药物组合的频繁项集所对应的方剂信息;此外,采用一种动态位向量（DBV）的压缩机制对无向图中边的权重进行压缩存储,以有效地提高算法的空间存储效率。分别对中医方剂数据集、真实数据集（Chess、Pumsb和Retail）和合成数据集（T10I4D100K和Test2K50KD1）进行测试和比较,结果表明该算法与iNTK和BTK相比具有更高的时间和空间效率,而且也可以应用于其他类型的数据集。