一种查存算法的比较方法

摘要

本发明公开了一种查存算法的比较方法，包括有以下步骤：A、用候选数据结构表示存储在系统中的已存集合；B、计算候选数据结构的评估参数；C、根据上述评估参数比较评估指标从而得出最合适的查存算法。本发明通过候选数据结构表示存储在系统中的已存集合，对不同的查存算法作出统一的描述，以便于后面在选择和评估查存算法中的比较和分析；并计算出相关的评估参数，包括有拒绝时间、空间开销、表示效率和误判率，用于评估和针对特定的应用需求选择适合的查存算法。本发明作为一种查存算法的比较方法可广泛应用于大数据处理领域。

说明书

技术领域

本发明涉及大数据处理领域，尤其是一种查存算法的比较方法。

背景技术

在大数据环境下，每天新产生的海量数据，将会存储在数据库系 统中。在很多情况下，系统新来一个数据，都需要查询该数据是否已 经在系统中，也就是对数据的查存。随着存储在系统中的数据量的增 加，需要消耗更多的时间来查询一个数据是否已经存在系统中。然而， 在实际应用中，却需要系统能快速地响应这类查询。例如，快盘存储 应用，需要快速查找文件是否存在，从而确定文件的变化来进行同步。 再如，近日，网络曝光成都工行ATM机吐出同号假钞，若能快速查询 同号假钞的冠字号是否存在银行的金库中，这样在出现假钞时，可以 快速确定具有相同冠字号的钞票是否出自银行ATM机以厘清银行与 顾客的责任，这也是快速查询数据是否存在系统中一个应用实例。因 此，快速响应一个数据是否已经存在已存储着海量数据的存储系统中， 是一个具有实际意义的应用需求。

现存的位图数据结构、布隆过滤器及其相关引申的数据结构算法， 各有优势，均可用来表示存储在系统中的所有数据，以快速响应数据 是否已存在系统中的查询。位图数据结构在实际数据库应用中通常用 作索引，布隆过滤器是一个以准确率换取高效空间的数据结构。

在大数据环境下，每天新产生的海量数据，将会存储在数据库系 统中。在很多情况下，系统新来一个数据，都需要查询该数据是否已 经在系统中，也就是对数据的查存。随着存储在系统中的数据量的增 加，需要消耗更多的时间来查询一个数据是否已经存在系统中。然而， 在实际应用中，却需要系统能快速地响应这类查询。例如，快盘存储 应用，需要快速查找文件是否存在，从而确定文件的变化来进行同步。 再如，近日，网络曝光成都工行ATM机吐出同号假钞，若能快速查询 同号假钞的冠字号是否存在银行的金库中，这样在出现假钞时，可以 快速确定具有相同冠字号的钞票是否出自银行ATM机以厘清银行与 顾客的责任，这也是快速查询数据是否存在系统中一个应用实例。因 此，快速响应一个数据是否已经存在已存储着海量数据的存储系统中， 是一个具有实际意义的应用需求。

现存的位图数据结构、布隆过滤器及其相关引申的数据结构算法， 各有优势，均可用来表示存储在系统中的所有数据，以快速响应数据 是否已存在系统中的查询。位图数据结构在实际数据库应用中通常用 作索引，布隆过滤器是一个以准确率换取高效空间的数据结构。

针对上述的如何表示存储在系统中的数据，并快速响应一个数据 是否已经存在已存储着海量数据的存储系统中应用场景需求，常见的 方案是通过客户端访问数据库系统，查询某一特定的数据是否已经在 存储系统中。这种方案虽然可行，但直接访问数据库查询相关的交易 记录，将会引起不必要的时间开销。另外，还有一种方案是，在内存 中实现一个数据结构，用来表示系统中的所有数据。当要查询某一数 据是否已经存在系统中时，只需要访问这个数据结构即可。

相对于第一种方案，第二种方案不需要访问数据库，相关查询只 需要在内存中完成，就可以知道这条数据是否已经存在系统中，在时 间开销上优于第一种方案。现存的数据结构，例如位图数据结构、布 隆过滤器及其相关引申的数据结构算法，各有优势，均可用来表示存 储在系统中的所有数据。然而，这些算法并非在所有场景中都表现出 良好的性能。另一方面，到目前为止，大多数相关工作侧重于对查存 算法的改进，还没有对这些算法的比较选择。

发明内容

为了解决上述技术问题，本发明的目的是：提供一种针对现有查 存算法进行计算评估的查存算法的比较方法。

本发明所采用的技术方案是：一种查存算法的比较方法，包括有 以下步骤：

A、用候选数据结构表示存储在系统中的已存集合；

B、计算候选数据结构的评估参数；

C、根据上述评估参数比较评估指标从而得出最合适的查存算法。

进一步，所述候选数据结构中包括有该数据结构中涉及的包含于 不同集合的操作数据对象、上述操作数据对象之间的映射关系和候选 数据结构的操作函数组成的集合。

进一步，所述操作数据对象包括有数据集和可提供置位的空间单 元。

进一步，所述评估参数包括有拒绝时间、空间开销、表示效率和 误判率。

进一步，所述步骤C中拒绝时间和空间开销用于评估查存算法判 断数据不在系统中的时间与查存数据结构的空间开销的权衡。

