连接位极大似然动态过滤算法

Minwise Hash极大似然估计子RMle综合考虑所有事件的发生概率,可以提高估计精度,但降低了估计的效率。连接位Minwise Hash估计子RMinwise,c可以成倍减少比对次数,动态阈值过滤器能够进一步提高Minwise Hash算法和其变种算法的效率。结合连接位极大似然估计子和动态阈值过滤器,提出了连接位极大似然动态过滤算法R(TMle,c)。实验表明,R(TMle,c)具有精度和效率兼顾的特性,计算时间最少,并且在k>300的条件下,其准确度与RMle的近乎相等。     

最优分数位minwise哈希算法的研究

在信息检索中,minwise哈希算法用于估值集合的相似度;b位minwise哈希算法则通过存储哈希值的b位来估算相似度,从而节省了存储空间和计算时间。分数位minwise哈希算法对各种精度和存储空间需求有着更加广泛的可选择性。对于给定的分数位f,构建f的方式有很多。分析了有限的分数位组合方式,给出最优化分数位的理论分析。大量的实验验证了此方法的有效性。     

基于共享Cache多核处理器的Hash连接优化

针对目前主流的多核处理器,研究了基于共享缓存多核处理器环境下的数据库Hash连接优化.首先提出基于Radix-Join算法的Hash连接多线程执行框架,通过实例分析了影响多线程Radix-Join算法性能的因素.在此基础上,优化了Hash连接多线程执行框架中的各种线程及其访问共享Cache的性能,优化了聚集连接时Hash连接算法的内存访问,并分析了多线程聚集划分的加速比.基于开源数据库INGRES和EaseDB,实现了所提出的连接多线程执行框架,在实验中测试了多线程Hash连接框架的性能.实验结果表明,该算法可以有效解决Hash连接执行时共享Cache在多线程条件下的访问冲突和处理器负载均衡问题,极大地提高了Hash连接性能.     

Top-k相似连接算法性能优化

相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型：基于相似度阈值的相似连接和Top-k相似连接.Top-k连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join.为了解决Topk-join中存在的性能问题,提出了一种Top-k相似连接算法Opt-join,该算法将Token批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价,并理论证明了该置换的正确性.实验结果表明：与Topk-join算法相比,Opt-join取得了1.28倍~3.09倍的性能提升.实验数据还显示：随着数据长度的增加或k值的增长,Opt-join的性能优势有不断增加的趋势.     

基于三级存储器的Join算法

研究了基于三级存储器的海量关系数据库的Join算法.目前,在所有磁带数据Join算法中,基于Hash思想的算法是最优的.但是,这些算法没有考虑从第三级存储器中读取数据时,磁带定位时间对算法性能的影响.磁带的磁头随机定位耗时大,是影响基于三级存储器的数据操作算法时间复杂性的关键因素.针对这个问题,提出了两种新的基于三级存储器的海量关系数据库连接算法,即Disk-Based-Hash-Join算法和Tertiary-Only-Hash-Join算法.这两种算法采用了磁盘缓冲技术和散列数据集中存储方法,降低了算法的磁带磁头随机定位时间复杂性,提高了基于三级存储器的连接算法的性能.理论分析和实验结果表明,提出的基于三级存储器连接算法的性能高于目前所有同类算法的性能,可以有效地应用于海量数据管理系统.     

适用于范围查询的列存储数据桶划分算法

范围查询是数据库中一项重要的操作.列存储数据库中,能否有效查找一个范围内的属性值,获取对应的行号集合,将极大影响元组重构的效率.与树型结构相比,Hash表对数据的精确查找具有更高的效率,但是范围查找的效率比较低.针对这种情况,提出了一种改进的可用于范围查询的数据桶划分算法.为了能够更好地对算法进行描述,首先提出了可用于范围查询的Hash存储模型(ranged Hash,RH),并给出了桶的值域和序列化的定义.其次针对列存储等“读优先”特性,在RH模型的基础上,提出一种改进的桶划分算法.该算法生成可序列化的哈希函数把属性值划分到桶中,能够同时提高属性值的范围查询效率和存储效率.最后,通过实验结果验证算法的有效性.     

基于二叉树的反向Hash链遍历

提出了一种反向Hash链遍历的时间、空间复杂度优化算法.采用堆栈操作实现了高效的反向Hash链遍历,并将Hash链遍历过程映射到了二叉树的后序遍历过程,利用二叉树性质对存储和计算性能进行了理论化分析和证明.分析证明结果表明,遍历对长为n的反向Hash链时,算法只需要存储[lbn]+1个节点值,并且进行不多于[(lbn-/2+1)n次Hash计算次数.相比同类其他算法,该算法并不要求链长为2的整数次方.通过对算法进行基于k叉树(k≥3)的扩展,进一步将存储空间降低到[lo gk[(k-1)n+1],但总计算次数提高到[(-logk[(k-1)n+1]-1)k/2+1]n;通过在算法执行前先把Hash链平分为p段(p≥2),将总计算次数降低到[(lb(n/p)-/2+1)n,但是所需的存储空间提高到[(lb(n/p)+1)p.     

基数估计算法参数的分析与优化

基数估计算法(Cardinality Estimation Algorithm)是基于概率统计理论的估算给定数据集中不重复元素基数的算法。算法中的Hash函数和相关参数的设置是影响算法性能的两个关键因素。针对这两个问题展开研究,提出了一种基数估计的优化算法,它可以根据数据规模和数据类型动态调整Hash函数和分桶参数,以提高算法的精度和稳定性。实验结果表明,改进的基数估计算法在经过训练之后,相比传统估计算法,其估计精度和稳定性均有所提高。     

使用Hash表和树位图的两级IPv6地址查找算法

为了提高IPv6地址查找效率,在分析IPv6路由前缀长度分布规律的基础上,提出了基于哈希表及树位图(Tree-bitmap)的两级IPv6地址查找算法.算法将长度为16,32,48和64比特的前缀分别存储在4个Hash表中,其余前缀的前16,32和48比特利用已有的Hash表存储,剩余的不足16比特的部分前缀利用树位图存储,并将树位图的入口地址保存在Hash表中.IP地址查找时在Hash表和树位图中进行两级查找.实验表明,该查找算法的平均内存访问次数为1～2,最坏情况下为7,适用于高速IPv6地址查找.     

列存储数据查询中的连接策略优化方法

列存储数据查询优化的重点是列的连接策略.现有的列存储系统通过存储的改变来简化列的连接,致使列的连接缺少查询优化处理,策略单一且无法满足复杂查询.在剖析现有连接选择策略的基础上,提出一种新的连接策略优化方法,即首先利用基于规则的优化方法为列存储数据查询制定优化规则,过滤不可能产生最优计划的候选计划;然后设计了基于代价的优化算法,根据动态Huffman树和左深连接树原理对查询执行顺序进行改进,进一步减少候选计划的规模;根据列存储数据的特点将候选计划中每个连接节点的执行策略归纳为串行连接和并行连接两类,并在此基础上提出代价估计模型,进而可针对这两种连接策略进行代价估计和策略选择.最后在SSB数据集上通过实验证明了方法在列存储数据查询中的有效性.