동적 데이터를 위한 분할된 학습 블룸필터 기반 구조

이예지,변하영 대한전자공학회 2023 전자공학회논문지 Vol.60 No.10

학습 블룸필터(Learned Bloom filter, LBF)는 학습 모델과 하나의 보조 블룸필터(Bloom filter, BF)를 사용하여 표준 BF를 대체한 학습 기반 구조이다. 분할된 학습 블룸필터(Partitioned learned Bloom filter, PL-BF)는 LBF를 변형한 구조로써, 학습된 모델과 모델의 데이터 확률분포에 따른 분할된 BF들을 사용하여 LBF보다 성능을 향상시킨 구조이다. 그러나 PL-BF는 저장된 데이터를 삭제할 수 없다는 단점을 가진다. 본 논문에서는 삽입과 삭제가 잦은 동적 데이터를 위해 분할된 학습 카운팅 블룸필터(Partitioned learned counting Bloom filter, PL-CBF)와 분할된 학습 쿼터너리 블룸필터(Partitioned learned quarternary Bloom filter, PL-QBF), 총 2가지 종류의 PL-BF 변형구조를 제안한다. 제안하는 PL-CBF와 PL-QBF는 모델의 데이터 확률 분포를 5개의 영역으로 나누고, 각각 다른 사이즈 팩터를 갖는 5개의 카운팅 블룸필터(Counting Bloom filter, CBF), 쿼터너리 블룸필터(Quarternary Bloom filter, QBF)를 사용한다. 실험을 통해, 제안하는 구조가 삭제 기능을 제공하여 동적 데이터 처리에 적합함을 보였으며, 동일한 전체 메모리 사용량 하에서, CBF, QBF와 비교하여 PL-CBF, PL-QBF이 각각 80% 이상 향상된 검색 성능을 보임을 확인하였다. A learned Bloom filter (LBF) is a learning-based structure that can replace a single standard Bloom filter (BF) with a learned model and an additional BF. A partitioned learned Bloom filter (PL-BF), a variant of the LBF, can improve search performance by partitioning the single additional BF into multiple smaller ones based on the data distribution of the learned model. However, the PL-BF does not support deletion operations. In this paper, we propose two variants of the PL-BF for dynamic data with frequent insertions and deletions: partitioned learned counting Bloom filter (PL-CBF) and partitioned learned quarternary Bloom filter (PL-QBF). The PL-CBF and PL-QBF divide the data distribution into five ranges and allocate five counting Bloom filters (CBFs) and five quarternary Bloom filters (QBFs) with different size factors to each range, respectively. Experiments show that the PL-CBF and PL-QBF effectively support data deletions and the structures are suitable for dynamic data processing. In addition, the search performance of PL-CBF and PL-QBF is improved by more than 80% compared to CBF and QBF, respectively, when using the same amount of memory.

Complement Bloom Filter for Identifying True Positiveness of a Bloom Filter

Hyesook Lim,Jungwon Lee,Changhoon Yim IEEE 2015 IEEE communications letters Vol.19 No.11

<P>The use of Bloom filters in network applications has increased rapidly. Since Bloom filters can produce false positives, the trueness of each positive needs to be identified by referring to an off-chip hash table. This letter proposes a new method for identifying the trueness of Bloom filter positives. We propose the use of an additional Bloom filter programmed for the complement set of the given set. In querying an input, if the complement Bloom filter produces a negative result, the input is a member of the given set since Bloom filters never produce a false negative. When both Bloom filters produce positives, a hash table needs to be referred to in our method. We provide a mathematical analysis, whereby the probability of referring to a hash table converges to the summation of the false positive probabilities of each Bloom filter. We provide the simulation result that the rate of referring to a hash table in our method is the order of 10<SUP>-5</SUP> for Bloom filter sizing factor 32.</P>

On Reducing False Positives of a Bloom Filter in Trie-Based Algorithms

Mun, Ju Hyoung,Lim, Hyesook The Institute of Electronics and Information Engin 2015 IEIE Transactions on Smart Processing & Computing Vol.4 No.3

Many IP address lookup approaches employ Bloom filters to obtain a high-speed search performance. Especially, it has been recently studied that the search performance of trie-based algorithms can be significantly improved by adding Bloom filters. In such algorithms, the number of trie accesses can be greatly reduced because Bloom filters can determine whether a node exists in a trie without actually accessing the trie. Bloom filters do not have false negatives but have false positives. False positives can lead to unnecessary trie accesses. The false positive rate must thus be reduced to enhance the performance of lookup algorithms applying Bloom filters. One important characteristic of trie-based algorithms is that all the ancestors of a node are also stored. The proposed algorithm utilizes this characteristic in reducing the false positive rate of a Bloom filter without increasing the size of the memory for the Bloom filter. When a Bloom filter produces a positive result for a node of a trie, we propose to check whether the ancestors of the node are also positives. Because Bloom filters have no false negatives, the negatives of any of the ancestors mean that the positive of the node is false. In other words, we propose to use more Bloom filter queries to reduce the false positive rate of a Bloom filter in trie-based algorithms. Simulation results show that querying one ancestor of a node can reduce the false positive rate by up to 67% with exactly the same architecture and the same memory requirement. The proposed approach can be applied to other trie-based algorithms employing Bloom filters.