进一步，所述步骤C中表示效率用于针对不同的数据量或在涉及 数据的变化情况下评估查存算法表示每个数据所用的空间开销。

进一步，所述步骤C中误判率用于评估查存算法的反映系统数据 的能力。

本发明的有益效果是：本发明通过候选数据结构表示存储在系统 中的已存集合，对不同的查存算法作出统一的描述，以便于后面在选 择和评估查存算法中的比较和分析；并计算出相关的评估参数，包括 有拒绝时间、空间开销、表示效率和误判率，用于评估和针对特定的 应用需求选择适合的查存算法。

附图说明

图1为本发明方法的步骤流程图；

图2为候选数据结构判断任意一个元素是否存在于系统中的示 意图；

图3为候选数据结构与已存集合增删元素示意图；

图4为位图数据结构示意图；

图5为标准型布隆过滤器结构示意图；

图6为计数型布隆过滤器结构示意图；

图7为D-left布隆过滤器的结构示意图。

具体实施方式

相关定义

定义1全集：全集是指由系统中的数据对应的整个数据范围空间。

形式化描述为，由涉及问题中的所有数据元素组成的集合，记为 U。全集U的元素个数为|U|，记为n_u。

定义2已存集合：是指存在系统中的海量数据集。形式化描述为， 由存储在系统中的数据元素组成的集合，记为DS。DS是全集U的 一个子集，即集合DS的元素个数是|DS|，记为n。

定义3测试集合：是指由任意一个到达系统，需要测试是否已经存 在于系统中的新数据组成的集合，记为TS。集合TS的元素个数 是|TS|，记为n_t。同样，它满足

定义4空间单元：表示内存中由1个或1个以上组成的连续比特位， 记为C，单位是比特，空间单元中，比特位的个数记为b。

定义5候选数据结构：是指在内存中实现的用于表示存储系统中的 海量数据和查存的数据结构算法，即是用于表示系统中的已存集 合DS的数据结构，记为A＝(D,R,F)。其中，D是指在该数据结 构中涉及的包含于不同集合的操作数据对象，R是指在D上不同 数据对象的映射关系，F是由候选数据结构的操作函数组成的集 合。

定义6置位：表示对空间单元(见定义4)的置1或赋值操作，记 为Set。形式化表示为，对于内存中任意的空间单元C，有Set使 得Set(C)＝1。

定义7置位集合：用于表示在候选数据结构(见定义5)中内存中 连续的空间单元(见定义4)，形式化描述为，由需要进行置位 (见定义6)的空间单元组成的集合，记为M，置位集合的元素 个数n_m＝|M|。在这里需要注意，M属于候选数据结构 A＝(D,R,F)的D中的其中一种集合。

定义8置位映射：表示将数据库系统中的数据映射至候选数据结构 的空间单元的映射函数，即已存集合到候选数据结构的置位集合 的映射函数，形式化描述为，对于1≤i≤n_u，映射函 数f使得f:U→M^r，M^r表示从集合M选择r个元素进行置位。

置位映射满足以下特性：

1)置位映射可以是一对一，也可以是一对多。r表示每次进行 映射时，选中置位集合中的元素的个数，其中r≥1。

2)置位映射的定义域

3)若f:U→M^r可逆，则它的逆映射是f^-1:U→M^r。

定义9表示集合：当插入数据时，候选数据结构(见定义5)的部 分或全部空间单元产生置位后，候选数据结构可以表示的数据集。 形式化描述如下：候选数据结构A＝(D,R,F)的置位映射产生后， 候选数据结构A＝(D,R,F)的可以表示的集合，称为表示集合， 记为S，它满足集合S的元素个数是|S|，记为n_s。

定义10表示关系：是指当候选数据结构的部分或全部空间单元产 生置位后时，组成候选数据结构的连续空间单元与它可以表示的 数据集的映射关系。形式化描述如下：候选数据结构A＝(D,R,F) 的从已存集合DS的所有元素通过置位映射(见定义8)映射到置 位集合后，置位集合已选择t个元素进行置位，这种被置位后的 置位集合与表示集合的映射关系，记为<M^t,S>。特别地，t＝0 时，表示插入元素，此时当t＝|M|＝n_m时，S＝U。

定义11成员查询：给定某一数据，用户访问候选数据结构查询该 数据是否存在于存储系统中。形式化描述如下：对任意d∈TS(见 定义3)，返回d是否包含于DS的查询应答的函数，记为query(d)。

定义12误判率：用于描述进行成员查询query(d)(见定义11)时 出现不准确应答的概率。误判率包括两类，一类是假阳性误判率， 即是将不存在于数据集中的元素误判为存在的误差；另一类是假 阴性误判率，即将存在于数据集DS误判为不存在的误差。

误判率的形式表示如下：

1)假阳性误判率FP：对于给定成员查询query(d)返 回表示d∈DS的真值，记为

2)假阴性误判率FN：对于给定d∈DS，成员查询query(d)返 回表示$d\notin \mathrm{DS}$的假值，$\mathrm{FN}=P(d\notin S|d\in \mathrm{DS}).$

定义13空间开销：是指候选数据结构A＝(D,R,F)(见定义5)在 内存中需要空间单元的个数，即置位集合(见定义6)的元素个 数，与每个空间单元所需的比特位个数(见定义4)的乘积，记 为Mem，单位是比特位。

