Multiset Membership Lookup in Large Datasets (Extended abstract)

We investigate multiset membership lookup prob-lem, a pivotal functionality in many computing and networking paradigms. We devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first propose multi-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure called balanced multi-hash color table to improve the compactness by integrating load balancing.