맵리듀스 환경에서 블룸 필터를 사용한 적응적 조인 처리

배혜찬(Hye-Chan Bae),이태휘(Taewhi Lee),김형주(Hyoung-Joo Kim) 한국정보과학회 2013 정보과학회논문지 : 데이타베이스 Vol.40 No.4

대용량 데이터의 처리, 분석을 위해 분산 프로그래밍 모델인 맵리듀스가 여러 분야에서 활용되고 있다. 그러나 맵리듀스는 조인 연산을 처리할 때 조인되지 않는 레코드들까지 맵퍼에서 리듀서로 전송하는데, 이는 불필요한 네트워크 비용을 발생시켜 조인 성능을 저하시킨다. 이러한 문제를 개선하기 위해 맵리듀스에서 블룸 필터를 사용하여 리듀서로 전송되는 레코드를 미리 여과하는 조인 방법이 제안되었다. 하지만 블룸 필터에 삽입되는 원소 데이터의 개수가 너무 많아지는 경우, 필터의 이점을 기대할 수 없으며 필터를 사용하기 위한 추가적인 비용으로 인하여 블룸 필터를 사용하지 않고 처리하는 것보다 오히려 성능이 더 저하될 수 있다. 이에 본 논문은 주기적으로 블룸 필터의 효율성을 검사하여 필터의 사용여부를 동적으로 결정하는 적응적 조인 연산 기법을 제안한다. 이를 위해, 우리는 필터에 삽입된 키의 개수를 활용하여 블룸 필터의 양성 오류율을 추정하고, 필터가 비효율적이라고 판단된 경우, 그 시점 이후로는 필터를 사용하지 않고 조인 연산을 처리하도록 한다. 실험을 통하여, 제안한 기법이 기본 맵리듀스 조인과 블룸 필터를 사용한 조인 중 보다 나은 성능을 보이는 연산 방법을 적응적으로 선택함으로써 안정적인 조인 성능을 보장함을 확인한다. MapReduce, a distributed programming model, has been used in many fields to process and analyze large volumes of data. However, MapReduce has a limitation to process join operations in that it transmits all the records, including ones that are not joined, from mappers to reducers. This causes unnecessary network costs and degrades the join performance. To handle this problem, the join technique that filters out the redundant records using Bloom filters was proposed. Nevertheless, if the number of data elements inserted into Bloom filter is too large, the performance of the join processing with Bloom filters can be worse than that without Bloom filters, because of additional costs to use them. This paper proposes an adaptive join processing technique that dynamically determines whether to use Bloom filters by checking the efficiency of them periodically. For this purpose, we estimate the false positive rate of Bloom filters with the numbers of the elements inserted into them. If it is judged that the filters are inefficient, the join operation is processed without them. The experiments show that the proposed technique ensures the stable performance of the join processing by choosing the better technique adaptively between the basic MapReduce join and the join using Bloom filter.

Probabilistic Bloom Filter for Online Learning in Personalized Recommender Systems

유찬우,강환수,김희천 한국디지털콘텐츠학회 2019 한국디지털콘텐츠학회논문지 Vol.20 No.7

Bloom filters are used as embeddings in machine learning domain because of its characteristic of remembering items with less storage. As to online learning, a specific kind of bloom filter is needed, which can prevent filters being full as new items appear by decay. We compared bloom filters which can decay in perspective of precision and the degree of preservation of similarities between items using dataset for personalized recommendation. We also suggested a new bloom filter named as 'probabilistic bloom filter', which has two advantages. First, it showed higher precision than other filters at the expense of similarities between items while overall performance was the second to 'stable bloom filter' when it comes to precision-similarity trade-off. Second, even in a long term, it ensures that filters are not full or empty without continuous parameter calibration.

Approaches for Improving Bloom Filter-Based Set Membership Query

( Hyunyong Lee ),( Byung-tak Lee ) 한국정보처리학회 2019 Journal of information processing systems Vol.15 No.3

We propose approaches for improving Bloom filter in terms of false positive probability and membership query speed. To reduce the false positive probability, we propose special type of additional Bloom filters that are used to handle false positives caused by the original Bloom filter. Implementing the proposed approach for a routing table lookup, we show that our approach reduces the routing table lookup time by up to 28% compared to the original Bloom filter by handling most false positives within the fast memory. We also introduce an approach for improving the membership query speed. Taking the hash table-like approach while storing only values, the proposed approach shows much faster membership query speed than the original Bloom filter (e.g., 34 times faster with 10 subsets). Even compared to a hash table, our approach reduces the routing table lookup time by up to 58%.