定义14表示效率：是指候选数据结构A＝(D,R,F)(见定义5)的 空间开销Mem(见定义13)与集合DS的全部元素个数n＝|DS|之 比，记为E。用于描述候选数据结构A＝(D,R,F)表示集合DS时， 平均每个元素需要的比特位的个数(通常用位数bits表示)。

定义15表示性能：候选数据结构A＝(D,R,F)表示一个元素的能力， 通过表示效率来度量。表示效率越大，已存集合DS中每个元素 所需比特位的个数越多，表明候选数据结构A＝(D,R,F)的表示 性能越差。

定义16拒绝时间：给定某一查询数据，候选数据结构A＝(D,R,F) 判定该数据不在系统中的时间。形式化描如下：给定元素d∈TS， 成员查询query(d)判断d不属于DS所需要的时间，记为T。(在这 里，不考虑判断d属于DS所需要的时间的定义是因为这个时间是 若干个单位时间，注意这里所说的时间并不包括访问外存以判断 d属于DS所需的时间。)

定义17一致性：是指候选数据结构A＝(D,R,F)(见定义5)反映 系统中的已存集合DS及其变化的度量。通常一致性用误判率(见 定义12)来度量。

下面结合附图对本发明的具体实施方式作进一步说明：

参照图1，一种查存算法的比较方法，包括有以下步骤：

A、用候选数据结构表示存储在系统中的已存集合；

B、计算候选数据结构的评估参数；

C、根据上述评估参数比较评估指标从而得出最合适的查存算法。

以下分步骤详细说明：

问题建模：

根据前面的相关定义，问题建模如下：考虑一个大数据集，将这 个数据集中全部数据或部分数据存储在系统，并在存储过程中，系统 的内存里实现一个数据结构，用来表示存储在系统中的海量数据。这 就是用内存小空间的数据结构表示系统中的大空间的数据。当往系统 插入数据时，数据结构相应地插入新数据，当系统要删除某一数据时， 数据结构若可删除元素，则相应地删除该数据。若要查询任意一个元 素是否在系统中，只要访问内存中该数据结构即可。

形式化表示为，全集U是大数据集所有不同的元素所组成的集合， 其所有元素的个数是n_u。DS是存储在系统中的所有元素的集合，该 集合元素个数是n。根据定义，n≤n_u，显然，集合DS本身 就是其全集时，等号成立。候选数据结构A＝(D,R,F)中的表示集合 测试集合TS是由任意一个属于全集的并用来测试是否存在于 系统的数据组成的集合。

下面结合附图对问题建模进行说明。

如图2，对于访问候选数据结构A＝(D,R,F)，查询d是 否在系统中，即d是否包含DS，候选数据结构A＝(D,R,F)有操作函数， 返回d∈DS或具体的实施方式是，对于任意的新来数据，访 问系统内存中的候选数据结构，查询这个数据是否在系统中，实施的 效果是这个候选数据结构返回真假值以应答本次查询。

如图3，当系统中新插入一个数据，候选数据结构若具有插入数 据的属性，则它能同步反映系统中的数据集新插入新数据。形式化描 述为，对于但已存集合DS＝DS+{d}，若候选数据 结构具有插入元素的属性，则A＝(D,R,F)有操作函数使得S＝S+{d}。 具体的实施方案是，当系统新插入一条数据的时候，候选数据结构通 过对若干个空间单元进行置位，以表示该数据。

如图3，当系统中新删除一个数据，候选数据结构若具有删除数 据的属性，则它能同步反映系统中的数据集删除旧数据。对于当DS＝DS-{d}，若候选数据结构A＝(D,R,F)具有可删除元素的属 性，则有操作函数使得S＝S-{d}。具体的实施方案是，当系统删除 数据时，若这个候选数据结构的连续空间单元可以恢复置位前的状态， 则它可以将删除的数据对应的空间单元恢复置位前的状态。

算法建模：

根据前面的问题建模，全集U是大数据集所有不同的元素所组成 的集合，其所有元素的个数是n_u。DS是存储在系统中的所有元素的 集合，该集合元素个数是n。根据定义，n≤n_u，显然，集 合DS本身就是其全集时，等号成立。因此对候选数据结构的统一建 模如下：

用候选数据结构A＝(D,R,F)表示存储在系统中的已存集合DS，

1)由问题中涉及的不同数据对象组成的集合D，相当于已存集 合DS的全集U与置位集合M的并集。指已存集合DS对应于系统中的数 据，全集U就是数据的范围，置位集合M对应于系统内存中的数据结 构的空间。直观来说，这里的数据对象是候选数据结构操作的对象的 统称。因此，集合D就是候选数据结构直接操作的数据对象组成的集 合，包括有数据集、可提供置位的空间单元。

2)R是在D上不同数据对象的映射关系：置位映射关系 R₁＝<d,M^r>，其中d∈DS，M^r表示从集合M选择r个元素进行置位 (见定义6)，直观来说，它就是一个数据与在候选数据结构中的所 有连续空间单元的选出若干个空间单元进行置位的对应关系；表示关 系R₂＝<M^t,S>，其中M^t表示从集合M选择t个元素进行置位，S是 表示集合(见定义9)。实际上，置位映射关系R₁是指系统插入一条 数据后，内存中的数据结构选择若干个空间单元置位。表示关系R₂则 是指内存中的数据结构的部分或全部空间单元被置位后，可表示的数 据。

