역방향(복원 가능한) 블룸 필터(invertible Bloom filter, IBF)는 다양한 네트워크 응용에서 유용한 자료구조이다. 이는 서로 다른 두 집합에 의해 각각 프로그래밍된 두 개의 IBF의 차이(difference IBF, d-IBF)가 각 집합에 고유한 서로 다른 원소들을 효과적으로 식별하기 때문이다. d-IBF는 공통 원소를 제거하며, 각 셀에 단일 원소를 저장하는 ‘순수 셀(pure cell)’을 활용하는 디코딩 과정으로 고유 원소들을 나열한다. 그러나 IBF의 디코딩을 위해 사용되는 순수 셀의 정의는 d-IBF를 디코딩하기에는 불충분하다. d-IBF의 복합 셀(composite cells) 또한 IBF에 대해 정의된 순수 셀 조건을 만족할 수 있으며, 복합 셀을 디코딩하는 것은 d-IBF 성능에 불리하게 작용한다. 본 연구는 d-IBF에서 디코딩 오류가 발생할 확률을 수학적으로 분석하고, 이러한 오류를 해결하기 위한 새로운 디코딩 방법을 제안한다. 실험 결과는 제안한 디코딩 방법이 디코딩 오류를 성공적으로 검출하고 해결함을 확인하였다. 이를 통해 집합의 크기에 무관하게, IBF의 셀 수가 m = (여기서 m은 IBF의 셀 수이고 d는 두 집합의 차이의 크기임)처럼 작더라도, 어떤 잘못된 원소도 생성하지 않으면서 두 집합 간의 차이를 정확하게 식별할 수 있다.
*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.