一种面向闪存键值存储的矩阵索引布鲁姆过滤器

索引结构是提高闪存键值存储插入和查询性能的关键技术之一.在分析目前相关索引结构特点的基础上提出了一种面向闪存键值存储的矩阵索引布鲁姆过滤器(matrix-indexed Bloom filter,MIBF),由m×s的位矩阵表示的多个布鲁姆过滤器组(multiple Bloom filter group,MBFG)和一个附加布鲁姆过滤器(additional Bloom filter,ABF)组成,其核心思想是键值对的闪存页地址被拆分为多组位串,每组位串采用MBFG中的一组布鲁姆过滤器(Bloom filter,BF)来表示,同时将键值对的Key与闪存页地址组合值存入ABF中.根据Key查询Value时,MBFG中的每组BF产生多位,组合生成键值对的闪存页地址,并通过ABF滤掉部分伪闪存页地址达到较精确地址定位,从而降低闪存访问次数,提高系统性能.与已有类似方法相比,MIBF的查询地址定位精度提高,内存和闪存访问次数降低明显,插入和查询性能显著提升.     

一种面向深度数据包检测的索引拆分Bloom过滤器

高速数据包处理迫切需要时空高效的深度数据包检测(DPI),满足其线速处理和低存储空间需求.Trie位图内容分析器(TriBiCa)采用片上位图Trie树来实现元素的最小完美Hash;但是,TriBiCa存在更新开销高和假阳性访问次数多等问题.共享节点快速Hash表(SFHT)采用片上计数Bloom过滤器(CBF)来实现硬件Hash表的快速查找;但是,SFHT存在更新开销高和存储空间需求大等问题.文中提出了一种索引拆分Bloom过滤器(ISBF).ISBF是由片上多组并行CBF和片外元素集构成,其核心思想是:元素的片外索引值被拆分成多组比特,每组比特采用多个片上并行CBF表示元素集;当查询元素时,每组并行CBF产生多个比特值,并合成候选元素的片外索引值.为了降低ISBF的更新开销,文中又提出了懒惰删除(lazyd eletion)算法和空缺插入(vacant insertion)算法,即采用一个片上删除位图,仅在片上并行CBF中删除或插入元素,而不需要调整其他元素的片外索引值.ISBF是一种时空高效的数据结构,其插入、删除和查询操作的平均片外存储器访问次数均为O(1);与TriBiCa和SFHT相比,ISBF在...     

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

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

一种基于间接索引桶的OLAP查询算法

提高多表连接和聚集操作性能是OLAP查询中的关键问题之一。本文提出了一种基于间接索引桶的OLAP分组聚集查询算法MIBGA。该算法将维层次编码和事实表标识符分组集合进行有效结合，用间接索引桶代替目前流行的位图连接索引，并通过分组属性位图的位操作方式来快速完成OLAP查询。分析表明，该方法压缩了索引的存储空间，减少了I／O开销，有效地提高了多表连接的查询效率。     

封闭立方体反转索引查询优化技术 *

处理用户复杂查询请求的速度是数据仓库关键性能之一。论述了在 QC算法产生的聚集表上建立反转索引和查询并还原出立方体上界的方法 ,查询算法包括位图查询算法和反转列表查询算法。最后进行了性能测试 ,结果表明这两种算法均能够提高查询的速度。     

BFPC:一种新型的基于Bloom Filter的报文分类算法

Bloom Filter是一种支持高速数据查询的数据结构,已被广泛应用到各个领域,包括路由查找、串匹配[1]等。本文将重点研究Bloom Filter在报文分类领域中的应用,提出一种新型的报文分类算法——BFPC,阐述BFPC算法的基本思想,并通过实例对该算法进行了描述。最后,对BFPC算法与其他报文分类算法进行了性能比较。     

位图索引的设计与实现

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

基于平衡二叉树和Bloom过滤器的可变长地址路由查找算法

可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题，提出一种基于平衡二叉树AVL(Adelson-Velskii and Landis)树和Bloom过滤器的适用于可变长地址的高效路由查找算法，简称为AVL-Bloom算法。首先，针对可变长地址灵活可变且无界的特点，利用多个片外哈希表分别存储前缀比特位数相同的路由条目及其下一跳信息，同时应用片上Bloom过滤器加速搜索可能匹配的路由前缀；其次，为了解决基于哈希技术的路由查找算法在查找最长前缀路由时需多次哈希对比的问题，引入AVL树技术，即通过AVL树组织每组路由前缀集合的Bloom过滤器及其哈希表，优化路由前缀长度的查询顺序，并减少哈希计算次数进而降低查询时间；最后，在3种不同的可变长地址数据集上将所提算法与METrie(Multi-Entrance-Trie)和COBF(Controlled prefix and One-hashing Bloom Filter)这两种传统路由查找算法进行对比实验。实验结果表明，AVL-Bloom算法的查询时间明显少于METrie和COBF算法，分别减少...     

