Learning-based data structures combine a learned model with auxiliary structures to efficiently handle large-scale data. By leveraging data distribution through a learned model, such structures can significantly improve search performance under limited memory. In this paper, we propose a partitioned learned functional Bloom filter (PL-FBF), which comprises a learned model and multiple partitioned functional Bloom filters (FBFs). The PL-FBF supports both membership checks and key–value retrieval, as in a single FBF, but achieves a lower search failure rate through prediction-based partitioning and adaptive memory allocation. The PL-FBF introduces a twolevel partitioning strategy: inter-group partitioning based on predicted classes, and intra-group partitioning based on predicted probabilities, enabling fine-grained memory allocation tailored to data characteristics. Furthermore, unlike prior learning-based structures, the PL-FBF can be constructed without negative data, making it applicable even when negative samples are unavailable for training. We also present a theoretical analysis of the search failure probability of an FBF for skewed data and derive optimal size factors for intra-group partitions. Experiments show that the PL-FBF reduces the search failure rate compared to a single FBF under the same memory and achieves its best performance when using the theoretically optimal size factors.

Set reconciliation between different hosts to hold the same dataset is an important prerequisite in numerous distributed applications. Sending the entire dataset to achieve set reconciliation is inefficient if the majority of the data owned by each host is the same. Each host is required to send exclusive elements uniquely included in its set to the other to minimize communication complexity. This paper proposes an efficient algorithm for a host to identify its exclusive elements using the recursive comparison of ternary Bloom filters, each representing the signature of a subset of elements and used for filtering out subsets with identical elements. Hence, subsets with exclusive elements are identified, and elements included in the identified subsets are programmed to an invertible Bloom filter (IBF) to be sent to the other host. Thus, the number of elements programmed in the IBF is significantly reduced. Simulation results show that the proposed algorithm provides excellent performance compared with existing set reconciliation algorithms under the constraint of the same amount of data communication.

As a challenging attempt to replace a traditional data structure with a learned model, this paper proposes a learned functional Bloom filter (L-FBF) for a key--value storage. The learned model in the proposed L-FBF learns the characteristics and the distribution of given data and classifies each input. It is shown through theoretical analysis that the L-FBF provides a lower search failure rate than a single FBF in the same memory size, while providing the same semantic guarantees. For model training, character-level neural networks are used with pretrained embeddings. In experiments, four types of different character-level neural networks are trained: a single gated recurrent unit (GRU), two GRUs, a single long short-term memory (LSTM), and a single one-dimensional convolutional neural network (1D CNN). Experimental results prove the validity of theoretical results, and show that the L-FBF reduces the search failures by 82.8% to 83.9% when compared with a single FBF under the same amount of memory used.