所属领域： A 电子信息技术

技术成果简介

现有技术的基于布谷鸟过滤器的集合成员管理方法中，算法基本上都在遵循随机选择策略，所以导致集合成员管理过程中效率低及候选桶指纹信息插入不均衡等情况，虽然现有技术中有方案在插入成员时选择候选桶的过程中满足了候选桶之间插入的负载均衡，但当两个候选桶满载时，又会因为负载均衡的缘故导致某个候选桶出现过载，导致算法失效；其次，发生重定位操作时现有的布谷鸟过滤器大多数都无法区分集合成员是否发生过重定位操作，这将导致一个成员重复发生重定位操作，即有可能陷入循环重定位操作，大量消耗时间。同样的，由于成员重定位算法也是遵循随机选择策略，即随机从候选桶中选择成员踢出换到另一个候选桶中，期间很可能导致一个成员刚插入就因为被选中踢出进行重定位操作两次而成为孤儿成员，虽然现有技术中也有发明解决了该问题，但是其存在存储效率低及空间利用率低等情况。针对现有技术中的上述不足，本发明涉及集合成员管理技术。本发明提供了一种基于先进先出及最小活跃数策略的集合成员管理方法，其技术方案可概括为：包括基于先进先出及最小活跃数策略的集合成员插入方法、基于先进先出及最小活跃数策略的集合成员判定方法及基于先进先出及最小活跃数策略的集合成员删除方法。本发明克服了现有集合成员管理方法中负载不均衡及插入时采用随机选择策略会产生额外遍历桶空白位置的时间开销的问题，克服了现有集合成员判定过程中遍历查询时时间开销较大的问题，以及克服了现有集合成员删除过程中数据紧凑技术的效率较低的问题，适用于集合成员管理方法。

技术成果前景

在本发明方案中，通过上述基于先进先出及最小活跃数策略的集合成员管理方法中的基于先进先出及最小活跃数策略的集合成员插入方法可见，其通过采用基于最小活跃数策略的自适应负载均衡策略对集合成员指纹信息存放的候选桶进行选择，克服了现有技术下因候选桶满载而导致的插入负载均衡算法的失灵，保证了该算法能够在不同情况下保证各候选桶的指纹数趋近于一致，达到一种候选桶之间装载指纹数均衡的效果，同时其摒弃了随机选择的策略而采用了先进先出的策略，即在插入成员集合指纹信息至候选桶时，按照插入的先后顺序依次排列在候选桶中，同样通过上述重定位操作步骤可见，在发生重定位操作时，选择最久最远入桶的指纹信息作为替换出桶的指纹信息，通过这样可以有效减少集合成员的指纹信息发送多次重定位操作，提高集合成员的插入效率；且通过采用了三区一标签的构造方式， 能够使孤儿指纹信息的数量尽可能少的同时，明确每一个指纹信息所发生的重定位次数（这里的重定位次数是指未重定位，即重定位标志值为0；重定位一次，即重定位标志值为1；及重定位两次，即重定位标志值为2，通过上述方法可见，重定位操作不会针对缓存区中的集合成员，则缓存区中的集合成员不会被重定位），避免因为无法标识指纹信息所发生的重定位次数而导致该指纹信息进行循环重定位操作，由此能够提高运行效率，同时针对机构特点，提出一种数据紧凑技术，通过将缓存区中的集合成员整理搬移至未满载的存储区中，避免缓存区存储资源浪费，提高存储区存储资源的运用，大大提高空间利用率。通过上述基于先进先出及最小活跃数策略的集合成员管理方法中的基于先进先出及最小活跃数策略的集合成员判定方法及删除方法可见，其分别采用基于先进先出策略的成员判定法遍历查询桶存储区，能够保证当桶状态为满桶时，其时间复杂度与顺序遍历相当，而当桶为非满载桶时，时间开销小于顺序查找遍历的时间开销，尽可能的减少了查询次数，提高了遍历查询效率。