3)候选数据结构的操作函数F＝{f:U→M^r,query(d)}，其中， f:U→M^r是置位映射(见定义8)，其定义域dom(f)＝DS，query(d)是成员查询(见定义11)，d∈TS，TS是测试集合，

这时，候选数据结构A＝(D,R,F)的空间开销是置位集合的元素 个数与候选数据结构的空间单元的比特位个数的乘积，即

Mem＝n_m×b   (1)

特别地，当映射个数r＝1，空间单元的比特位个数b＝1时，由 于DS的随机性，关系R₂<M^t,S>中的表示集合S必须是DS的全集， 才能表示DS，此时

Mem＝n_u   (2)

由于候选数据结构A＝(D,R,F)的置位集合M中每个元素是内存 中的一个空间单元(见定义4)，当每个空间单元的比特位个数是b＞1 时，则候选数据结构A＝(D,R,F)的置位集合M中任意一个元素发生 赋值操作的置位(见定义6)，且产生的空间单元的赋值置位相等的 概率是

$\frac{1}{n_m\times 2^b}---\left(3\right)$

已知置位映射f:U→M^r进行一次映射从置位集合M中选择的元 素个数r＞1，且每个元素是仅由一个比特位组成的置位空间时，当DS 中的所有元素都通过置位映射将置位集合M相应的空间单元置位后， 这时，M有t个元素被置位，表示为M^t，其中t≤|M|＝n_m，因而产 生关系R₂<M^t,S>。因此，候选数据结构A＝(D,R,F)的置位集合M 中任意一个元素发生置1操作的置位(见定义6)时，置位集合M的 一个元素仍未发生置位的概率是

$P={(1-\frac{1}{n_m})}^{\mathrm{rn}}---\left(4\right)$

候选数据结构A＝(D,R,F)的成员查询query(d)的假阳性误差率 (本具体实施例算法建模暂不考虑假阴性误差率)是

$\mathrm{FP}=P(d\in S|d\notin \mathrm{DS})={(1-P)}^r---\left(5\right)$

由上可得，候选数据结构A＝(D,R,F)的空间开销取决于置位集 合的元素个数以及空间单元的比特位个数，而误差率受已存集合的元 素个数、置位集合的元素个数、置位映射的映射个数以及空间单元的 比特位个数决定。

评估指标

1)拒绝时间与空间开销的评估

拒绝时间与空间开销的评估主要是评估候选数据结构的空间开 销对它判定任意一数据不存在系统中的时间的影响。

置位集合M表示候选数据结构A＝(D,R,F)内存中连续的空间单 元，Mem表示候选数据结构A＝(D,R,F)的空间开销(见定义13)。 对于置位函数f(d)＝f:U→M^r将从置位集合M中选出r个 元素进行置位，每个元素，即每个置位集合中的空间单元均以1/n_m的 概率被置位。

首先，考虑置位映射f:U→M^r进行一次映射从置位集合M中选 择的元素个数r＝1情况。当r＝1，b＝1时，候选数据结构 A＝(D,R,F)的置位集合M每个元素是由一个比特位组成的空间单元。 置位映射f:U→M^r进行一次映射时，只会产生一个空间单元的置位， 即对一个比特位进行置位。换言之，已存集合DS的一个元素对应于 置位集合中的一个空间单元。当DS中的所有元素都通过置位映射将 置位集合M相应的空间单元置位后，M有t个元素被置位，表示为M^t， 产生关系R₂<M^t,S>。直观上来说，就是将候选数据结构 A＝(D,R,F)的n_m个空间单元的相应t个位置位后，它表示的数据集 与置位后的候选数据结构的对应关系。因此，置位集合M的一个元素 仍未发生置位的概率是P＝(1-1/n_m)ⁿ，此时FP＝1-P＝1- (1-1/n_m)ⁿ，由n_m＞＞1，可得FP＝0。又因为DS的随机性，关系 R₂<M^t,S>中的表示集合S必须是DS的全集，才能表示DS，因此

Mem＝n_m×b＝n_u×1＝n_u   (6)

由上式可得，当r＝1，b＝1时，判定元素不存在集合里只需要 一个单元的时间O(1)，因此，空间Mem与拒绝时间T不产生依赖。

再看，当r＝1，b＞1时，空间Mem越大，意味着置位集合M中 的元素的空间单元的比特位个数越多，空间单元中相同的置位的可能 性就越低，因而候选数据结构A＝(D,R,F)判定元素不存在集合的拒 绝时间就越少。

再考虑置位映射f:U→M^r进行一次映射从置位集合M中选择的 元素个数r＞1的情况。当DS中的所有元素都通过置位映射将置位集 合M相应的空间单元置位后，M有t个元素被置位，表示为M^t，其中 t≤|M|＝n_m，产生关系R₂<M^t,S>。易得，置位集合M的一个元 素仍未发生置位的概率是

$P={(1-\frac{1}{n_m})}^{\mathrm{rn}}---\left(7\right)$

易得，对于d∈T，成员查询query(d)函数错误认为元素d已出现 在DS的假阳性误判率是

$\mathrm{FP}=P(d\in S|d\notin \mathrm{DS})={(1-P)}^r---\left(8\right)$

