Multiset Membership Lookup in Large Datasets

Given a dataset S composed of g subsets with each data item belonging to one of them, multiset membership lookup takes an item e as input and outputs a binary answer whether e∈S and, in case of yes, the ID of the subset to which e belongs. Overlaid upon while more sophisticated than the canonical membership lookup, multiset membership lookup emerges as a pivotal functionality in many computing and networking paradigms. The quest to achieve high-speed, high-accuracy lookup with limited memory cost makes lookup algorithm design a challenging task, particularly when the data items arrive as a stream. In this paper, 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 the state-of-the-art load balancing technique. We complete our work by addressing the case of batch arrivals and design a batched recording algorithm optimizing the memory efficiency. We give both theoretical and empirical analysis to characterize and evaluate the performance of the proposed algorithms in terms of lookup accuracy, memory and access efficiency.