基于双层索引结构的起源图查询方法

为解决现有的起源图查询效率低和资源占用率高的问题,考虑起源信息和数据本身之间的关联关系以及起源信息内部结构特点,提出了一种基于双层索引结构的起源图查询方法。首先,面向起源图查询,提出了一种包括基于词典表全局索引和基于位图局部索引的双层索引结构,全局索引用于查询起源图所存储的服务器节点,局部索引用于对全局索引查询到的服务器节点细化查询;然后,基于双层索引结构,设计了一种起源图查询方法,针对6种选择索引和3种join链接索引实现了查询算法。实验结果表明,所提方法既提高了查询效率,又降低了内存资源的浪费。     

基于计数型Bloom过滤器的网络数据流统计

现有的流统计信息主要侧重于流抽样而忽视全流统计。为此,提出一种使用优化设计的计数型Bloom过滤器流统计方法。针对计数型Bloom过滤器数据增长带来的计数器溢出和假阳性错误率增高的问题,分别设计动态统计和多个计数器协同统计的方案。概要化的存储结构可方便查询,而且其计数型Bloom过滤器简单的数据结构也易于硬件实现。实验结果表明,与传统哈希方法相比,计数型Bloom过滤器流统计方法的时间复杂度更低,可用于网络应用中的快速全流统计。     

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

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

基于双布鲁姆过滤器的数据排重技术

针对文件级单布鲁姆过滤器排重算法只能以文件为单位进行数据排重,数据块级单布鲁姆过滤器排重算法耗时过多的缺点,采用2个布鲁姆过滤器,创建文件级和数据块级2级数据排重的算法结构。实验结果表明,双布鲁姆过滤器排重算法可以以数据块为单位对数据排重,在保持低假阳性误判率的同时,相比数据块级单布鲁姆过滤器排重算法耗时缩短了43%~68%。     

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

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

实时数据库混合索引机制的设计与实现

在卫星地面设备监控中,需要将大量实时数据实时地存进数据库并提供实时查询。针对实时数据和Judy array数字树的特点,提出了一种基于内存映射文件的位图分配法,然后设计了一种哈希表、B+树和Judy array混合索引机制。通过大量记录的插入和查询,结果表明位图分配法能避免大量不可利用的内存碎片的产生,结合内存位图分配法的混合索引机制也为应用程序提供了实时的索引插入和查询。     

Bloom搜索过滤器的优化设计与实现

基于Bloom搜索过滤器的搜索过滤机制会发生误判,且在查询目标进入过滤器后,查询整个关键字的步骤会耗费太多成本。该文提出一套新的搜索过滤器架构。经实验验证,该过滤器能减少误判率的发生,降低整个过滤器的搜索成本,提高搜索过滤器的整体性能。     

L-priorities bloom filter: A new member of the bloom filter family

A Bloom filter is a space-efficient data structure used for concisely representing a set as well as membership queries at the expense of introducing false positive. In this paper, we propose the L-priorities Bloom filter (LPBF) as a new member of the Bloom filter (BF) family, it uses a limited multidimensional bit space matrix to replace the bit vector of standard bloom filters in order to support different priorities for the elements of a set. We demonstrate the time and space complexity, especially the false positive rate of LPBF. Furthermore, we also present a detailed practical evaluation of the false positive rate achieved by LPBF. The results show that LPBF performs better than standard BFs with respect to false positive rate.     

SBH: Super byte-aligned hybrid bitmap compression

Bitmap indexes are commonly used in data warehousing applications such as on-line analytic processing (OLAP). Storing the bitmaps in compressed form has been shown to be effective not only for low cardinality attributes, as conventional wisdom would suggest, but also for high cardinality attributes. Compressed bitmap indexes, such as Byte-aligned Bitmap Compression (BBC), Word-Aligned Hybrid (WAH) and several of their variants have been shown to be efficient in terms of both time and space, compared to traditional database indexes. In this paper, we propose a new technique for compressed bitmap indexing, called Super Byte-aligned Hybrid (SBH) bitmap compression, which improves upon the current state-of-the-art compression schemes. In our empirical evaluation, the query processing time of SBH was about five times faster than that of WAH, while the size of its compressed bitmap indexes was retained nearly close to that of BBC.     

基于MIR树的空间查询验证方法

在数据外包服务中,空间多项式函数查询能确保返回用户查询信息的真实性,因而具有较高的应用价值。为解决MIR树中倒排索引文件通信代价过高的问题,采用位图替代倒排索引文件,构造一种支持查询验证的数据索引结构——MRH树,在此基础上构造验证对象生成算法验证查询结果。实验结果表明,在保证查询结果可靠、正确和完整的前提下,相较于MIR树,MRH树能显著地降低通信开销和计算时间。