블룸 필터(Bloom filter)는 입력이 주어진 집합에 속하는지를 식별하는 단순한 자료구조이다. 다양한 유형의 블룸 필터가 최근 수년간 널리 사용되어 왔다. 표준 블룸 필터는 셀(cell)에 0 또는 1 값을 저장함으로써 특정 집합에 대한 멤버십 식별만을 제공하는 반면, 본 연구에서는 하나의 블룸 필터에 셀마다 서로 다른 값을 저장하여 여러 집합의 멤버십 정보를 제공하고자 한다. 즉, 두 개의 서로 다른 집합이 주어질 때 제안하는 블룸 필터 구조는 하나의 셀에 2비트(2 bits)를 할당하고, 각 집합을 나타내는 두 개의 서로 다른 값은 집합을 프로그래밍하기 위해 사전에 지정한다. 따라서 제안하는 블룸 필터 구조는 단일 블룸 필터를 질의함으로써 각 집합의 멤버십과 두 집합의 교집합을 정확하게 판정할 수 있다. 또한 멤버십 식별의 정확도를 향상시키기 위해 둘러싸인(circled) 블룸 필터 구조를 제안한다. 실험 결과는 제안하는 블룸 필터 구조가 두 개의 분리된 블룸 필터 구조에 비해 질의 연산의 절반만 사용하면서도 더 나은 정확도를 제공함을 보여준다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.