随着计算机技术的发展,通信时用到的数据集合的尺寸在逐渐增大,涉及到的应用数量也在逐步增加,人们希望能够使用一种更紧凑的数据结构处理海量数据集。在计算机系统和应用中,为人熟知的集合操作正是一种最基础的操作,处理数据集的效率与集合查询的效率紧密相关。在本文中关注的正是如何高效处理集合查询的问题。在集合查询问题中,效率主要集中在三个方面:内存存取次数,查询时间,正确率。传统处理海量数据集的经典方法之一是布隆过滤器(Bloom Filter)。本文通过对布隆过滤器进行修改,设计并提出了一种新的改进的布隆过滤器ShBF(ShiftingBloomFilter),该算法既可用于存储数据,也可用来进行集合查询。其优势是进行集合查询时,既能够比传统的布隆过滤器的内存使用量和操作时间更少,又不会导致错误率明显上升。为了展示算法的查询效率,本文一共选择了三种常见的集合查询:元素查询(membership queries),联合查询(association queries)和重复元素查询(multiplicity queries)。ShBF的创新点在于使用偏移量对算法结构进行优化,使得新的算法能够充分利用每次存取得到的数据,以记录更多的信息。因为使用布隆过滤器进行插入与查询时,每次存取的数据数量至少为一个机器字,而实际需要的只是其中一个二进制位。本文中将其余的比特位称为偏移量,ShBF通过使用集合元素自带的偏移量,将更多的信息编码写入其中,从而达到对布隆过滤器进行优化的目的。ShBF和布隆过滤器的主要区别在于如何存储附加信息,所谓附加信息是指元素的存在信息以外的信息。在布隆过滤器中需要应用程序分配更多的内存才能存储更多信息,而ShBF会将这些信息存储到元素的偏移量中。本文针对三种不同的集合操作,提供了三种ShBF的设计方案,并选择了经典的布隆过滤器改进算法进行对比。在测试阶段使用模拟产生的一系列数据及真实的网络数据进行评估,在内存使用,计算量,以及正确率多个方面进行评估,验证ShBF的性能优势。