카운팅 블룸필터는 표준 블룸필터에서 제공하지 못하는 삭제 기능을 제공하여, 동적 집합에 대한 멤버쉽 쿼리를 허용하므로, 다양한 네트워크 알고리즘과 어플리케이션에 널리 사용된다. 그러나 카운팅 기능으로 인해 표준 블룸필터에는 없었던 오버플로우가 발생할 수 있고 이에 따라 거짓 음성이 발생할 수 있다. 4-비트 카운팅 블룸필터가 일반적으로 많이 사용되는데, 이는 모든 카운터에 4 비트를 할당하므로 메모리를 낭비한다는 단점이 있다. 거짓 음성의 가능성을 제거하고 메모리 사용량을 줄이기 위해서, 본 논문은 카운팅 블룸필터의 변형인 터너리 블룸필터(Ternary Bloom filter)를 제안한다. TBF는 하나의 카운터에 2개 이상의 원소가 대응될 경우, 더 이상의 삽입이나 삭제가 불가능하게 정한 구조이다. 실험을 통해 4-비트 카운팅 블룸필터와 같은 크기의 메모리 사용 시 TBF는 거짓 음성을 발생시키지 않을 뿐 아니라 거짓 양성률에 있어서도 상당한 우위를 보임을 확인하였다.
카운팅 블룸필터는 표준 블룸필터에서 제공하지 못하는 삭제 기능을 제공하여, 동적 집합에 대한 멤버쉽 쿼리를 허용하므로, 다양한 네트워크 알고리즘과 어플리케이션에 널리 사용된다. 그러나 카운팅 기능으로 인해 표준 블룸필터에는 없었던 오버플로우가 발생할 수 있고 이에 따라 거짓 음성이 발생할 수 있다. 4-비트 카운팅 블룸필터가 일반적으로 많이 사용되는데, 이는 모든 카운터에 4 비트를 할당하므로 메모리를 낭비한다는 단점이 있다. 거짓 음성의 가능성을 제거하고 메모리 사용량을 줄이기 위해서, 본 논문은 카운팅 블룸필터의 변형인 터너리 블룸필터(Ternary Bloom filter)를 제안한다. TBF는 하나의 카운터에 2개 이상의 원소가 대응될 경우, 더 이상의 삽입이나 삭제가 불가능하게 정한 구조이다. 실험을 통해 4-비트 카운팅 블룸필터와 같은 크기의 메모리 사용 시 TBF는 거짓 음성을 발생시키지 않을 뿐 아니라 거짓 양성률에 있어서도 상당한 우위를 보임을 확인하였다.
Counting Bloom filters (CBFs) have been popularly used in many network algorithms and applications for the membership queries of dynamic sets, since CBFs can provide delete operations, which are not provided in a standard 1-bit vector Bloom filter. However, because of the counting functions, a CBF c...
Counting Bloom filters (CBFs) have been popularly used in many network algorithms and applications for the membership queries of dynamic sets, since CBFs can provide delete operations, which are not provided in a standard 1-bit vector Bloom filter. However, because of the counting functions, a CBF can have overflows and accordingly false negatives. CBFs composed of 4-bit counters are generally used, but the 4-bit CBF wastes memory spaces by allocating 4 bits for every counter. In this paper, we propose a simple alternative of a 4-bit CBF named ternary Bloom filter (TBF). In the proposed TBF structure, if two or more elements are mapped to a counter in programming, the counters are not used for insertion or deletion operations any more. When the TBF consumes the same amount of memory space as a 4-bit CBF, it is shown through simulation that the TBF provides a better false positive rate than the CBF as well as the TBF does not generate false negatives.
Counting Bloom filters (CBFs) have been popularly used in many network algorithms and applications for the membership queries of dynamic sets, since CBFs can provide delete operations, which are not provided in a standard 1-bit vector Bloom filter. However, because of the counting functions, a CBF can have overflows and accordingly false negatives. CBFs composed of 4-bit counters are generally used, but the 4-bit CBF wastes memory spaces by allocating 4 bits for every counter. In this paper, we propose a simple alternative of a 4-bit CBF named ternary Bloom filter (TBF). In the proposed TBF structure, if two or more elements are mapped to a counter in programming, the counters are not used for insertion or deletion operations any more. When the TBF consumes the same amount of memory space as a 4-bit CBF, it is shown through simulation that the TBF provides a better false positive rate than the CBF as well as the TBF does not generate false negatives.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 기존의 카운팅 블룸필터의 불필요한 메모리 낭비를 줄여 같은 메모리 사용량에서 거짓 양성률을 줄임과 동시에, 거짓 음성의 가능성을 제거하는 새로운 블룸필터 구조를 제안하였다. 제안하는 TBF 구조는 하나의 셀에 두개 이상의 원소가 대응되는 경우 X로 선언하여, 원소의 삭제 시 사용되지 않음을 표현하므로 거짓 음성의 가능성을 제거하였다.
본 논문에서는 이러한 문제들을 해결한 블룸필터 구조를 제안한다. 본 논문에서 제안하는 블룸필터는 블룸필터 동작에 치명적인 거짓 음성의 가능성을 없애고, 카운팅 블룸필터와 같은 메모리 사용량에 대하여 보다 낮은 거짓 양성률을 제공하는 구조이다.
가설 설정
DBF 구조에서 r-비트를 블룸필터의 충돌표시를 위하여 할당한다고 가정하면, 실제 프로그래밍 되는 블룸필터 사이즈(m’)는 m-r 비트이고, 본 실험에서는 r-비트가 전체 블룸필터 사이즈(m)의 1/5을 차지하는 경우를DBF_1으로 표현하였고, 1/20을 차지하는 경우를 DBF_2로 표현하여 실험하였다.
다음은 원소의 삭제기능에 대하여 실험하였다. 삭제는 프로그래밍에 사용된 집합에 속한 원소만을 삭제함을 가정한다. 그러므로 삭제할 원소가 0으로 프로그래밍 된 셀과 대응되는 경우는 존재하지 않는다.
블룸필터의 크기는 한 셀 당 가장 많은 비트를 차지하는 4-비트 CBF를 기준으로 메모리 사용량이 같도록 설정하였다. 원소의 개수가 N인 집합에 대하여, 4-비트 CBF의 셀의 개수를 N, 2N, 4N으로 정할 때, TBF의 경우 값의 종류가 3개여서 하나의 셀 당 1.5 비트를 갖는다고 가정할 수 있으므로 TBF 셀의 개수는 8N/3, 16N/3, 32N/3이 되며, QBF 셀의 개수는 2N, 4N, 8N이 된다.
제안 방법
먼저 제안하는 블룸필터 구조에서 ‘Not determinable’이 나오는 경우에 대하여 실험하였다.
본 논문에서는 이러한 문제들을 해결한 블룸필터 구조를 제안한다. 본 논문에서 제안하는 블룸필터는 블룸필터 동작에 치명적인 거짓 음성의 가능성을 없애고, 카운팅 블룸필터와 같은 메모리 사용량에 대하여 보다 낮은 거짓 양성률을 제공하는 구조이다. 본 논문의 구성은 다음과 같다.
그러므로 삭제할 원소가 0으로 프로그래밍 된 셀과 대응되는 경우는 존재하지 않는다. 본 논문에서는 2장에서 언급한 여러 연구들 중에서 제안하는 구조와 같은 성능평가 기준을 갖는 Deletable BF[16]와 성능 비교를 진행하였다. Deletable BF(DBF) 셀의 개수는 4N, 8N, 16N으로 설정하되, 블룸필터의 일부 비트를 충돌이 일어난 구역 표시를 위하여 사용한다.
제안하는 구조는 CBF에서 0으로 프로그래밍 된 카운터를 위해서도 c-비트를 할당해야 하는 낭비를 해결하기 위하여 출발하였다. 본 논문에서는 CBF와 같은 양의 메모리를 사용하되 하나의 카운터에 c보다 적은비트를 할당하고, 그 대신 블룸필터에 포함되는 카운터의 개수를 키울 것을 제안한다. 카운터의 개수가 많아지면 이에 따라 해시 인덱스의 최적 개수도 늘어나게 되므로, 입력의 멤버십 여부를 판단하거나 프로그래밍된 원소를 삭제하고자 할 때 오버플로우가 일어난 카운터는 사용하지 않는 방식이다.
상용 메모리 기술에서는 값이 종류가 0, 1, X의 3종류를 갖는 경우에도 2비트의 카운터를 사용하여야 하고 이 경우 0, 1, 2, X의 4종류의 값을 표현할 수 있으므로, 본 논문에서 제안하는 TBF의 변형인 Quarternary Bloom filter(QBF)를 정의하였다. TBF에서의 하나의 셀은 1개의 원소만 대응될 수 있는데 반하여 QBF에서의 하나의 셀은 최대 2개의 원소가 대응될 수 있다.
제안하는 구조는 CBF에서 0으로 프로그래밍 된 카운터를 위해서도 c-비트를 할당해야 하는 낭비를 해결하기 위하여 출발하였다. 본 논문에서는 CBF와 같은 양의 메모리를 사용하되 하나의 카운터에 c보다 적은비트를 할당하고, 그 대신 블룸필터에 포함되는 카운터의 개수를 키울 것을 제안한다.
‘Not determinable’이란 쿼링된 원소의 멤버십 여부를 판단할 수 없다는 의미이다. 제안하는 블룸필터에 이미 프로그래밍 된 어떤 원소를 삭제하고자 할 때에는 그 값이 X가 아닌 셀 중에서 블룸필터 셀의 값이 1인 셀들을 0으로 변경한다. 삭제 시에 대응된 블룸필터의 셀 값이 모두 X인 경우는 ‘Not deletable’로 정의한다.
대상 데이터
실험은 Web Information Company인 ALEXA[20]에서 제공하는 URL중 임의로 선정하여 수행하였다. 집합 S를 프로그래밍 한 후 S의 여집합(SC)에 대해 쿼링을 수행하였는데, 이러한 방식으로 쿼링을 수행하면 집합에 포함된 원소는 하나도 존재하지 않으므로 모두 음성이 나와야 참인 결과이다.
데이터처리
그림 5에서는 각 알고리즘의 거짓 양성률을 비교하였다. 제안하는 블룸필터와 동일한 메모리 소요량을 보이는 4-비트 CBF와 DBF의 성능을 함께 비교하였다. 거짓 양성률은 각 집합 별로 거짓 양성의 개수를 쿼링된 입력 개수로 나눈 값으로 나타내었다.
성능/효과
첫 번째, 오버플로우 및 해시 충돌로 인한 잘못된 카운터 감소 때문에 거짓 음성을 발생시킬 수 있다. 두 번째, 최적화된 블룸필터의 경우 0으로 프로그래밍 된 카운터의 개수가 전체 블룸필터의 반 정도를 차지하는데, 0으로 프로그래밍 된 카운터들을 위해서도 c 비트를 할당하므로 메모리 낭비가 크다. 또한 c 비트가 모두 사용되는 확률도 매우 낮기 때문에 그 값이 0이 아닌 카운터의 경우에도 사용되지 않는 비트가 존재하여 메모리가 낭비된다.
제안하는 구조에서는 쿼링 시 ‘Not determinable’이 발생하는 경우와 삭제 시 ‘Not deletable’이 발생하는 경우를 새롭게 정의하였는데, 집합에 속한 N개의 원소에 대하여 TBF의 셀의 개수가 32N/3일 때, 그리고 QBF의 셀의 개수가 8N일 때 모두 0으로 수렴함을 보았다. 또한 4-비트 카운팅 블룸필터와 같은 메모리 사용량을 가질 때의 거짓 양성률을 비교하였을 때, 제안하는 구조에서의 거짓 양성률이 카운팅 블룸필터보다 월등히 우수함을 보았다.
블룸필터의 사이즈가 증가할수록 해시 인덱스 k가 커지기 때문에 k개의 셀 값이 모두 X인 비율이 줄어들어 ‘Not deletable’의 발생률이 감소됨을 볼 수 있으며, TBF의 경우 셀의 개수가 32N/3이고, QBF의 경우 셀의 개수가 8N일 때, ‘Not deletable’의 발생률이 0으로 수렴됨을 볼 수 있다.
거짓 양성률은 각 집합 별로 거짓 양성의 개수를 쿼링된 입력 개수로 나눈 값으로 나타내었다. 비교를 진행한 4개의 블룸필터 모두, 사이즈가 증가할수록 거짓 양성률이 감소됨을 볼 수 있다. 4-비트 CBF의 경우 동일한 크기의 메모리를 사용하더라도 다른 블룸필터보다 거짓 양성의 비율은 현저히 높음을 알 수 있는데, 이는 앞서 설명한 바와 같이 모든 카운터에 4비트가 할당되었기 때문에 상대적으로 셀의 개수가 적은 블룸 필터이기 때문이다.
본 논문에서는 기존의 카운팅 블룸필터의 불필요한 메모리 낭비를 줄여 같은 메모리 사용량에서 거짓 양성률을 줄임과 동시에, 거짓 음성의 가능성을 제거하는 새로운 블룸필터 구조를 제안하였다. 제안하는 TBF 구조는 하나의 셀에 두개 이상의 원소가 대응되는 경우 X로 선언하여, 원소의 삭제 시 사용되지 않음을 표현하므로 거짓 음성의 가능성을 제거하였다. 제안하는 구조에서는 쿼링 시 ‘Not determinable’이 발생하는 경우와 삭제 시 ‘Not deletable’이 발생하는 경우를 새롭게 정의하였는데, 집합에 속한 N개의 원소에 대하여 TBF의 셀의 개수가 32N/3일 때, 그리고 QBF의 셀의 개수가 8N일 때 모두 0으로 수렴함을 보았다.
제안하는 구조에서는 쿼링 시 ‘Not determinable’이 발생하는 경우와 삭제 시 ‘Not deletable’이 발생하는 경우를 새롭게 정의하였는데, 집합에 속한 N개의 원소에 대하여 TBF의 셀의 개수가 32N/3일 때, 그리고 QBF의 셀의 개수가 8N일 때 모두 0으로 수렴함을 보았다.
제안하는 구조인 QBF와 TBF를 비교해 보면 QBF가 TBF보다 값 X의 발생이 적기 때문에 ‘Not deletable’로 판단되는 비율 역시 작게 나옴을 볼 수 있다.
카운터의 개수가 많아지면 이에 따라 해시 인덱스의 최적 개수도 늘어나게 되므로, 입력의 멤버십 여부를 판단하거나 프로그래밍된 원소를 삭제하고자 할 때 오버플로우가 일어난 카운터는 사용하지 않는 방식이다. 제안하는 블룸필터 구조는 이러한 방식으로 CBF의 치명적인 단점인 거짓 음성의 가능성을 제거하였고, CBF와 같은 크기의 메모리 사용하였을 때 거짓 양성의 비율을 줄여 더욱 향상된 성능을 보인다.
그러나, 카운팅 블룸필터에는 두 가지 문제점이 있다. 첫 번째, 오버플로우 및 해시 충돌로 인한 잘못된 카운터 감소 때문에 거짓 음성을 발생시킬 수 있다. 두 번째, 최적화된 블룸필터의 경우 0으로 프로그래밍 된 카운터의 개수가 전체 블룸필터의 반 정도를 차지하는데, 0으로 프로그래밍 된 카운터들을 위해서도 c 비트를 할당하므로 메모리 낭비가 크다.
질의응답
핵심어
질문
논문에서 추출한 답변
블룸필터란?
블룸필터[1]는 비트 벡터 형식의 공간효율적인 자료구조로써, 주어진 집합에 대한 멤버쉽 쿼리(membership query)를 제공해준다. 블룸필터를 사용하면 공간을 적게 사용하면서도 빠른 검색이 가능하다는 장점이 있어, 회계(accounting), 모니터링(monitoring), 로드 밸런싱(load balancing), 정책 적용(policy enforcement), 라우팅(routing), 필터링(filtering), 보안(security), 차등화 서비스(differentiated service), 캐시 디렉터리(cache directory)와 같은 다양한 응용 프로그램을 위해 널리 사용되고 있다[2∼7].
표준 블룸필터의 취약점은?
표준 블룸필터의 한 가지 취약점은 이미 프로그래밍 된 원소를 삭제하는 것이 불가능하다는 것이다. 집합의 원소가 동적으로 변화하는 경우 삭제기능이 필요한데, 삭제 기능을 제공하는 대표적인 변형은 카운팅 블룸필터[10]이다.
카운팅 블룸필터의 두 가지 문제점은 무엇인가?
그러나, 카운팅 블룸필터에는 두 가지 문제점이 있다. 첫 번째, 오버플로우 및 해시 충돌로 인한 잘못된 카운터 감소 때문에 거짓 음성을 발생시킬 수 있다. 두 번째, 최적화된 블룸필터의 경우 0으로 프로그래밍 된 카운터의 개수가 전체 블룸필터의 반 정도를 차지하는데, 0으로 프로그래밍 된 카운터들을 위해서도 c 비트를 할당하므로 메모리 낭비가 크다. 또한 c 비트가 모두 사용되는 확률도 매우 낮기 때문에 그 값이 0이 아닌 카운터의 경우에도 사용되지 않는 비트가 존재하여 메모리가 낭비된다.
참고문헌 (20)
B. Bloom, "Space/time Tradeoffs in Hash Coding with Allowable Errors," Communications of the ACM, Vol.13, No.7, pp. 422-426, Jul. 1970.
F. Bonomi, M. Mitzenmacher, R. Panigrah, S. Singh, and G. Varghese, "Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines," in Proc. ACM SIGCOMM, pp. 315-326, Pisa, Italy, Sep. 2006.
H. Song, F. Hao, M. Kodialam, and T. V. Lakshman, "IPv6 Lookups Using Distributed and Load Balanced Bloom Filters for 100 Gbps Core Router Line Cards," in Proc. IEEE INFOCOM, pp. 2518-2526, Rio, Brazil, Apr. 2009.
O. Rottenstreich and I. Keslassy, "The Bloom Paradox: When Not to Use a Bloom Filter," IEEE/ACM Trans. on Networking, Vol. 23, No. 3, pp. 703-716, Jun. 2015.
S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, "Longest Prefix Matching Using Bloom Filters," IEEE/ACM Trans. on Networking, Vol. 14, No. 2, pp. 397-409, Apr. 2006.
H. Lim, K. Lim, N. Lee, and K. Park, "On Adding Bloom Filters to Longest Prefix Matching Algorithms," IEEE Trans. on Computers, Vol. 63, No. 2, pp. 411-423, Feb. 2014.
J. Mun, and H. Lim, "New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based Algorithms," IEEE Trans. on Computers, Vol. 65, No.5, pp.1558-1565, May. 2016.
S. Tarkoma, C. E. Rothenberg, and E. Lagerspetz, "Theory and Practice of Bloom Filters for Distributed Systems," IEEE Communications Surveys and Tutorials, Vol. 14, No. 1, pp. 131-155, First Quarter, 2012.
L. Fan, P. Cao, J. Almeida, and A. Broder, "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol," IEEE/ACM Trans. on Networking, Vol. 8, No.3, pp. 281-293, Jun. 2000.
D. Ficara, A. Di Pietro, S. Giordano, G. Procissi, and F. Vitucci, "Enhancing Counting Bloom Filters through Huffman-Ccoded Multilayer Structures," IEEE/ACM Trans. on Networking, Vol. 18, No. 6, pp. 1977-1987, Dec. 2010.
Y. Lu, A. Montanari, B. Prabhakar, S. Dharmapurikar, and A. Kabbani, "Counter Braids: A Novel Counter Architecture for Per-Flow Measurement," in Proc. ACM SIGMETRICS 2008, pp. 121-132, Annapolis, USA, 2008.
F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, "An Improved Construction for Counting Bloom Filters," in Proc. ESA, pp. 684-695, Zurich, Switzerland, Sep. 2006.
O. Rottenstreich, Y. Kanizo, and I. Keslassy, "The Variable-Increment Counting Bloom Filter," IEEE/ACM Trans. on Networking, Vol. 22, No. 4, pp. 1092-1105, Aug. 2014.
K. Huang, J. Zhang, D. Zhang, G. Xie, K. Salamatian, A. Liu, and W. Li, "A multi-partitioning approach to building fast and accurate counting bloom filters," IEEE IPDPS, pp. 1159-1170, Boston, USA, May. 2013.
C. Rothenberg, C. Macapuna, F. Verdi, and M. Magalhaes, "The Deletable Bloom Filter: A New Member of the Bloom Family," IEEE Communications Letters, Vol. 14, No. 6, pp. 557-559, Jun. 2010.
D. Ficara, A. Di Pietro, S. Giordano, G. Procissi, and F. Vitucci, "Enhancing counting Bloom filters through Huffman-coded multilayer structures," IEEE/ACM Trans. on Networking, Vol. 18, No. 6, pp. 1977-1987, Dec. 2010.
L. Li, B. Wang, and J. Lan, "A variable length counting Bloom filter," in Proc. 2nd Int. Conf. on ICCET, pp. 504-508, Kuala Lumpur, Malaysia, Apr. 2010.
N. Hua, H. Zhao, B. Lin, and J. Xu, "Rank-indexed hashing: A compact construction of Bloom filters and variants," in IEEE ICNP, pp. 73-82, Orlando, USA, Oct. 2008.
Alexa the Web Information Company, http://www.alexa.com/
※ AI-Helper는 부적절한 답변을 할 수 있습니다.