2019/12/16 by Yue Fu, Fu, Yue, Rong Du +7
Computer Science · Materials Science · #Caching and Content Delivery #Carbon and Quantum Dots Applications #Covalent Organic Framework Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1912.07153
openalex publication_date 2019/12/16 · openalex created_date 2019/12/26 · openalex updated_date 2026/07/28
With the growing scale of big data, probabilistic structures receive increasing popularity for efficient approximate storage and query processing. For example, Bloom filters (BF) can achieve satisfactory performance for approximate membership existence query at the expense of false positives. However, a standard Bloom filter can only handle univariate data and single membership existence query, which is insufficient for OLAP and machine learning applications. In this paper, we focus on a common multivariate data type, namely, 2-tuples, or equivalently, key-value pairs. We design the matrix Bloom filter as a high-dimensional extension of the standard Bloom filter. This new probabilistic data structure can not only insert and lookup a single 2-tuple efficiently, but also support these operations efficiently in batches --- a key requirement for OLAP and machine learning tasks. To further balance the insertion and query efficiency for different workload patterns, we propose two variants, namely, the maximum adaptive matrix BF and minimum storage matrix BF. Through both theoretical and empirical studies, we show the performance of matrix Bloom filter is superior on datasets with common statistical distributions; and even without them, it just degrades to a standard Bloom filter.