bloom filter

 석사 졸업 논문으로 위키피디아를 이용하여 검색 정확도를 향상시키는

 주제에 관하여 논문을 작성하였다.

 논문 실험에서 TREC WT10G 데이터(약 4G)를 인덱싱하는데 대략 3시간

 쯤 걸린듯하다. 내가 제안하는 알고리즘은 위키피디아의 Entry를 이용하여

 랭킹 알고리즘을 수정하였기 때문에 각 다큐먼트를 인덱싱할때에 다큐먼트의

 모든 TERM에 대해서 위키피디아의 엔트리로 존재하는지를 검색해야하고

 이때문에 초기에는 위키피디아 entry를 DB에 모두 저장하여 실험을 하여보았다.

 DB를 이용했을때 대략 WT10G 데이터 전체를 인덱싱하는데에

 10시간쯤 걸린듯 하다.

 이에 성능을 높이기 위해 bloom filter를 고려하게 되었다.

 Bloom filter는 특정 data가 존재하는지의 여부만을 알고자 할때 매우 효율적이고

 논문의 랭킹 알고리즘에서는 해당하는 TERM이 위키피디아 entry로 존재하는지

 의 여부만을 알면 되기 떄문에 굳이 DB를 사용할 필요가 없고 Bloom filter도

 이러한 목적으로는 충분하다.

 위키피디아 entry 전체( 약 700만개의 word)를  bloom filter에 저장하게 되면

 설정에 따라 다르겠지만 대략 500M정도의 메모리를 사용하게 된다.

 대신에 메모리에 직접 올라가기 떄문에 DB를 이용하는 것 보다 훨씬 빨라져서

 인덱싱하는데 대략 3시간 30분 정도 걸린듯 하다. 즉 추가적인 entry 검색으로

 30분 정도가 걸린것으로 볼수 있다. DB검색에 7시간 정도 걸린것에 비해보면

 매우 효율적이라 볼수 있다.


 내가 사용한 bloom filter의 소스를 링크한다.

 https://sites.google.com/site/wittgena/upload_file/BloomFilter.java?attredirects=0&d=1