Filters are data structures that probabilistically represents the presence of items within a given set. Filters, using less space compared to storing all elements, thus resides in memory and reduces unnecessary I/O operations to the secondary storage. Well-known filters such as Bloom filters, Quotient filters, and Vector Quotient filters have the drawback of experiencing memory overhead when dealing with datasets skewed distributions. This paper analyzes the shortcomings of Vector Quotient filters with skewed datasets. Then we introduce Counting Vector Quotient Filter, which solves this problem by applying a counting algorithm and filter size adjustment algorithm to the Vector Quotient Filter. This paper evaluate the performance of Counting Vector Quotient Filter in terms of operations per second on insertion, lookup, and deletion operations for datasets with skewed datasets.
필터는 주어진 집합 내에 원소의 존재 유무를 확률적으로 나타내는 자료구조이다. 필터는 모든 원소를 저장하는 것에 비해 적은 공간을 사용하기에 메모리 내에 상주하며 불필요한 입출력을 줄인다. 제안된 대표적인 필터들인 블룸 필터, 몫 필터, 벡터 몫 필터 등은 불균형 분포의 데이터셋에 대해서는 메모리 오버헤드가 발생한다는 문제점을 가지고 있다. 본 논문은 불균형 분포의 데이터셋에서 벡터 몫 필터의 문제점을 분석하고 카운팅 기법과 필터 크기 조절 알고리즘을 도입함으로써 이를 해결한다. 불균형 분포의 데이터셋에 대해서 카운팅 필터들간의 초당 연산량을 비교하여 삽입, 검색, 삭제 연산에서 모두 높은 성능을 보임을 확인한다.
