Shifting Bloom Filters at Peking University, China

Explore the innovative research on Shifting Bloom Filters conducted at Peking University, China, featuring evaluations, conclusions, background information, and insights on membership, association, and multiplicity queries. The study delves into hash functions, theoretical results, and the Shifting Model's impact on query types. Discover how different offset values correspond to various query categories and the use of hash tables for efficient query processing.

• Peking University
• Bloom Filters
• China
• Hash Functions
• Query Processing

bluebell Follow

Uploaded on Aug 17, 2024 | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Peking University, China Shifting Bloom Filters Tong Yang, Alex X. Liu, Muhammad Shahzad, Yuankun Zhong Qiaobin Fu, Zi Li, Gaogang Xie, Xiaoming Li 17 August 2024

2. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity 1. Membership query 2. Association query 3. Multiplicity query 17 August 2024 2

3. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity element e set S1 set S2 Question 1. e in S1 ? --- Membership Query Question 2. e in S1 or S2 ? --- Association Query Question 3. e s quantity in S1 ? --- Multiplicity Query 17 August 2024 3

4. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Question 1. e in S ? --- Membership Query Solution I: Traversing the set. O(n) Solution II: Using hash tables. O(1), large memory, worst case is unbounded. 17 August 2024 4

5. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity More hash functions or Standard Bloom filters e less hash functions? k=m/n * ln2 f=0.5^k 1 1 1 17 August 2024 5

6. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Shifting Model Different offset(x) corresponds to different kinds of queries. x c: the max value of offset(x) offset(x) offset(x) 1 2 m m+c 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 Each hashing read c bits when querying Hashing range 0~m, additional c bits for offset 17 August 2024 6

7. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Membership query x hk/2+1(x) hk/2+1(x) hk/2+1(x) 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 a Word 17 August 2024 7

8. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Theoretical Results: 0.10 n 4000 0.08 ? = 0.6185? n 6000 ? ?= 0.6931 ? n 10000 ? = ln2 Bloom filter: FPrate n 8000 0.06 ? ? 0.04 ? = 0.6204? n 12000 ? = 0.7009 ? ShBFM: 0.02 ? ? 0.00 0 5 10 k 15 20 17 August 2024 8

9. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Association Query: BF1 BF2 Overhead: 1) 2k hash computations 2) 2k memory accesses 3) False positives Our goal: 1) k hash computations 2) k memory accesses 3) No false positives k: # hash functions 17 August 2024 9

10. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ?1-S2 ?? ?? ?? ?? x:3 2 2 1 2 m m+3 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 Each hashing reads 3 bits 17 August 2024 10

11. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity 1. Only e S1 S2,S1 S2 2. Only e S1 S2,S1 S2 3. Only e S2 S1,S2 S1 4. Both e S1 S2 and e S1 S2, ?1 ?1 ?3 ?2, 5. Both e S1 S2 and e S2 S1, ?2 ?3 = ?1 ?2 6. Both e S1 S2 and e S2 S1, !(S1 S2) 7. e S1 S2,e S2 ?1 ??? S1 S2 S1 S2 17 August 2024 11

12. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Si : all the elements which have i multiplicities. x B1 Query x in hash table x:4 2 m+1 B2 OR report t times OR Bg m+g-1 OR g Delete x:t-1 from CShBF_C 3 3 1 2 m m+c m+g-1 1 1 g-1 m+1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 nr BA = update ShBF_C Each hashing read c bits OR Insert x: t into ShBF_C Hashing range 0~m, additional c bits for offset 1 m r BA = 17 August 2024 12

13. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Experimental Setup 10Gbps link of a backbone router 5-tuple flow ID of each packet: source IP, source port, destination IP, destination port, and protocol type. 10 million 5-tuple flow IDs, out of which 8 million flow IDs are distinct 17 August 2024 13

14. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFM: Membership Query --- FP rate 0.06 1MemBF simulation of ShBFM Theory of ShBFM 0.05 0.04 FP rate 0.03 0.02 0.01 0.00 4 6 k (m=22976, n=2000) 8 10 12 14 16 17 August 2024 14

15. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFM: Membership Query --- FP rate 0.008 theory of ShBFM (m=22008) simulation of ShBFM (m=22008) 1MemBF (m=22008) 1MemBF (m=22008*1.5) 0.007 0.006 0.005 FP rate 0.004 0.003 0.002 0.001 0.000 1000 1100 1200 n (k=8) 1300 1400 17 August 2024 15

16. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFM: Membership Query --- FP rate 0.055 1MemBF simulation of ShBFM Theory of ShBFM 0.050 0.045 0.040 0.035 FP rate 0.030 0.025 0.020 0.015 0.010 0.005 0.000 32000 34000 36000 38000 40000 42000 44000 m (n=4000, k=6) 17 August 2024 16

17. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFM: Membership Query ---- Query Speed (Mqps) 18 BF 1MemBF ShBFM Query speed (Mqps) 16 14 12 10 8 6 4 1000 1200 1400 1600 1800 2000 n (m=22008, k=8) 17 August 2024 17

18. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFM: Membership Query ---- Query Speed (Mqps) 22 BF 1MemBF ShBFM Query speed (Mqps) 20 18 16 14 12 10 8 6 4 2 4 6 k (m=33024, n=1000) 8 10 12 14 16 17 August 2024 18

19. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFM: Membership Query ---- Query Speed (Mqps) 20 BF 1MemBF ShBFM Query speed (Mqps) 18 16 14 12 10 8 6 4 32000 34000 36000 38000 40000 42000 44000 m (k=8, n=4000) 17 August 2024 19

20. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFA: Association Query iBF ShBFA 12 Query speed (Mqps) 10 8 6 4 2 0 4 6 8 10 k 12 14 16 18 17 August 2024 20

21. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFX: Multiplicity Query 2.4 theory of ShBFX simulations of ShBFX simulations of Spectral BF simulations of CM Sketch 2.2 2.0 Correctness rate 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0 8 9 # of hash functions -- k 10 11 12 13 14 15 16 17 August 2024 21

22. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFX: Multiplicity Query 18 # of memory accesses Spectral BF ShBFX CM sketch 16 14 12 10 8 6 4 2 3 4 5 6 # of hash functions -- k 7 8 9 10 11 12 13 14 15 16 17 August 2024 22

23. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity ShBFX: Multiplicity Query Query speed (Mqps) 10 Spectral BF ShBFX CM Sketch 8 6 4 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 # of hash functions -- k 17 August 2024 23

24. Shifting Bloom Filters Peking University, China Evaluation Conclusion Background Membership Association Multiplicity Key Contributions: 1. We propose Shifting Bloom Filter, a general framework to answer a variety of set queries. 2. We present how to use ShBF to answer three important set queries, i.e., membership, association, and multiplicity queries. 3. We validated our analytical models through simulations using real world network traces. The source codes of our ShBF and prior art are available at http://net.pku.edu.cn/~yangtong/ 17 August 2024 24

25. Peking University, China Thanks! 17 August 2024 IWQoS 2015 25