基于重叠分块的FM-index性能研究与分析

FM-index压缩查询方法结合压缩技术和索引技术,其最大优势是能够在不解开压缩文件的情况下对源文件进行查询。该文通过理论分析和详细的测试数据研究重叠分块对FM-index压缩查询性能的改善。对改进后的FM-index和压缩软件Winrar在压缩时间和文件占用空间上进行分析和比较,进一步证明了重叠分块对FM-index压缩查询性能的改善。     

FM-index算法性能测试及并行化

介绍了FM-index压缩查询技术,详细阐述了FM—index的工作流程,描述了实现计算字符串在压缩文本中出现次数的算法。对FM-index的源代码在Linux平台上进行了测试,从测试结果分析了使用FM-index进行压缩查询的优点和不足。最后给出了加快FM-index压缩速度的一个并行化算法的初步设计思路。     

基于自索引的DBF压缩查询工具研究*

介绍了DBF表的文件格式和基于自索引的全文查询算法FM-index。针对DBF文件同时包含二进制文件头和纯文本数据记录的特点,以及对查询结果的特定要求,扩充了现有的FM-index算法,使其支持对DBF文件的压缩查询。测试结果表明,虽然FM-index在压缩/解压时间上与WinRAR仍有一段差距,但是FM-index对压缩查询功能的支持大大提高了文件的查询性能。     

FM-index压缩查询算法解析

FM-index 是目前信息检索领域中国际上比较领先的压缩查询方法。该算法是压缩技术和索引技术的结合,它的最大优势在于能够支持在不解开压缩文件的情况下对源文件进行查询。本文对 FM-Index 如何实现压缩,如何建立索引以及如何实现压缩状态下的查询和定位算法进行了详细的解析,并对该算法的核心部分用图示加以说明,为 FM-Index 算法的相关研究及在实际中能良好的应用和改进提供了参考。     

高效低索引的图相似性搜索算法

图相似性搜索是在给定的度量标准下查找与查询图相似的图集合,目前大多采用“过滤-验证”的计算框架。针对现有方法中过滤下界不紧密和索引空间占用较大等问题,提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z-Index。该算法首先通过全局粗粒度过滤得到预候选集;然后提出基于扩展概率的查询图分区算法,并采用层级过滤机制进一步精简候选集,增强下界紧密性;最后引入序列相似性差值计算序列中数据分布的稀疏度,提出分区压缩和差值压缩两种编码压缩算法,并据此构建“零”索引结构,降低索引空间开销。实验结果表明,Z-Index算法所得下界更加紧密,产生的候选集大小可减少50%左右,算法执行时间大大缩短,且该算法在索引空间占用极小的情况下仍具有可扩展性。     

基于内存的HBase二级索引设计

在大数据时代,具有海量数据存储能力的HBase已被广泛应用。HBase只对行键进行了索引优化,对非行键的列未建立索引,这严重影响了复杂条件查询的效率。针对此问题,提出了基于内存的HBase二级索引方案。该方案对需要查询的列建立了映射到行键的索引,并将索引存储在Spark搭建的内存环境中,在查询时先通过索引获取行键,然后利用行键在HBase中快速查找对应的记录。由于列的基数大小和是否涉及范围查询决定了建立索引的类型,故针对三种不同情况构建了不同类型的索引,并利用Spark内存计算、并行化的特点来提高索引的查询效率。实验结果表明,该二级索引具有较好的查询性能,查询时间小于基于Solr的二级索引,可以解决HBase中因非行键的列缺乏索引导致查询效率较低的问题,提高基于HBase存储的大数据分析的查询效率。     

ROLAP中星型模型的索引优化策略

目前主要有三种方法来提高ROLAP查询效率：聚集策略、即席查询策略以及采用高性能软硬件并行计算机系统结构。文中以暂住人口数据仓库为例，阐述如何利用索引来提高ROLAP的查询效率。主要讨论了位图索引和数据索引对ROLAP的查询优化，并从查询时间的长短以及数据占用存储空间的大小来比较这两种方法的优缺点。     

一种新的基于划分的结构连接算法

有效的结构连接是XML查询处理的关键。目前，大部分结构连接算法由于需要临时排序、建立索引或存在数据复制及I/O问题，大大降低了执行效率。该文在分析比较现有结构连接算法的基础上，提出了一种新的基于划分的结构连接算法。该算法不需要排序或建立索引，通过栈的机制解决了数据复制问题，并充分考虑内存缓冲提高了I/O性能。实验分析表明该算法具有良好的查询性能。     

