索引压缩算法New PForDelta简介以及使用SIMD技术的优化

本文涉及的产品
智能开放搜索 OpenSearch行业算法版,1GB 20LCU 1个月
OpenSearch LLM智能问答版免费试用套餐,存储1GB首月+计算资源100CU
简介: New PForDelta算法介绍 倒排索引的数据包括docid, term frequency, term position等,往往会占用很大的磁盘空间,需要进行压缩。压缩算法需要考虑两点:压缩效果和解压缩效率。

written by 普队

New PForDelta算法介绍

倒排索引的数据包括docid, term frequency, term position等,往往会占用很大的磁盘空间,需要进行压缩。压缩算法需要考虑两点:压缩效果和解压缩效率。一般来说,提升解压缩效率,减少用户查询的响应时间更加重要。PForDelta算法以及它的改进版本New PForDelta算法在拥有不错压缩率的情况下解压缩性能也十分优秀。

PForDelta算法

算法的第一步是要进行Delta Encoding操作,对于一组按照顺序从小到大排列的数据,不需要保存每个元素的值,只需要保存相邻元素的差值即可。例如存储docid时就需要这么做,而对于不是递增排列的TF和TP,则没有这个操作,此时仅被称为PFor算法。

完成Delta Encoding后得到的数据会被拆分成多个block,每个block存储固定个数的数据(例如128个),算法会分别对每个block独立的压缩和解压。这样做除了可以利用数据的局部性特征,对不同部分采用不同的压缩策略外,还可以在解压缩时只选择解压部分block,不需要针对整个文件,例如查询某一term的position时只解压其所在block。

PForDelta算法的基础思想是对于一个block,认为其中大部分数据只需要较小的空间就可以存储下来,而剩下的部分被当做异常数据处理。一般通过设定一个值framebit,使得超过90%的数据都可以直接由framebit位存储下来,称为正常部分,剩下的小于10%的数据单独存储,称为异常部分。

比如一组数据如下:10, 34, 69, 77, 126, 137, 150, 179, 278, 279, ……..,在Delta Encoding后得到数据10, 24, 35, 8, 49, 11, 13, 29, 99, 1, …….,设定framebit = 5,那么小于32的数据都可以直接存下,大于等于32的有35, 49, 99需要单独存储。使用PForDelta压缩后的数据如下图所示:

11

图中第一个位置的“2”表示与第一个异常值的位置是2,往后数间隔2个可以找到第一个异常值的位置,可以通过异常部分知道这个异常值是35,然后根据这个位置的“1”又可以往后数间隔1个找到下一个异常值的位置,这个异常值是49,以此类推可以继续找下去。异常部分的存储是倒序的,这样做是为了在解压缩的时候更方便的把异常值填进去。

解压的过程就是先把正常部分每5位提取出来,然后按前面所说将异常值的位置找出来并且根据异常部分填入异常值。

除了存储数据外,整个数据还需要一个头信息,用于记录framebit的取值以及压缩后的长度等。

PForDelta算法会存在一个问题:异常数据的间隔可能超过framebit位能存储的最大值,例如framebit=5时异常值的间隔超过了31。一个可行的解决方法是将某些原来不是异常值的数据当成异常值处理,从而减小异常值的间隔,但是这样也造成了不必要的浪费。

New PForDelta算法

针对上面提到的问题,改进后的PForDelta算法的思路是:以128个数据为block大小时,异常值的间隔不会很大,可以把它们单独拿出来存储,而原来存储这些间隔大小的位置就用来存储异常值的低位,异常值的高位则和间隔一起存储在异常部分。

继续以上面Delta Encoding后的数据为例:10, 24, 35, 8, 49, 11, 13, 29, 99, 1, …….,设定framebit = 5。使用New PForDelta后的数据如下图所示:

22

可以比较与普通PForDelta的不同:正常部分开头存储的第一个异常值的位置没有了;圆圈内原来存储的是异常值的间隔,现在变成了35, 49, 99二进制形式下的低5位;异常部分存储的是第一个异常值35的位置“2”以及它除去低5位后的高位,异常值49与上一个异常值的间隔“1”以及它的高位,异常值99与上一个异常值的间隔“3”以及它的高位等等。