由于r＞1，假设r《nm，nm》1，根据相关文献1(Zhong M,Lu  P,Shen K,et al.Optimizing data popularity conscious bloom  filters[C].Proceedings of the twenty-seventh ACM symposium on  Principles of distributed computing.ACM,2008:355-364.)的 推导，r往往远小于n_m，近似得到如下公式，

$n_m=-\frac{n·{\log }_2\mathrm{FP}·{\log }_{2}e}{{\log }_{2}P·{\log }_2(1-P)}---\left(9\right)$

同样，由上述文献求得到拒绝时间T的近似值是

$T={\Sigma }_{x=1}^{\infty }x·P·{(1-P)}^{x-1}=1/P---\left(10\right)$

由定义13，空间开销是Mem置位集合的元素个数与每个空间单 元所需的比特位个数的乘积，再根据上述文献，结合公式9，可得时 间、空间以及误差率的权衡如下式，

$\mathrm{Mem}=n_m\times b=-\frac{b·n·{\log }_2\mathrm{FP}·{\log }_{2}e}{{\log }_{2}1/T·{\log }_2(1-1/T)}---\left(11\right)$

根据公式(11)可知，给定误差率范围内，当空间开销Mem越 少，判断d不属于DS所需要的时间会相对越长，反之，时间相对会越 短。从直观意义上来解释，空间开销Mem越少，意味着候选数据结 构A＝(D,R,F)的置位集合M的元素个数越少，那么随着置位映射 f(d)＝f:U→M^r的定义域集合dom(f)＝DS范围增大，即元素个数 增大，置位集合M的元素被选中置位的个数相应增加，成员查询 query(d)找到置位集合M未被选中的时间越长，从而导致拒绝时间的 增加。

2)空间开销与表示性能的评估

空间开销与表示性能的评估候选数据结构的空间开销和表示性 能随着已存集合的元素个数以及全集的范围的变化趋势。表示性能用 表示效率度量，表示效率是指系统中每个数据在内存中平均需要的比 特位的个数，表示效率越高，查存算法的表示性能越低。

首先，考虑置位映射f:U→M^r进行一次映射从置位集合M中选 择的元素个数r＝1情况。当r＝1，b＝1时，由于DS的随机性，关 系R₂<M^t,S>中的表示集合S必须是DS的全集U，才能表示全集U中 的任意子集DS，Mem＝n_u×b，因此，此时的表示效率是直观上来说，当r＝1，b＝1时，当集合DS相对于全集U越稀疏，集 合DS中每个元素在候选数据结构A＝(D,R,F)中，所需要元素的比特 位的个数越多，表明候选数据结构A＝(D,R,F)的表示效率越高，则 它的表示性能越差。

再考虑置位映射f:U→M^r进行一次映射从置位集合M中选择的 元素个数r＞1的情况。当DS中的所有元素都通过置位映射将置位集 合M相应的空间单元置位后，产生关系R₂<M^t,S>，其中 t≤|M|＝n_m，又因为DS是一个由全集U中任意n个元素组成的集合， 要表示全集U中任意n个元素组成的集合DS，则(这里与r＝1 的情况不同。r＞1时，关系R₂<M^t,S>意味着置位集合M有t个元 素被置位，其中t≤|M|＝n_m，这时只有t＝n_m时，S＝U。)。 结合相关文献2(Aguilar-Saborit J,Trancoso P,Muntes-Mulero  V,et al.Dynamic count filters[J].ACM SIGMOD Record,2006, 35(1):26-32.)的推导，令0＜∈＜1，表示集合S至多包含 n_s＝n+∈(n_u-n)个元素，关系R₂<M^t,S>中的集合S就是包含 n_s＝n+∈(n_u-n)个元素的特定集合，当t≤|M|＝nm，满足由于表示集合S的任意一个包含n个这些元素的子集的组合个数是 那么，要使S表示全集U中所有个组合的集合， 则需要满足相关文献2：

$2^{n_m}\left(\begin{array}{c}n+\in (n_u-n)\\ n\end{array}\right)\ge \begin{array}{c}\left(\begin{array}{c}{n}_u\\ n\end{array}\right)\end{array}---\left(12\right)$

由于置位集合M中每个元素是需要进行置位的空间单元，每个空 间单元由b个比特位组成，结合相关文献2第490页的推导结果，易 得，

$\left(\begin{array}{c}\mathrm{Mem}=n_m\times b\ge b·{\log }_2\frac{\left(\begin{array}{c}{n}_u\\ n\end{array}\right)}{\left(\begin{array}{c}n+\in (n_u-n)\\ n\end{array}\right)}\\ \approx b·{\log }_2\frac{\left(\begin{array}{c}{n}_u\\ n\end{array}\right)}{\left(\begin{array}{c}{\in n}_u\\ n\end{array}\right)}\ge b·{\log }_2{\in }^{-n}\\ =b·n{\log }_2(1/\in )\end{array}\right)---\left(13\right)$

同时，相关文献2中指出取r＝ln2·(n_m/n)时，FP取最小值， 要使误差率不超过∈，FP≤∈，则$\mathrm{Mem}\ge b·n\frac{{\log }_2\left(\frac{1}{\in }\right)}{\ln 2}=b·{n\log }_{2}e·$${\log }_2(1/\in ).$

