Noisy Bloom Filters For Multi-set Membership Testing

This thesis is on designing a compact data structure for multi-set membership test-ing allowing fast set querying.Multi-set membership testing is a fundamental operation for computing systems and networking applications.For example,for frame forward-ing in a layer-2 switch,multiple MAC addresses are mapped to a single port and fast querying for the associated port for a MAC address is crucial for frame forwarding.Here,MAC addresses correspond to elements and the associated port corresponds to the set.Most existing schemes for multi-set membership testing are built upon Bloom fil-ter,and fall short in either storage space cost or query speed.On one hand,some prior art adopts a general framework that divides the whole storage space into multiple uniform cells and uses one or more cells to record set IDs of element.This coarse granularity for storing set IDs leads to inefficient use of storage space.On the other hand,other prior art mainly falls short in memory access overhead and query processing speed.Most of proposed schemes in these works assign multiple dedicated Bloom filters for recording set ID information.Consequently,the memory accesses of these schemes are generally several times higher than standard Bloom filters depending on the number of established Bloom filters,which results in much lower query processing speed.To address this issue,this thesis proposes Noisy Bloom Filter(NBF)and Error Corrected Noisy Bloom Filter(NBF-E)for multi-set membership testing.For theoreti-cal analysis,this thesis optimizes their classification failure rate and false positive rate,and present criteria for selection between NBF and NBF-E.The key novelty of NBF and NBF-E is to store set ID information in a compact but noisy way that allows fast recording and querying,and use denoising method for querying.Especially,NBF-E incorporates asymmetric error-correcting coding tech-nique into NBF to enhance the resilience of query results to noise by revealing and leveraging the asymmetric error nature of query results.To evaluate NBF and NBF-E in comparison with prior art,this thesis conducted experiments using real-world network traces.Experiment result shows that NBF and NBF-E significantly advance the state-of-the-art on multi-set membership testing.In addition,the disclosure of inherent asymmetric error property of Bloom filters and proposition of adopting AEC codes would shed light to future researches including not only NBF-E extensions but also other Bloom filer based schemes.