解压缩时首先将前面每5个bit存储的数据解压出来,然后处理异常部分:读到“2”,于是将“0000001”拼接到第2个位置“00011”之前得到35;读到“1”,将”00000001”拼接到第4个位置”10001”之前得到49;读到”3”,将“0000003”拼接到第8个位置”00011”之前得到99。(假设下标从0开始)

异常部分每个值的大小一般不会很大,可以用别的压缩算法继续压缩,例如indexlib中采用了s9算法(这里只是简单介绍一下):对每一个4字节32bit,选定一个提前规定的9种bit_length中的一种,例如选为7,且它对应的code_num为4,意思是接下来的4个数据都能用7bit的方式存储在这4个字节中,应当保证bit_length选的尽量小使得可以存储尽量多的数据。预先取定的9种bit_length保证它乘上对应的code_num不超过28,这样留下4bit的空间用于存储采用了第几种bit_length。

New PForDelta算法的优势与实现

算法的性能好坏与它的实现密切相关,原因是它的设计原则要求它CPU流水线友好,从而达到压缩率好的情况下解压效率也很优秀的目标。

因此实现时需要做到:对每个framebit分别实现函数;采用循环展开的优化方法;减少或避免分支结构出现。这些策略都是为了尽量保证流水线的通畅性。

使用SIMD技术

SIMD全称Single Instruction Multiple Data,单指令多数据流,通俗的说是指这样的指令集:收集多个操作数,将它们放入128位、256位甚至更多位的寄存器中(这个过程的访存操作也是并行的),同时(并行)对它们执行相同的操作。索引压缩算法看重压缩率和解压效率,New PForDelta算法解压时的指令序列契合SIMD技术对多个操作数执行相同操作的理念,因此可以使用SIMD技术来优化它。

New PForDelta算法解压时分为正常部分和异常部分的解压。异常部分需要将异常数据的高位依据间隔补到正常部分解压出来的数组中,不能使用SIMD指令,而正常部分只是将一系列按相同的framebit位存储的数据顺序提取到数组中,完全可以使用SIMD指令,因此我们只针对正常部分进行优化,优化的指令集是128位的sse4指令集(在编译时使用avx2编译选项,线上机器也支持avx2)。

来看一个简单的例子:framebit取8,解压时原来的实现方法是将一个int(4字节)中每8位用位运算取出分到数组中,解压16个数据则需要对4个int执行上述操作,采用sse4指令后只需将128位并行存入寄存器,然后并行的将它们分到数组的16个单元中。可以发现优化后的指令条数相比原来少了很多,但是流水线的流畅性就没有原来那么好了。另外,对于不规则的framebit(意思是有很多数据存储时横跨两个字节或者两个int),sse4指令需要添加一些额外的操作,超过原来解压方法所付出的代价。但是总体上来说,指令数目的减少弥补了流水线的问题,使用SIMD技术后解压效率有不错的提升,这将在后面介绍的测试效果中体现出来。

33

上图为原来解压的操作顺序,其中每个int的低位在左边。

44

上图为优化后解压的操作顺序,相同的标号代表并行执行。

测试效果

测试1

测试数据:没有异常值的随机数据

测试机器:CPU版本为v4的线上机器

蓝色和橙色:对应原始解压方法和新型解压方法

横坐标:表示用不同framebit压缩的数据(例如5表示此数据用framebit=5的方式压缩了)

纵坐标:表示解压速率,单位MB/s

55

测试2

测试数据:有接近10%异常值的随机数据

其它指标不变

66

可以发现,平均情况下解压速率提升了10%左右。framebit=6的异常是由于原先特别针对此情况采用了复杂的SIMD技术优化(汇编代码形式),framebit=15的异常原因主要是此种情况下sse指令特别复杂(每15位填充需要32个数据才能填满整int,因此需要很多额外的指令处理数据)。提升效果没有预想中的明显,可见New PForDelta算法流水线友好的设计初衷得到了体现。

结语

本文只讨论单纯使用SIMD技术对New PForDelta算法的提升作用,另一个优化思路是从索引结构上进行考虑,包括PForDelta和New PForDelta在不同场景下的对比、异常部分的压缩策略(例如是否采用s9)等。另外,压缩率和解压效率的平衡也是一个重要的课题。