此时，候选数据结构A＝(D,R,F)的表示效率是log₂e·log₂(1/∈)，显然，它与误差率相关，不随已存集合的元素个 数变化而变化。因此，在给定的误差率范围内，候选数据结构 A＝(D,R,F)的表示性能不变。

综上，当r＝1，b＝1时，其空间开销Mem＝n_u×b，存储效率 显然，当要表示的集合只占全集的一小部分，候选数据 结构A＝(D,R,F)的表示性能明显不高。因此，若要表示的集合的全 集范围不大，且其所有元素占全集的比重超过一半时，建议置位映射 f:U→M^r中的r取r＝1。

当r＞1，其空间开销$\mathrm{Mem}\ge b·n·\frac{{\log }_2\left(\frac{1}{\in }\right)}{\ln 2}=b·n·{\log }_{2}e·$${\log }_2(1/\in ),$∈表示给定的误判率范围。表示效率在给定误判率的范围下，空间开销Mem与候选数 据结构要表示的集合DS的所有元素个数n以及单元空间的比特位个 数b的乘积呈线性相关，通常情况下，n＞＞b，且b一般给定的，因此， 空间开销Mem可看作与n成正比。而表示效率仅与候选数据结构 A＝(D,R,F)的置位集合M的每个元素，即空间单元，所需的比特位 的个数b成正比。因此，当要DS仅占全集U的一小部分时的情况下， 亦即当集合DS相对于全集U较稀疏时，建议置位映射f:U→M^r中的r 取r＞1。

3)一致性评估

一致性评估是指候选数据结构A＝(D,R,F)的表示集合S能反映 系统中的已存集合DS的变化的度量。它包括三方面，首先，已存集 合DS新增元素时，相应地，候选数据结构A＝(D,R,F)的两组关系 R₁＝<d,M^r>，R₂<M^t,S>能及时反映这一变化，即表示集合S亦 同时新增元素。其次，当已存集合DS删除元素时，候选数据结构 A＝(D,R,F)若及时反映这一变化，它的表示集合S相应地删除该元素。 最后，对测试集合TS中的任意元素进行成员查询时，query(d)是否 能准确或是在一定误差范围内反映该元素是否存在系统。具体的形式 化描述如下：

1)候选数据结构A＝(D,R,F)新增元素时，一致性评估为： 若DS＝DS∪{d}，则有f:U→M^r使得S＝S∪{d}。

2)候选数据结构A＝(D,R,F)删除元素时，一致性评估为： 若DS＝DS-{d}且f:U→M^r可逆，则有f^-1:U→M^r，使 得S＝S-{d}。

3)候选数据结构A＝(D,R,F)进行成员查询时，一致性评估为： query(d)返回d∈DS的真假值。

一致性评估可用误判率来度量，(或)，query(d) 以一定误差范围内返回真(假)。

3.4算法建模评估流程

针对前面的问题建模和算法建模，如图1所示，给定候选数据结 构，首先，根据前面的相关定义，用上述的统一建模描述这个候选数 据结构，这一步的主要结果是：给出候选数据结构要处理的数据全集 以及候选数据结构在内存中可置位的空间表示的集合组成的处理数 据对象集合表示、候选数据结构要处理的不同数据对象的映射关系以 及候选数据结构的操作函数；操作函数包括有候选数据结构中，在存 储任一数据时，选择对应的内存中的置位空间的映射函数，还有对任 意一条数据的成员查询函数。然后，由上面的统一描述数学模型，即 用本模型的符号系统，推导出候选数据结构的拒绝时间、空间开销、 表示效率以及误判率。最后，根据给出的三方面评估指标，推导出拒 绝时间和空间开销的变化趋势、空间开销与表示性能的关系以及候选 数据结构内存表示与系统数据的一致性是否在可接受范围内。在这里 需要注意的是，具体的接受范围与实际硬件资源条件(例如内存大小 等)息息相关，因此，在此模型中只给出三方面的评估比较指标，并 不给出具体的阈值。

举例说明五种查存算法建模

1)位图数据结构

用位图来表示系统中的静态数据集，就是将位图中一个位用于表 示集合元素中对应的值，在这里假设我们的静态数据集中没有重复的 元素。与在相关工作里提到的简单位图索引的思路一样，即简单地将 每一个位表示每个不同的值。插入新元素时，将新元素在位图上的对 应位置1。在应答一个元素的成员查询的时候，直接查询该元素对应 位。例如，假设要表示集合{3,7,8,10}，若用位图的表示方案，则如图 4所示，位图中对应的第3位、第7位、第8位以及第10位均置1。 简单的位图方案在集合范围不大的时候，在空间上和查询处理时间上 很有效。但是，随着集合范围的增加，相应的空间开销也会随之增大， 因而引起了稀疏问题。

位图数据结构的建模描述如下：

1)D＝{U,M}，其中，U是全集，M是由位图数据结构BM的 位数组上连续的空间单元组成的置位集合，M中每个元素是一 个比特位的空间单元，且|M|＝n_m，n_m表示BM的位数组的长 度。

2)R＝{R₁,R₂}，其中R₁＝<d,M^r>，d∈DS，DS是已存集 合，M^r表示从BM的置位集合中选择r个比特位置位， 其中r＝1。R₂＝<M^t,S>表示BM的置位集合中选择t个元素 置位后，M^t对应的表示集合S。

