导读:本文包含了压缩索引论文开题报告文献综述及选题提纲参考文献，主要关键词:GPU,渲染管线,顶点索引,绘制模式
压缩索引论文文献综述
王可,杜慧敏,黄虎才,刘世豪,刘鑫[1]（2019）在《图形渲染管线中顶点索引压缩方法》一文中研究指出提高性能和降低功耗一直以来都是高性能GPU的关键技术所在。在图形渲染管线中,访问外部存储器是必不可少的操作之一,但是频繁地访问存储会导致系统性能降低,功耗增大。因此,在图形处理流水线中采用数据压缩是一种常用的手段,通过数据压缩可以减少数据传输位宽,减少访问外部存储的次数,相应地提高系统性能。论文在分析和总结渲染管线的绘制模式和顶点索引的数据特征的基础上,提出了一种针对顶点索引存储优化的方法,可以大幅度减少顶点索引的存储空间,提高其利用率。论文对提出的压缩算法进行了建模,并搭建了System Verilog的仿真平台对不同测试用例下的顶点索引进行了仿真,统计其压缩比。由测试结果得出,该方法可以较好地减小存储资源的占用。(本文来源于《计算机与数字工程》期刊2019年11期）
安兆翔[2]（2019）在《基于模式化编码的倒排索引压缩算法研究》一文中研究指出倒排索引是信息检索系统的重要组成部分之一,被用于维护数十亿文档并对大量查询操作进行响应。随着当前互联网数据量的不断增加,倒排索引的体积也不断攀升。倒排索引压缩算法可以提高信息检索系统的性能,减少索引的空间占用,加快查询处理速度,因而成为了重要的研究对象。模式化编码相比传统的位编码具有解码速度快,压缩效果好的优点,因而被广泛应用于倒排索引压缩中。本文针对模式化编码中的字节对齐编码算法、固定比特编码算法以及字对齐编码算法进行深入研究,主要工作如下:(1)本文对字节对齐编码和固定比特编码的特点进行剖析,并以此为基础提出了 PVU编码压缩算法。算法以字节对齐编码为基础,引入了固定比特编码中的分区思想,使用“模式区-长度区-编码区”的叁层存储结构对字节对齐编码中的二层结构加以改进。算法代替以字节为最小存储单位的单一方式,设计了多种最小存储单位供各分区选取最优的压缩模式,从而提高了全局压缩率。针对PVU编码的分区策略进行研究,将编码分区问题转换为图论中的最短路径问题,设计并实现了动态规划求解编码最优分区的方法,并提出了分区优化的OptPVU编码。(2)分析DocID序列经预处理后的取值分布特征,以字对齐编码Simple Family为基础,融合游程编码加以改进,提出了 Simple21编码压缩算法。算法包含21种编码模式,当序列包含大量连续0值时,Simple21编码相比其它Simple Family编码有效减少了占用空间。Simple21编码还通过将模式标识符和压缩编码分割的方式,增加了编码的最大存储长度,扩大了算法的可用范围。(3)本文提出并实现了 PVU编码、分区优化的OptPVU编码以及Simple21编码叁种倒排索引压缩算法,并与Golomb编码、Elias-Delta编码,Variable Byte编码、Stream VByte编码、NewPFD编码和Simple9编码进行了对比实验。实验结果表明,Simple21编码在压缩率和解码速度方面均优于其它压缩算法,是实验中综合效果最优的编码方案。PVU编码、OptPVU编码相比字节对齐编码VByte和Stream VByte,在压缩率上取得了明显的优势。与固定比特编码NewPFD相比,PVU编码与NewPFD编码具有相似的压缩效果,而经分区优化的OptPVU编码则取得了比NewPFD编码更好的压缩率和解码速度。(本文来源于《北京交通大学》期刊2019-05-01）
安兆翔,瞿有利[3]（2019）在《编码单位可变的倒排索引压缩算法研究》一文中研究指出倒排索引是大多数大型文本搜索系统的核心数据结构,索引压缩可以有效地减少倒排索引的空间占用,提升检索效率。针对倒排索引压缩算法中的字节对齐编码进行研究,对于其压缩率不够优秀的问题,提出了分区可变单位编码(PVU编码)。算法以可变单位方式代替固定字节存储,使实际存储空间更加贴合原码长度,从而提高压缩效果。针对序列均匀分区并非最优分区的问题,提出将最优分区问题转化为图论中最短路径问题的方法,使用Dijkstra算法求解序列的最优编码分区。通过对比实验验证了改进优化的PVU编码相较于传统的字节对齐编码能够更好地压缩倒排索引序列。(本文来源于《计算机工程与应用》期刊2019年15期）
李高超,李犇,卢毓海,刘梦雅,刘燕兵[4]（2018）在《基于二级索引结构的图压缩算法》一文中研究指出目前,各领域对图数据的分析、应用需求日益增加,且对结构复杂、耦合度高的大规模图数据的管理面临着速度低下和空间开销大的双重挑战。面对图数据管理中查询耗时高和空间占比大的难题,提出一种图数据二级索引压缩算法——GCom Idx。该算法利用有序的键值(Key-Value)结构将相关节点和边尽可能地以相邻的方式存储,并为高效的属性查询和邻居查询分别构造二级索引和hash节点索引。此外,为了节省存储空间,GCom Idx算法采用压缩算法来降低图数据磁盘空间占用率。实验结果表明,GCom Idx算法能够有效降低图数据计算的初始化时间和图数据存储的磁盘空间占用,且查询时间小于通用数据库和其他Key-Value存储方案。(本文来源于《通信学报》期刊2018年06期）
宋省身[5]（2018）在《时空高效的倒排索引压缩和求交算法研究》一文中研究指出随着互联网的发展,各类信息的体量规模增长也越来越快。日益壮大的数据体积和用户数量也为各类信息系统,尤其是搜索引擎带来了严峻的考验。应对这类挑战的关键措施是提升系统在数据爬取收集、整理压缩以及查询应答的效率,而倒排索引作为信息检索底层最常用的数据结构,(负责对信息进行组织管理和查询处理),对检索效率和系统运营成本有着至关重要的影响。因此,针对倒排索引的压缩和查询优化已经成为信息检索领域一个重要的研究课题。为此,本文针对倒排索引的压缩和查询效率问题,重点研究了设计时空高效的压缩算法和并行求交算法。本文的主要成果如下:1.为了提升压缩算法的压缩速度,本文将面向分块的压缩算法所使用的分块划分问题归纳为了在单源有向无环图上的最短路径问题,并改进优化了AFOR和VSEncoding压缩算法所使用的分块划分策略,包括为AFOR增加分块的折迭合并和使用近似算法替代VSEncoding的动态规划,提升其压解速度的同时维持了相同水平的压缩率。本文还提出了自启发式划分的Elias-Fano索引压缩算法,针对PEF索引使用多个滑动窗口反复遍历倒排链的缺点,该方法根据分块的长度和压缩代价增量的变化,仅需一个滑动窗口探测异常值并完成划分,在损失了轻微的压缩率和解压速度的代价下,极大地提高了压缩速度。实验结果表明,本文提出的压缩算法相比优化前的算法在压缩/解压缩速度-压缩率对应的时空曲线上能达到更优的位置。2.本文提出了双权重标准压缩算法的概念,针对近年来融合多种压缩算法的混合式索引,本文将最优地分配压缩算法到各个分块的问题,归纳为了资源受限的双权重有向无环图的最短路径问题,对应的权重为压缩大小和解压缩时间,并借助于拉格朗日松弛算法寻找压缩算法的最优分配方案。相比于现行的方案,本文的算法仅需要O(n log n)的时间和O(n)空间进行求解,同时结果与最优解之间仅保留加性误差。除此以外,我们还探索了使用动态规划对倒排链进行变长分块,将完成分配的分块按照相似度准则进行合并,进一步提升了查询效率。实验结果表明,本文提出的压缩算法分配算法能够动态地调整倒排索引的时空特性,使之适应实际应用中索引设计者对空间/时间的任一要求。3.针对倒排链的求交算法,本文首先回顾了传统的多倒排链求交算法以及近年来提出的基于SIMD的并行求交算法,归纳分析了影响求交算法的两个因素,即排除项选择方式和倒排链的搜索算法。由于当前基于SIMD的并行求交算法都是针对倒排链两两相交设计的,并未利用到传统的多倒排链求交算法。为此,我们提出了基于SIMD的多倒排链并行求交算法,由于它采用线性搜索,对于长倒排链的效果并不是很好。为了继续提高算法效率,我们首先研究了使用AVX2提供的收集指令同时收集倒排链中离散位置的元素与排除项同时进行比较,用于加速跳查过程;随后提出了基于双尺度自适应变换搜索窗口的搜索算法,相比于先行算法简单地使用经验参数,我们的搜索算法更针对参与倒排链的长度自动匹配最优的搜索参数,极大地提高了倒排链求交的性能。(本文来源于《国防科技大学》期刊2018-06-01）
荣河江[6]（2018）在《基于自索引结构的高通量基因组重测序数据压缩算法》一文中研究指出测序技术的进步,使得人们对基因组测序的兴趣日益增加。早期测序技术需要几年的时间来捕获30亿个核苷酸的基因组,目前新一代测序技术在数天内就可以对220亿个核苷酸的基因组进行测序。在测序速度提升的同时,测序成本也直线下降。基因组测序在个性化医疗和公共健康中日益发挥着重要的作用。越来越多的基因组测序数据在不断产生,这些数据需要进行有效的存储、传输和分析。如何解决高速增长的数据与有限的存储空间的矛盾,成为重要的研究课题。DNA数据压缩为解决问题提供了一种有效思路。但由于DNA数据自身的特点,传统的压缩方法难以达到很好的压缩效果。本文针对上述问题,在前两章调研了现有的高通量数据压缩技术,并对相关的压缩算法原理和以及面临的挑战进行分析,最后提出了改进的高通量数据压缩算法。本论文做了如下几件工作:(1)调研了高通量测序数据集的存储格式,以及现有的压缩算法。分析了测序数据的生物特性,同时通过分析表明,对质量分数的有损压缩,在提高压缩性能的同时,在下游分析中还能保持较好(有时甚至更优)的性能。(2)在基于参考基因组进行差异化压缩编码的方案基础上,采用垂直方向的编码方式,同时对质量数采用稀疏化处理和均值处理相结合的方式,获得较好的有损压缩性能,实验表明压缩效果更优。(3)针对数据需要随机解压缩和快速检索的需求,在分析自索引压缩技术原理的基础上,提出基于PBWT数据结构的自索引压缩技术,实验表明,自索引技术的引入,在随机解压缩上有较好的性能。本文在基于参考基因组的压缩算法基础上,提出了基于自索引结构的随机解压缩算法,在压缩效率上有一定的优势,同时可以满足局部检索和解压缩的需求。这在一定程度上可以缓解海量高通量数据的存储和传输压力,为后续相关研究提供经验和借鉴。(本文来源于《哈尔滨工业大学》期刊2018-06-01）
马柏林[7]（2018）在《激光点云数据索引和压缩方法研究》一文中研究指出叁维激光扫描技术是一种先进的全自动高精度立体扫描技术,高精度叁维模型已在各行各业中取得了广泛应用,因此对于点云数据处理方法的研究尤为重要。本文在对叁维激光扫描技术的原理以及点云数据处理技术研究的基础上,对点云数据索引以及点云数据压缩的经典算法进行改进,以获得高效的点云数据查询效率以及高精度的点云数据压缩质量。点云数据索引主要有格网索引、KD树索引、R树索引、八叉树索引、四叉树索引等方法,其中四叉树索引具有较好的索引效率,但是在索引过程中存在树深较大、四叉树存储冗余、堆栈溢出等问题。因此本文对四叉树索引进行改进,首先根据点云数据的跨度对点云数据进行分块,然后对分块后的点云数据进行四叉树索引,在四叉树索引时,引入自定义堆栈以及最小外包矩形的概念,从而对点云数据的四叉树索引结构进行良好的改进,经与传统的四叉树结构进行实验对比分析,改进的点云数据索引具有良好的建树效率以及查询效率。点云数据压缩方法主要有曲率采样法、随机采样法、均匀网格采样法、坐标增量法、区域重心法等方法,其中区域重心法具有较好的压缩精度,但是在压缩过程中会造成一些物体表面细节特征丢失,因此本文对区域重心法进行改进,首先对点云数据进行包围盒的构建,再根据划分阈值将包围盒划分为若干个子包围盒,然后对子包围盒内的点云数据求取代重心点,再对其余点根据点到最近邻平面的阈值进行删除,然后对保留的点根据点到重心的距离进行二次删除,最终完成点云数据压缩,经过与区域重心采样以及其他压缩算法进行对比,改进算法改善了压缩质量,保证了数据简度,提高了叁维模型构建精度。(本文来源于《西安科技大学》期刊2018-06-01）
白福均[8]（2018）在《云环境下全文索引压缩关键技术研究》一文中研究指出随着网络技术和信息技术迅猛发展,社交网络、电子商务、资讯信息流、网络游戏以及多媒体视听内容空前繁荣,其中以文本为载体的信息呈现出爆炸式的增长,人们逐步被淹没在数据汪洋里。如何在数据汪洋中快速的检索到所需的有用是亟待解决的难题,因此信息检索已成为当下最热研究领域之一。全文索引是检索引擎、信息过滤等信息检索领域中的关键技术,它是实现快速信息检索的关键数据结构,然而存储索引本身所需的磁盘空间开销为原始语料库的数倍,这不但会造成巨大的磁盘空间浪费,而且也是影响检索性能优劣的重要原因之一。因此,研究全文索引压缩算法具有重要的意义,因为压缩全文索引不仅可以降低索引的磁盘空间开销,同时也可以在检索时减少磁盘I/O开销以提高检索性能。本课题对全文索引中目前应用最广泛的倒排索引的压缩算法进行了深入研究,主要工作如下:从理论上分析了目前典型的倒排索引压缩算法磁盘空间占用情况;基于文本聚类思想提出了一种文档标识符分配算法;提出了自适应分段压缩ASCS算法的四种改进方案,即针对ASCS算法中的分段方式并非最优分段问题,提出了以人工蜂群算法优化分段方式,改进了蜜源的适应度计算公式,使用压缩性能更好的DGap序列进行压缩,对分段参数使用Golomb Rice编码压缩;由于在引入人工蜂群优化算法对ASCS算法优化时存在一个相对耗时的迭代寻优过程,在大数据背景下,使用Hadoop分布式云框架对算法进行并行化。本文对改进后的算法使用Java语言进行了实现,通过9个不同的整数序列验证了算法改进的有效性;通过引入Hadoop分布式云框架对算法实施并行化,在两个标准TREC语料库GOV2和ClueWeb09下验证了并行化的有效性。(本文来源于《贵州大学》期刊2018-06-01）
徐芹宝[9]（2018）在《WSN中基于路径索引差分的溯源数据压缩方法》一文中研究指出在无线传感器网络(Wireless Sensor Network,WSN)中,溯源(Provenance)记录数据的产生、处理以及传输等历史信息,是进行数据可信性评估、网络异常检测等操作的重要依据。但是,Provenance会随着数据包传输路径的增长而迅速膨胀。由于WSN在能量以及传输带宽等资源方面受限,因此无法直接传输数据量较大的Provenance。为了解决Provenance数据量过载问题,多种Provenance的压缩方法被相继提出。在这些方法中,基于字典的Provenance方法具有最高的压缩比,但该方法对网络拓扑结构变化敏感,使其应用范围受限。针对字典Provenance方法的不足,本文提出一种基于路径索引差分的Provenance编码方法。在本方法中,首先,运用向量场论以及概率论中的相关知识,以WSN中每一个数据源节点为起点,沿着趋向于基站(Base Station,BS)的梯度方向建立骨干路径;其次,使用本文提出的一种“折断海明距离”路径去重方法对网络中的骨干路径进行去重,并对去重后的骨干路径建立字典;最后,当网络中出现新数据包传输路径时,不再对新数据包传输路径建立字典,而是在节点上运用基于SimHash的相似度比较方法检索与其最相似的字典中的路径。在找到与新数据包传输路径最相似的路径后,将新数据包传输路径表示成为与其最相似路径的索引差分形式,从而进一步提高Provenance的平均压缩比。软件仿真以及硬件组网实验结果均表明,本文提出的基于路径索引差分的Provenance编码方法不仅可以有效克服已知的Provenance编码方法对网络拓扑结构变化敏感的问题,而且可以实现更高的Provenance平均压缩比。(本文来源于《江苏大学》期刊2018-04-01）
郭文钰[10]（2018）在《全文自索引压缩算法的研究》一文中研究指出随着互联网技术的不断发展,网络信息爆炸式地增长,繁杂的文本数据带给人们便利的同时,也给文本检索带来巨大的挑战。倒排索引技术虽然能解决部分需求,但当分词不准确或者无法进行分词时,就会导致检索的精准度出现问题。全文自索引算法不是以“词”的粒度来分割文本,而是以文本的单个符号进行分割,可以解决精准匹配的问题。全文自索引所占有的空间是原文本所占空间的4～20倍,造成非常大的空间浪费,所以全文自索引压缩算法对全文检索有着重要的意义。本文研究了后缀数组、rank/select/access操作、BWT数据轮转算法、小波树和整数编码压缩算法,在此基础上设计高效的全文自索引压缩算法,主要工作如下:(1)本文在Sad-CSA算法的基础上,利用其上下文划分的理念,保存一层上下文结构,提出了 PEF-CSA自索引压缩算法。该算法利用Partitioned-Elias-Fano编码压缩算法对后缀数组转化而成的间断单调递增的近邻数组φ进行压缩,并采用二级压缩结构得到良好的压缩效果和查询性能。(2)本文在原始FM-Index算法基础上提出了 Adaptive-FM-Index自索引压缩算法。将原文本T经过BWT数据轮转得到T~(bwt）,利用Huffman小波树结构存储T~(bwt),得到HWT(T~(bwt)),将HWT(T~(bwt))每个节点存储的bit串划分得到超块与块的两级结构,提升了查询的速度,并且根据块的数据分布特点,选取自适应的编码方式,提升了压缩性能,结合采样后缀数组与采样名次数组的辅助结构提供高效的自索引结构。(3)本文实现了 PEF-CSA自索引压缩算法和Sad-CSA压缩算法、RL-CSA压缩算法、SDSL-CSA算法。实验表明,PEF-CSA自索引压缩算法的压缩率和计数查询性能是CSA算法中最优的,定位查询性能也高于大多数CSA算法。实现了Adaptive-FM-Index 自索引压缩算法,并且实现了 FM-RRR 算法、FM-uncompressed算法、FM-hybrid算法、RLFM算法。实验表明,Adaptive-FM-Index自索引压缩算法的压缩率,计数查询性能与定位查询性能都普遍好于其他FM-Index算法,并且在字符频率失衡的数据集上压缩效果更好。Adaptive-FM-Index自索引压缩算法压缩率优于PEF-CSA自索引压缩算法,但在english类的平衡数据集上,PEF-CSA自索引压缩算法的压缩率更低,PEF-CSA自索引压缩算法的定位查询性能优于Adaptive-FM-Index自索引压缩算法。(本文来源于《北京交通大学》期刊2018-03-01）
压缩索引论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
倒排索引是信息检索系统的重要组成部分之一,被用于维护数十亿文档并对大量查询操作进行响应。随着当前互联网数据量的不断增加,倒排索引的体积也不断攀升。倒排索引压缩算法可以提高信息检索系统的性能,减少索引的空间占用,加快查询处理速度,因而成为了重要的研究对象。模式化编码相比传统的位编码具有解码速度快,压缩效果好的优点,因而被广泛应用于倒排索引压缩中。本文针对模式化编码中的字节对齐编码算法、固定比特编码算法以及字对齐编码算法进行深入研究,主要工作如下:(1)本文对字节对齐编码和固定比特编码的特点进行剖析,并以此为基础提出了 PVU编码压缩算法。算法以字节对齐编码为基础,引入了固定比特编码中的分区思想,使用“模式区-长度区-编码区”的叁层存储结构对字节对齐编码中的二层结构加以改进。算法代替以字节为最小存储单位的单一方式,设计了多种最小存储单位供各分区选取最优的压缩模式,从而提高了全局压缩率。针对PVU编码的分区策略进行研究,将编码分区问题转换为图论中的最短路径问题,设计并实现了动态规划求解编码最优分区的方法,并提出了分区优化的OptPVU编码。(2)分析DocID序列经预处理后的取值分布特征,以字对齐编码Simple Family为基础,融合游程编码加以改进,提出了 Simple21编码压缩算法。算法包含21种编码模式,当序列包含大量连续0值时,Simple21编码相比其它Simple Family编码有效减少了占用空间。Simple21编码还通过将模式标识符和压缩编码分割的方式,增加了编码的最大存储长度,扩大了算法的可用范围。(3)本文提出并实现了 PVU编码、分区优化的OptPVU编码以及Simple21编码叁种倒排索引压缩算法,并与Golomb编码、Elias-Delta编码,Variable Byte编码、Stream VByte编码、NewPFD编码和Simple9编码进行了对比实验。实验结果表明,Simple21编码在压缩率和解码速度方面均优于其它压缩算法,是实验中综合效果最优的编码方案。PVU编码、OptPVU编码相比字节对齐编码VByte和Stream VByte,在压缩率上取得了明显的优势。与固定比特编码NewPFD相比,PVU编码与NewPFD编码具有相似的压缩效果,而经分区优化的OptPVU编码则取得了比NewPFD编码更好的压缩率和解码速度。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
压缩索引论文参考文献
[1].王可,杜慧敏,黄虎才,刘世豪,刘鑫.图形渲染管线中顶点索引压缩方法[J].计算机与数字工程.2019
[2].安兆翔.基于模式化编码的倒排索引压缩算法研究[D].北京交通大学.2019
[3].安兆翔,瞿有利.编码单位可变的倒排索引压缩算法研究[J].计算机工程与应用.2019
[4].李高超,李犇,卢毓海,刘梦雅,刘燕兵.基于二级索引结构的图压缩算法[J].通信学报.2018
[5].宋省身.时空高效的倒排索引压缩和求交算法研究[D].国防科技大学.2018
[6].荣河江.基于自索引结构的高通量基因组重测序数据压缩算法[D].哈尔滨工业大学.2018
[7].马柏林.激光点云数据索引和压缩方法研究[D].西安科技大学.2018
[8].白福均.云环境下全文索引压缩关键技术研究[D].贵州大学.2018
[9].徐芹宝.WSN中基于路径索引差分的溯源数据压缩方法[D].江苏大学.2018
[10].郭文钰.全文自索引压缩算法的研究[D].北京交通大学.2018