PROJECT TITLE :

Multiset Membership Lookup in Large Datasets

ABSTRACT:

The multiset membership lookup function takes an item as input and returns a binary answer indicating whether or not the item belongs to the dataset S and, if it does, the identifier of the subset to which the item belongs if it is determined that the item does belong to one of the g subsets in the dataset. The multiset membership lookup emerges as a pivotal functionality in many different computing and networking paradigms. This lookup is an overlay on the canonical membership lookup, and it is more sophisticated than the canonical membership lookup. The design of a lookup algorithm is a challenging task, and it is made even more difficult when the data items arrive in the form of a stream because of the goal of achieving high-speed, high-accuracy lookup with limited memory cost. In this article, we develop compact data structures and lookup algorithms that are amenable for hardware implementation. These algorithms and data structures guarantee a high level of lookup accuracy and support interactive query processing. We begin by presenting multi-hash color table, a modification of Bloom filter, with the goal of efficiently encoding subset IDs and mapping the ID of an item to its respective subset ID. We further construct a data structure that is more balanced by calling it a balanced multi-hash color table in order to improve the compactness by integrating a load balancing technique that is considered to be state-of-the-art. We finish our work by addressing the case of batch arrivals and designing a batched recording algorithm with the goal of optimizing the efficiency of memory use. In order to characterize and evaluate the performance of the proposed algorithms in terms of lookup accuracy, memory efficiency, and access efficiency, we provide both theoretical and empirical analysis.