3)F＝{f:U→M^r,query(d)}，其中f:U→M^r，且r＝1， dom(f)＝DS，d∈TS，TS是测试集合，

2)标准型布隆过滤器

布隆过滤器是用于判断一个元素是否在集合中的数据结构，是一 个由m个比特位的位数组，具有k个独立的哈希函数，每个哈希函数 的映射范围落在范围{1,2,3…m}，用于产生置位的比特位。

初始时，该数据结构，即该位数组的m个比特位均为0。当一个 元素插入集合中时，布隆过滤器将分别计算这k个独立的哈希函数， 然后根据结果，将位数组的对应位置1。在检测一个元素是否在集合 中时，布隆过滤器将根据该元素的值计算相应的k个哈希值，求出位 数组中对应的k个位，然后检测这k个位是否全部置1，若有任意一位 是0，则可判断该元素不在集合中，若全部为1，则该元素有可能在 集合中，也有可能不在集合中。显然，当检测元素存在性时，若对应 的k位全部置1，元素有不存在的可能性。

如图5所示，最初布隆过滤器初始值为0，元素x₁，x₂分别通过 哈希函数将对布隆过滤器相应位的置1。而在检测元素y₁和y₂是否在 布隆过滤器所表示的集合中时，分别计算它们的对应位，易见y₁对应 的位中有一个位为0，可以确定它不在集合中。而对于y₂对应的位全 是1，因此，要么在布隆过滤器表示的集合中，要么只是一个假阳性 的误差。标准型布隆过滤器的建模描述如下：

1)D＝{U,M}，其中，U是已存集合DS的全集，M是由标准型 布隆过滤器BF的位数组上连续的空间单元组成的置位集合， M中每个元素是一个比特位的空间单元，且|M|＝n_m，n_m表 示BF的位数组的长度。

2)R＝{R₁,R₂}，其中R₁＝<d,M^r>，d∈DS，DS是已存集 合，M^r表示从布隆过滤器BF的置位集合，即这个位 数组中选择r个比特位置位。R₂＝<M^t,S>表示布隆过滤器BF 的位数组中选择t个比特位置位后，M^t对应的表示集合S。

3)F＝{f:U→M^r,query(d)}，其中f:U→M^r，且r＝k，布 隆过滤器BF的哈希函数个数，d∈TS，TS 是测试集合，$\mathrm{TS}\subseteq U.$

3)计数型布隆过滤器

计数型布隆过滤器是通过将布隆过滤器的位数组扩展成统计该 位置被置1的次数的数据结构，以弥补布隆过滤器无法删除元素的局 限。在这个数据结构中，布隆过虑器的每个记录就是一个与基本的布 隆过滤器相关的小型计数器，用于记录该位被设为1值的次数。最初， 这些计数器全部初始化为0。当一个元素a插入或删除时，布隆过滤 器将分别计算这k个独立的哈希函数，然后根据得出的结果，将位数 组的对应位置的计数器，进行相应地自增或自减， 例如，(c(h₁(a)),c(h₂(a)),…,c(h_k(a)))。与标准型布隆过滤器一样， 在进行元素的成员查询时，计数型布隆过滤器将根据该元素的值计算 这k个哈希函数，分别求出该元素在位数组中对应的k个位的计数器， 如果任意一个为0，则可判断该元素不在计数型布隆过滤器这个数据 结构所表示的集合。若对应的计数器全部是非0，与标准型布隆过滤 器一样，该元素有可能存在集合中，也存在这只是一个假阳性误差的 可能性。如图6所示，最初布隆过滤器初始值为0，元素x₁，x₂分别 通过哈希函数将对布隆过滤器相应位的置1，发生碰撞的位，于是计 数器自增1。计数型布隆过滤器CBF＝(D,R,F)的算法建模描述如下：

1)D＝{U,M}，其中，U是已存集合DS的全集，M是由计数型 布隆过滤器BF的位数组上连续的空间单元组成的置位集合， M中每个元素是由若干比特位(记为b个比特位)组成的空间 单元，对应于CBF的每个计数器，且|M|＝n_m，n_m表示CBF的 计数器的个数。

2)R＝{R₁,R₂}，其中R₁＝<d,M^r>，d∈DS，DS是已存集 合，M^r表示从CBF的置位集合，即CBF的m个计数 器中选择r个计数器进行自增1的置位。R₂＝<M^t,S>表示 CBF中有t个计数器进行自增1的置位后，M^t对应的表示集合S。

3)F＝{f:U→M^r,query(d)}，其中f:U→M^r，且r＝k，k是 CBF的哈希函数个数，d∈TS，TS是测试 集合，$\mathrm{TS}\subseteq U.$

4)Dynamic Bloom Filter