검증 블룸 필터를 사용한 IP 주소 검색 알고리즘

이정원,임혜숙 한국정보과학회 2012 정보과학회논문지 : 시스템 및 이론 Vol.39 No.4

트라이의 레벨에 따른 이진 검색 알고리즘은 트라이에 기초한 IP주소 검색 알고리즘 중 가장 성능이 뛰어난 것으로 알려져 있다. 최근 레벨에 따른 이진 검색 알고리즘에 블룸 필터를 추가하여, 트라이에 노드가 존재하지 않는 경우 외부 해시 테이블로의 접근을 제한하여 성능을 향상시킨 구조가 제안되었다. 본 논문에서는 기존의 블룸 필터 사용 레벨에 따른 이진 검색 알고리즘에, 검증 블룸 필터를 추가하여 검색 성능을 더욱 향상시킨 알고리즘을 제안한다. 인터넷 라우터에서 사용된 실제 라우팅 데이터를 사용한 실험을 통해, 제안하는 구조에서는 평균 2-3번의 메모리 접근으로 IP주소 검색이 가능함을 보였다. Binary search on trie levels is known to be the most efficient IP address lookup algorithm among trie-based algorithms. Recently, a new algorithm that adds a Bloom filter to the binary search on trie levels is proposed. The Bloom filter avoids an unnecessary access to a hash table in case that there is no node in the corresponding level of the trie. This paper proposes a new IP address lookup algorithm that additionally adds cross-checking Bloom filters to the existing algorithm. Compared with the existing single Bloom filter algorithm, the proposed algorithm provides improved search performance by reducing the false positive rate of the Bloom filter. It is shown that an IP address lookup is performed by 2-3 accesses to external memory in average in our proposed scheme.

Name prefix matching using bloom filter pre-searching for content centric network

Lee, J.,Shim, M.,Lim, H. Academic Press 2016 JOURNAL OF NETWORK AND COMPUTER APPLICATIONS - Vol.65 No.-

<P>As a new networking paradigm for future Internet, content centric networking (CCN) technology provides a contents-oriented communication infrastructure for the rapidly increasing amount of data traffic. For the successful realization of CCN, it is essential to design an efficient forwarding engine that performs high-speed name lookup. This paper proposes the use of a hashing-based name prefix trie and a Bloom filter. In the proposed approach, an off-chip hash table storing the nodes of the name prefix trie is only accessed when the Bloom filter states that the node under querying exists in the trie. In accessing the node depending on the result of the Bloom filter, we propose two algorithms that have different strategies. The first algorithm accesses the the node for every positive result of the Bloom filter, while the second algorithm first attempts to determine the longest matching length using Bloom filter queries. Trie nodes are accessed from the possible longest length, and tracked back if there is no match. Simulation results show that the proposed approach can provide the output face of each input name, with a single node access on average and with two node accesses in the worst-case using a reasonable size of a Bloom filter. (C) 2016 Elsevier Ltd. All rights reserved.</P>

New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based Algorithms

Ju Hyoung Mun,Hyesook Lim IEEE 2016 IEEE Transactions on Computers Vol.65 No.5

<P>IP address lookup operation determines the longest prefix matching each incoming destination address. As a fundamental operation for packet forwarding at Internet routers, search speed for routing table lookup is the most important performance metric. Previous researches have shown that the search performance of trie-based algorithms can be improved by adding on-chip Bloom filters. In these algorithms, an on-chip Bloom filter identifies the membership of a node in an off-chip trie, and the number of trie accesses is reduced, because the Bloom filter can filter out accesses to non-existing nodes in the trie. In this paper, we propose a new method of utilizing a Bloom filter for the IP address lookup problem. In the previous Bloom filter-based approach, false positiveness has to be identified by accessing the off-chip trie for every positive result, since false positives can produce wrong results. In our proposed approach, the false positiveness of a Bloom filter is not necessarily identified by making false positives not mislead the search. Hence the number of off-chip trie accesses are significantly reduced. Simulation results show that the best matching prefix can be found with a single off-chip access in average and in the worst-case with the reasonable size of a Bloom filter in our proposed method.</P>

On the Deletable Bloom Filter

Hyesook Lim,Jungwon Lee,Changhoon Yim 대한전자공학회 2018 IEIE Transactions on Smart Processing & Computing Vol.7 No.6

The deletable Bloom filter (DBF) enables false negative–free deletions that are not possible in a standard Bloom filter or in a counting Bloom filter. The DBF is expected to be applied to many Bloom filter applications that require delete operations. Hence, the characteristics and the performance of the DBF should be studied further, as well as the error in the DBF. The first contribution of this paper is to provide the correct probability for the element being deletable in the DBF. The second contribution is to discuss the tradeoff between two important performance metrics (false positive probability and deletability probability), and to propose a cost function combining them. The third contribution is to provide a mathematical analysis of the false positive probability related to deletion rates. We also provide a comparison of the false positive probability between the analytical results and the simulation results as the deletion rate increases.