Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams

The unparalleled growth and popularity of the Internet cou-pled with the advent of diverse modern applications such as search engines, on-line transactions, climate warning sys-tems, etc., has catered to an unprecedented expanse in the volume of data stored world-wide. Efficient storage, man-agement, and processing of such massively exponential amount of data has emerged as a central theme of research in this direction. Detection and removal of redundancies and du-plicates in real-time from such multi-trillion record-set to bolster resource and compute efficiency constitutes a chal-lenging area of study. The infeasibility of storing the entire data from potentially unbounded data streams, with the need for precise elimination of duplicates calls for intelligent approximate duplicate detection algorithms. The literature hosts numerous works based on the well-known probabilistic bitmap structure, Bloom Filter and its variants. In this paper we propose a novel data structure, Streaming Quotient Filter, (SQF) for efficient detection and removal of duplicates in data streams. SQF intelligently stores the sig-natures of elements arriving on a data stream, and along with an eviction policy provides near zero false positive and false negative rates. We show that the near optimal per-formance of SQF is achieved with a very low memory re-quirement, making it ideal for real-time memory-efficient de-duplication applications having an extremely low false positive and false negative tolerance rates. We present de-tailed theoretical analysis of the working of SQF, providing a guarantee on its performance. Empirically, we compare SQF to alternate methods and show that the proposed method is superior in terms of memory and accuracy compared to the existing solutions. We also discuss Dynamic SQF for evolving streams and the parallel implementation of SQF