A Shifting Framework for Set Queries

Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.National Basic Research Program of China [2014CB340400]; Primary Research & Development Plan of China [2016YFB1000304]; NSFC [61472009, 61672061]; Open Project Funding of CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences; Special Fund for Strategic Pilot Technology, Chinese Academy of Sciences [XDA06010302]; National Science Foundation [CNS-1318563, CNS-1524698, CNS-1421407, CNS-1616317, IIP-1632051]; Shenzhen Research Project [JCYJ20160330095313861]; National Natural Science Foundation of China [61472184, 61321491]; Jiangsu Innovation and Entrepreneurship (Shuangchuang) ProgramSCI(E)ARTICLE53116-31312