分片位图索引:一种适用于云数据管理的辅助索引机制

云计算技术的快速发展为海量数据的存储和管理提供了可能.然而,由于存储模型的根本改变,传统关系数据库管理系统中成熟的索引技术既不能直接应用于海量数据的处理,也无法被简单地迁移到云计算环境中.通过分析对比辅助索引在云环境中的两种截然不同的基本逻辑结构,即集中式方案与分布式方案,在吸收两者的优势并规避其弱点的基础上,提出了具有良好可扩展性的分片位图索引机制,从而对云环境中海量数据的检索任务提供高效的支持.通过充分利用云环境中的并行计算资源,使单条查询的响应速度得到提升;与此同时,局部节点根据其所掌握的全局信息规避了不必要的检索开销从而使大量请求并发到达时的查询吞吐量得以保证.在真实数据上进行实验的结果表明,分片位图索引的查询性能大大优于其它方法.

利用位图索引加速大规模科学数据按需访问

在分析TB及以上规模复杂科学数据时,实现关键数据的快速定位是一项非常具有挑战性的任务.通过引进目前国际最新位图索引技术,设计并实现科学数据按需访问软件系统,综合利用分段、编码、WAH压缩等位图索引改进策略,减少索引尺寸规模和查询响应时间.通过实际数据性能结果表明,此方法可以将大规模科学数据的按需访问速度提高2～10倍.

基于压缩-字对齐位图的天文海量数据实时索引

澄江一米新真空大型天文望远镜(NVST)当前每天最大能产生2 TB,约十多万条的观测数据。由于这些数据量巨大并具有非结构化特性,使用离线构建索引会带来巨大时间开销,传统的关系型数据库难以满足快速索引和检索需求。针对这些问题,结合数据采集流程,提出了使用基于压缩的字对齐位图索引算法来在线实时构建索引。这种方式不仅克服了离线构建索引方式时,文件访问、FITS头读取和解析FITS头等操作带来的大量额外时间消耗问题,而且有助于解决海量太阳观测数据的高效检索难题。通过实验证明了在线实时构建索引方式能够极大地降低时间开销,也表明了该方式在天文海量数据索引和检索应用中的有效性和可行性。

数据仓库中一种基于维层次编码的位图索引方法

为了减少OLAP中的多表连接,压缩维属性连接关键字,对查询数据进行有效地分组聚集操作,来提高OLAP查询速度.利用维属性具有层次特性对维成员进行编码,生成其维层次编码,来代替维表中原关键字,实现了维表关键字的压缩.通过编码长度较小的维层次编码及其层次前缀路径,对维层次编码进行前缀匹配操作,快速检索出与查询关键字相匹配的维层次编码,求得维层次属性的查询范围,从而大大减少和简化了事实表与维表之间的多表连接,减少了I/O开销,提高了OLAP查询效率.

位图索引及其在数据仓库中的应用研究

介绍位图索引的原理及其在数据仓库中的应用,对位图索引的概念、特征、查询操作、编码压缩以及维护作了较为详细的描述,以便于在数据仓库中正确地使用位图索引,提高数据仓库的处理性能。

CB-LSH:基于压缩位图的高性能LSH索引算法

由于传统局部敏感散列(LSH)算法的删除性能不足,阻碍了LSH算法在实际产品中的应用.提出一种基于压缩位图的改进方法,通过引入压缩位图改良传统LSH算法的桶中数据结构,以及使用标记清除策略进行算法流程优化,解决传统LSH索引实时删除性能差的问题.理论分析证明:基于压缩位图的LSH(CB-LSH)算法可以显著降低算法的空间复杂度和时间复杂度.实验结果支撑了理论分析的结论,相对于传统LSH算法,CB-LSH在降低内存消耗的同时,可显著提高索引删除、数据插入和数据查询的性能.在大型项目中的应用实践验证了在线实时更新的海量多媒体数据检索系统中,CB-LSH索引算法对于多媒体数据的高维索引是有效可行的,并显著提升了性能、降低了资源消耗.

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

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

结合分段位图和B^+树的云数据索引机制研究

针对位图索引数据存储空间大、检索效率低的问题,提出了一种结合分段位图和B^+树的云数据索引机制(BBI)。BBI在索引创建时按照一定的基数对元组数据进行分段,以段为单位建立位图索引,索引数据量的决定因子由属性值的取值范围转变为分段数与基数的乘积,大大减少了索引数据量;同时,在每个数据节点上建立B^+树,避免了数据检索时对非结果数据的逐个遍历,从而显著提高了数据检索效率。实验结果表明,BBI索引是一种性能较优的云数据索引机制。

一种采用双向有序链表存储的动态编码位图索引方法

位图索引依据其独特的位向量编码方式,在数据检索中得到广泛使用。在对比分析位图索引结构中的简单位图索引和编码位图索引的基础上,提出了一种新的基于双向有序链表存储的动态编码位图索引方法,并给出了这一动态编码位图索引方法在数据插入、删除、更新和检索中的详细算法。最后,进行实验测试。结果表明,所提出的索引方法具有更好的执行效率。

一种利用位图索引求解成员查询的高效算法

