해시 기반 자료구조는 많은 응용 분야에서 널리 사용되어 왔다. 해싱의 본질적인 문제는 충돌(collision)인데, 이는 둘 이상의 원소가 동일한 값으로 해시되는 경우를 말한다. 해시 테이블이 과도하게 적재(loaded)되어 있으면 더 많은 충돌이 발생한다. 충돌로 인해 해시 테이블에 저장할 수 없었던 원소들은 탐색 실패를 유발한다. 충돌의 수를 줄이기 위해 많은 변형 구조들이 연구되어 왔으나, 어떤 구조도 충돌 문제를 완전히 해결하지는 못한다. 본 논문에서는 기능성 블룸 필터(functional Bloom filter; FBF)가 해시 테이블이 과도하게 적재되어 있을 때 해시 테이블보다 더 낮은 탐색 실패율을 제공한다고 주장한다. 즉, FBF는 제한된 크기의 메모리에 대량의 데이터를 저장할 때 탐색 실패율 측면에서 해시 테이블보다 더 효과적이므로, 해시 테이블을 FBF로 대체할 수 있다. 해시 테이블은 각 입력 키와 더불어 그 반환값(return value)을 저장해야 하는 반면, 기능성 블룸 필터는 입력 키 없이 반환값을 저장하는데, 이는 각 입력 키에 따라 서로 다른 인덱스 조합을 사용하여 입력 키를 식별할 수 있기 때문이다. 탐색 실패율에 관하여, 본 연구는 FBF를 다중 해시 테이블(multi-hash table), 큐쿠 해시 테이블(cuckoo hash table), d-좌측 해시 테이블(d-left hash table)과 같은 해시 기반 자료구조와 이론적으로 비교한다. 또한, 본 이론적 결과의 타당성을 입증하기 위해 시뮬레이션 결과도 제시한다. 시뮬레이션 결과는 적재 계수(load factor)가 0.6보다 클 때 해시 테이블의 탐색 실패율이 기능성 블룸 필터의 탐색 실패율보다 더 크다는 것을 보여준다.

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