Dynamic Bloom Filter是一个动态的s×m位矩阵，该矩阵包含 s个标准的(或计数型)布隆过滤器。该矩阵包含s个大小是m，哈希 函数个数是k标准型布隆过滤器(或计数型布隆过滤器)。在一个特定 时间，Dynamic Bloom Filter中仅有一个布隆过滤器是活动，其他 均非活动状态。插入布隆过滤器的元素的个数将会被跟踪。当插入元 素时，第一个拥有该元素计数器小于特定的阈值的布隆过滤器将被选 为活动的布隆过滤器。如果这个活动的布隆过滤器不能找到，将创建 新的并设为活动的布隆过滤器，然后元素将插入活动布隆过滤器。当 进行成员查询操作时，将对集合中的布隆过滤器进行迭代，若任一个 布隆过滤器包含该元素，则返回真值。若这个矩阵是由计数型布隆过 滤器组成，则可以删除元素，因此，在删除元素时，需要找到第一个 声称含有该元素的子布隆过滤器。只有一个布隆过滤器声称含有该元 素的情况下，只需要将对应的位自减1即可，多于一个布隆过滤器的 情况下，元素的删除最多会导致k个潜在的假阴性错误。在这种情况 下，若保留不存在假阴性的错误，则元素的位不能自减，这样就删除 操作失败，会增加一定的假阳性错误率。Dynamic布隆过滤器 DY＝(D,R,F)的建模描述如下：

1)D＝{U,M}，其中，U是已存集合DS的全集，M是由s个标 准型布隆过滤器BF(或计数型布隆过滤器CBF)的位数组上 连续的空间单元组成的置位集合并集，记为M＝M₁∪M₂…∪ M_s，M_i中每个元素是由若干个比特位组成的空间单元，且 |M_i|＝m，1≤i≤s，m表示BF(或CBF)的位数组的长度， 因此，置位集合的元素个数M＝n_m。

2)R＝{R₁,R₂}，其中R₁＝<d,M_i^r>，d∈DS，DS是已存集 合，M_i^r表示从矩阵中第i个活跃BF(或CBF)的置 位集合中，选出r个元素置位。R₂＝<M_i^t,S_i>表示第i个活跃 BF(或CBF)的位数组中选择t个比特位置位后，M^t对应的表 示集合S_i，于是可得整个Dynamic布隆过滤器DY的表示集合 $S={\cup }_{i=1}^s{S}_i.$

3)F＝{f:U→M^r,query(d)}，其中f:U→M^r，且r＝k，BF (或CBF)的哈希函数个数，d∈TS，TS是 测试集合，$\mathrm{TS}\subseteq U.$

5)D-left布隆过滤器

D-left哈希和指纹(fingerprint)的数据结构，将哈希表分成 d个子表，每个子表大小相同，并且有n/d个桶，其中n是桶的总数。 对于每个元素，都会通过哈希函数产生一个指纹(fingerprint)，这 个指纹(fingerprint)包含两部分，一部分是桶索引，另一部分是 剩余指纹(remainder)，桶索引是指存放剩余指纹(remainder)的 桶地址。而每个桶有c个单元(cell)的空间，每个单元是一些具有 固定大小的位，用于存储剩余指纹(remainder)和计数器。

如图7所示，假设哈希表分成4个子表，每个子表中分别含有8 个桶，每个桶有4个单元。当插入元素时，计算该元素的哈希值 f_x＝H(x)＝(b,r)，选出d个子表中相同位置的候选桶和一个指纹哈希 值(fingerprint)。然后，用附加的(伪随机的)随机排列计算出与 f_x对应的d个位置以及相应的指纹P_i(f_x)＝(b_i,r_i)，其中1≤i≤d。这 样做是为了使得给定元素，它的存储在子表中的指纹各不相同。接着， 先检测对于任意的剩余指纹(remainder)r_i是否存在于任意桶b_i中， 如果是，就将相应的计数器加1。否则，将该指纹插入到元素最少的 子表中。在平均情况下，则放到最左边的子表的桶里。查询时，元素 的查询利用d个子表的并行查询，找出剩余指纹(remainder)和包含 该值的计数器。删除时，计数器减1。这些计数器比标准的Counting  Bloom Filter要少得多，主要原因是由基于指纹的D-left构造产生 较少的碰撞。

假设k表示子表个数，m表示每个子表包含桶的个数，c表示每个 桶包含的单元个数，D-Left布隆过滤器DL＝(D,R,F)的建模描述如 下：

1)D＝{U,M}，其中，U是已存集合DS的全集，M是由D-Left 布隆过滤器上的每个子表的所有桶组成的置位集合，相当于每 个子表中的桶组成的集合的并集，形式化描述为M＝M₁∪ M₂…∪M_k，其中M_i中每个元素是由c个D-Left布隆过滤器中 的单元(cell)组成，每个单元包含若干比特位(记为b个比 特位)，|M|＝n_m，n_m表示DL的所有桶的总数，因此， n_m＝k·m。

2)R＝{R₁,R₂}，其中R₁＝<d,M^r>，d∈DS，DS是已存集 合，M^r表示从DL的置位集合，选择r个单元(cell) 进行存放指纹和计数器自增1的置位。R₂＝<M^t,S>表示DL 中有t个单元(cell)存放指纹后，M^t对应的表示集合S。

3)F＝{f:U→M^r,query(d)}，其中置位映射f:U→M^r， r＝1，即每次映射时只选择1个桶(cell)作为存放剩余指 纹(remainder)的桶地址，d∈TS，TS 是测试集合，$\mathrm{TS}\subseteq U.$

以上是对本发明的较佳实施进行了具体说明，但本发明创造并不 限于所述实施例，熟悉本领域的技术人员在不违背本发明精神的前提 下还可以作出种种的等同变换或替换，这些等同的变形或替换均包含 在本申请权利要求所限定的范围内。