在利用位图索引求解成员查询时 ,减少对位图的重复扫描可以有效地提高查询的效率 .本文提出了解决该问题的有效方案 ,给出了相应的算法 。

基于位图连接索引的复杂多维层次的连接和聚集算法

在ROLAP中往往涉及到大量数据的复杂即席查询，从SQL角度看，这些查询通常都包含多表连接和分组聚集操作。本文提出了一种连接和聚集操作的新算法JAMDHBJI，该算法充分考虑了ROLAP中复杂多维层次的特点，同时考虑到并非全部维都具有维层次的语义特性，将维层次编码和位图连接索引有效结合，把复杂的连接和分组聚集操作转化为在事实表上的区域查询，从而大大提高了连接和分组聚集的效率。理论分析表明该算法是高效的。

不精确位图索引中Bloom filter空间预估的一种方法

为了控制不精确位图索引的查询精度,根据位图索引查询结果中假阳元组所占的比率,提出了新的查询精度度量指标—查询假阳率,该指标可以准确反映不精确位图索引的查询精度,并容易被用户理解和设置.根据索引属性的基数、用户预期的属性选择率和查询假阳率,给出了一种预估Bloom filter空间大小的计算公式.实验结果表明,根据该计算公式确定的Bloom filter空间大小能很好地满足用户期望的查询精度.

位图索引的设计与实现

文章在分析了几种现有位图索引的基础上,为国产数据库系统DM设计了分段范围编码位图索引。最后介绍了DM位图索引的建立以及查询方法。

位图连接索引服务机制研究

位图连接索引是数据仓库中一种有效的优化表间连接操作性能的索引机制。在大内存分析处理应用场景下,位图连接索引不仅需要权衡索引的内存和CPU开销,还需要进一步考虑处理器平台所带来的性能收益和数据访问延迟。提出了基于服务的位图连接索引管理机制,其主要特点体现在三个方面:独立于数据库的自管理索引机制;基于存储空间约束的TOP K关键字位图连接索引机制;处理器敏感(processor-conscious)的位图连接索引技术。索引服务将索引从数据库中内置的数据结构变成数据库外的索引服务层,通过对用户查询负载的分析模块和索引服务管理模块改变传统的由数据库管理员人工管理索引的模式,同时借助于协处理器和内存云技术提高索引服务的性能和灵活性。实验测试结果表明,索引服务机制能够有效地提高索引存储和访问效率,在通用GPU的强大并行处理能力的支持下,位图连接索引服务的性能和数据库整体查询处理性能都得到了显著的提升。

基于分段位图索引在求解成员查询算法中的研究

从成员查询的特点出发,对各种位图索引求解成员查询的过程进行介绍。针对分段位图编码模式求解成员查询时,会出现重复扫描位图的情况,提出一种基于分段位图索引求解成员查询的高效算法。

使用Broadcast Disks方法分布的空中位图索引

提出一种使用BroadcastDisks算法来分布位图索引的空中索引方法,根据数据项访问概率,使用位图作为数据广播的索引,减少了移动终端等待数据时保持激活状态的时间,达到节能的目的。

基于Bin位图索引的多维查询优化算法

在属性基数(该属性可能的取值数)很高的情况下,简单位图索引需要占用太大存储空间。Bin位图索引可以很好解决这个问题。这种索引不像简单位图索引那样建立在不同的属性值上,而是建立在属性范围上,但候选检查往往占用大部分的查询时间。为了提高查询性能,提出一种排序方法来对各属性进行排序,以减少候选检查数目,并在此基础上提出动态预扫描算法。实验结果表明,排序和动态预扫描算法都取得了良好的效果。

基于Bloom过滤器的精确位图索引

针对基于Bloom过滤器的位图索引方法查询结果不精确的问题,提出一种精确位图索引算法——FPT-Index。该算法采用Bloom过滤器对基本位图索引进行压缩,同时引入假阳表,对查询结果进行筛选,从而达到精确查询的目的。通过理论分析得出,在给定关键词出现频率的前提条件下,可计算出最小压缩率以及所需哈希函数的个数。实验结果表明,FPT-Index相较于WAH方法在压缩率和查询效率两方面都有较好的表现。

并行框架下基于位图索引的多表星型连接算法

分析面向大数据平台的MapReduce分布式编程技术以及实现数据查询时的连接算法,针对SSB数据模型,提出基于分布式缓存的多表星型连接优化技术。利用谓词向量技术,将维表中间连接的数据依赖转化为表上的位图索引过滤,减少数据依赖产生的巨大网络开销;采用分布式缓存技术充分利用处理节点的内存,优化网络传输,减少查询代价。

基于Hadoop的位图索引的空间和效率研究

位图索引是一种使用Bit位的索引,有着较高的效率,大多运用于属性基数相对较小的情况。它有着较多的重复数据,可进行压缩,压缩编码的改进是研究的一个热点。对现有COMPAX编码方式进行改进。基于Hadoop的位图索引,使用分布式处理机制,使得位图索引的执行效率得到提升,可以运用于现今的大数据环境中;以解决目前大量的信息数据的查找问题。在建立索引过程中同时使用改进后的COMPAX编码进行数据压缩,使得索引占用空间减小,进一步提高对索引处理效率。