目录
相关文章
|
29天前
|
机器学习/深度学习 算法 数据挖掘
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
|
1月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本内容包含基于BiLSTM与遗传算法(GA)的算法介绍及实现。算法通过MATLAB2022a/2024b运行,核心为优化BiLSTM超参数(如学习率、神经元数量),提升预测性能。LSTM解决传统RNN梯度问题,捕捉长期依赖;BiLSTM双向处理序列,融合前文后文信息,适合全局信息任务。附完整代码(含注释)、操作视频及无水印运行效果预览,适用于股票预测等场景,精度优于单向LSTM。
|
18天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
|
20天前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
48 6
|
18天前
|
机器学习/深度学习 算法
基于遗传优化ELM网络的时间序列预测算法matlab仿真
本项目实现了一种基于遗传算法优化的极限学习机(GA-ELM)网络时间序列预测方法。通过对比传统ELM与GA-ELM,验证了参数优化对非线性时间序列预测精度的提升效果。核心程序利用MATLAB 2022A完成,采用遗传算法全局搜索最优权重与偏置,结合ELM快速训练特性,显著提高模型稳定性与准确性。实验结果展示了GA-ELM在复杂数据中的优越表现,误差明显降低。此方法适用于金融、气象等领域的时间序列预测任务。
|
23天前
|
算法
基于遗传优化算法的带时间窗多车辆路线规划matlab仿真
本程序基于遗传优化算法,实现带时间窗的多车辆路线规划,并通过MATLAB2022A仿真展示结果。输入节点坐标与时间窗信息后,算法输出最优路径规划方案。示例结果包含4条路线,覆盖所有节点并满足时间窗约束。核心代码包括初始化、适应度计算、交叉变异及局部搜索等环节,确保解的质量与可行性。遗传算法通过模拟自然进化过程,逐步优化种群个体,有效解决复杂约束条件下的路径规划问题。
|
1月前
|
机器学习/深度学习 算法
基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法matlab仿真
本项目实现基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法的MATLAB仿真,对比SVM和GWO-SVM性能。算法结合差分进化(DE)与灰狼优化(GWO),优化SVM参数以提升复杂高维数据预测能力。核心流程包括DE生成新种群、GWO更新位置,迭代直至满足终止条件,选出最优参数组合。适用于分类、回归等任务,显著提高模型效率与准确性,运行环境为MATLAB 2022A。
|
1月前
|
算法
基于PSO粒子群优化的多无人机路径规划matlab仿真,对比WOA优化算法
本程序基于粒子群优化(PSO)算法实现多无人机路径规划,并与鲸鱼优化算法(WOA)进行对比。使用MATLAB2022A运行,通过四个无人机的仿真,评估两种算法在能耗、复杂度、路径规划效果及收敛曲线等指标上的表现。算法原理源于1995年提出的群体智能优化,模拟鸟群觅食行为,在搜索空间中寻找最优解。环境建模采用栅格或几何法,考虑避障、速度限制等因素,将约束条件融入适应度函数。程序包含初始化粒子群、更新速度与位置、计算适应度值、迭代优化等步骤,最终输出最优路径。
|
26天前
|
机器学习/深度学习 数据采集 算法
基于GWO灰狼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于Matlab 2022a/2024b实现,结合灰狼优化(GWO)算法与双向长短期记忆网络(BiLSTM),用于序列预测任务。核心代码包含数据预处理、种群初始化、适应度计算及参数优化等步骤,完整版附带中文注释与操作视频。BiLSTM通过前向与后向处理捕捉序列上下文信息,GWO优化其参数以提升预测性能。效果图展示训练过程与预测结果,适用于气象、交通等领域。LSTM结构含输入门、遗忘门与输出门,解决传统RNN梯度问题,而BiLSTM进一步增强上下文理解能力。
|
1月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的TCN-GRU时间卷积神经网络时间序列预测算法matlab仿真
本内容包含时间序列预测算法的相关资料,涵盖以下几个方面:1. 算法运行效果预览(无水印);2. 运行环境为Matlab 2022a/2024b;3. 提供部分核心程序,完整版含中文注释及操作视频;4. 理论概述:结合时间卷积神经网络(TCN)与鲸鱼优化算法(WOA),优化TCN超参数以提升非线性时间序列预测性能。通过因果卷积层与残差连接构建TCN模型,并用WOA调整卷积核大小、层数等参数,实现精准预测。适用于金融、气象等领域决策支持。