一种基于路径分块索引的XML查询方法

针对XML的相对路径查询及引用路径查询问题，提出了一种面向XML数据的路径分块索引KI。探讨了KI索引构造方法、索引节点分裂算法和相关查询处理的算法，并用VC++实现，利用Shakespeare和Xorder数据集进行了XML查询测试，实验结果表明，提出的KI索引能有效地提高XML查询效率。     

高效的随机访问分块倒排文件自索引技术

针对倒排索引空间开销大、查询时间效率低以及难以同时支持连接布尔查询和排序查询的问题,提出了一种同时提高空间效率与查询时间效率的高效随机访问分块倒排文件自索引RABIF.为了在降低空间消耗的同时支持连接布尔查询与排序查询,RABIF将倒排列表进行合理地分块,然后对每个子块的不同部分采用相应的压缩方式,在不需要插入任何附加辅助信息的前提下实现压缩索引的快速定位与随机访问.理论分析及实验结果表明,与忽略倒排文件自索引SIF相比,提出的RABIF空间开销平均减少5.3%,布尔查询时间平均减少17.8%;对于0.2%与1%排序查询,查询时间分别平均减少34.4%与27.5%.     

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.     

基于图压缩的最大Steiner连通k核查询处理

研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1～2个数量级.     

基于压缩HMAC算法的传感器网络范围查询方法

传统范围查询方法主要针对一维数据,在感知节点上传的信息较多,导致能耗较高。提出一种基于压缩HMAC算法的两层无线传感器网络多维数据范围查询方法。使用AES对称加密算法生成数据密文及加密索引链,运用反向0-1编码和压缩HMAC算法生成最值比较链,反向0-1编码不需额外进行数值化处理,压缩HMAC算法能够缩短HMAC编码长度,从而减少感知节点的发送数据,降低感知节点的能量消耗。在AliOS Things Developer Kit开发板和iTOP-4412核心板上对该方法进行实验,并从单个周期采集数据个数、感知节点数据位数和采集数据维数3个方面与CSRQ等方法进行能量消耗对比分析,结果表明,该方法能保持数据的完整性,且能量消耗更少。     

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

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

传感器网络中节点个数约束查询处理算法

对传感器网络中一类新查询--节点个数约束查询,提出能量有效的查询处理算法.算法主要由查询下发和结果回收两部分构成.查询下发算法首先根据节点个数约束查询的特点提出相关节点选择以及基于Steiner树的查询下发算法.然后对该下发算法以及一种基于洪泛的能量有效查询下发算法的能量消耗进行分析,并对比两种算法的能量消耗从中选择适当的下发算法.结果回收算法提出直接和间接两种结果回收方式,并给出两种方式在进行结果回收时能够节省能量的条件.仿真实验表明,提出的能量有效节点个数约束查询处理算法能够在满足用户查询精度的同时,使其能量消耗低于其他查询处理算法.     

无线传感器网络Top-k多查询算法

针对无线传感器网络中多个Top-k查询问题,提出了一种Top-k多查询处理的算法,对接收到的多个Top-k查询请求进行预处理,预处理依据是约束条件,得出两类不同的查询集合:单约束条件的多查询和多约束条件的多查询。针对单约束条件的多查询提出了ETOP算法,该算法首先对排在时间序列最前面的Top-k查询请求进行基于网内处理,然后把查询结果存入基站缓存,并把结果的最小值设定为阈值传输到各个节点,再根据后续查询请求的查询范围进行相应的查询,从而快速地获得Top-k查询结果。实验表明:Top-k多查询方法在能够很好地实现查询的同时,减少了无线传感器网络中的传输消耗和能量消耗。     

一种有效的关系数据库压缩方法

海量关系中经常存在小值域属性,关系不仅在这些属性上的互不相同的值的数量很小,而且在这些属性的组合上的值域也很小.因此,海量关系在这些属性上有很多重复的组合值.一种提高数据库的存储和查询效率的重要方法就是消除这些重复取值.为此,提出了拆分压缩技术,它将海量关系拆分成两种较小的关系,其中一种关系的属性由小值域属性组组成,而另一种关系的属性是海量关系的其他属性.该方法的关键是小值域属性组的识别问题.在证明了这个问题的NP-完全性后,给出了两种在海量关系中识别小值域属性组合的算法,并在此基础上提出了海量关系拆分压缩技术,讨论了压缩关系的查询处理方法.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并可以提高数据库查询处理的整体性能.