Filter, also known as Approximate Membership Query, is a data structure that approximately represents whether an element belongs to a set. Compared to dictionary, which stores all data, filters use much less space and therefore is able to fit in memory. Using filter can decrease the amount of unnecessary queries and this benefits performance in various fields including distributed storage, network, machine learning and computational biology. Some famous filters are bloom filter, cuckoo filter, morton filter and quotient filter. Vector quotient filter has superior insertion throughput above all others due to its architectural optimizations. This paper focus on the issue that rise when skewed data is inserted to vector quotient filter, a variant of quotient filter. The issue can solved by implementing counter. Implementation of counter inside vector quotient filter is described and the benefits and overhead of implementing counter are assessed.
필터는 주어진 집합 내에 특정 원소가 존재하는지 확률적으로 나타내는 자료구조이다. 필터는 모든 원소를 저장하는 것에 비해 적은 공간을 사용하기에 메모리 내에 상주할 수 있다. 필터를 사용하면 원소 검색 시 불필요한 입출력을 줄일 수 있어 성능상의 이점을 얻을 수 있다. 필터의 종류로는 블룸 필터, 쿠쿠 필터, 모턴 필터, 몫 필터 등이 있다. 본 논문은 몫 필터에서 파생된 벡터 몫 필터 자료구조에 대해 고찰하고 원소 삽입 시 발생할 수 있는 문제를 카운팅 기법을 적용해 해결한다. 이후 카운팅 기법으로 절약할 수 있는 공간에 대해 분석하고 오버헤드를 측정한다.
