Fuse Multi-Map: A Fast, Accurate, and Memory-Efficient Multi-Set Query Structure with Privacy Extension

Abstract

Multi-Set Query (MSQ) is a fundamental task in computer networks and database systems, which can determine which set an element belongs to within multi-sets. Previous MSQ solutions struggle to balance query speed, query accuracy, and memory usage. To address this issue, we propose a novel MSQ structure called Fuse Multi-Map (FMM), which is fast, error-free, has low false positives, and is memory efficient. The key idea is to store and check the element-set ID pairs and the corresponding fingerprints using a random hash-based hypergraph. Compared to the state-of-the-art baselines with the same memory usage, FMM reduces the false positive rate by at least an order of magnitude, while query speed is approximately 5.87× ∼ 21.23× faster. Furthermore, we initiate the study of Encrypted MSQ (EMSQ), which allows MSQ on encrypted data. EMSQ is widely applicable in data privacy protection scenarios, such as deep packet inspection over encrypted traffic. We give a formal definition of EMSQ and formalize its security model. To our knowledge, we present the first EMSQ construction, Encrypted FMM (EFMM), from the FMM and pseudo-random function (PRF), and demonstrate that EFMM is adaptive-secure. The comparative evaluation shows that EFMM also outperforms other MSQ schemes.

Keywords

Multi-set Query / Encrypted Multi-set Query / Data Privacy

RIGHTS & PERMISSIONS

Higher Education Press 2026

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.