오픈마루에서 Inverted Index Compression에 대해서 발표했습니다.

오늘 오픈마루에서 inverted index compression 발표를 했다.

ppt는 아래 논문과 서적을 참고로 만들었다.

무엇보다 이 발표자료를 만들면서 그동안 몇가지 알고리즘을 알고 있었던것과 더불어 새로운 알고리즘까지 내 자신이 스스로 총정리 할 수 있었던 아주 좋은 기회가 되었던거 같다.
그리고 앞으로 어떤 Doc Id특성을 가지고 있을경우는 어떤걸 쓴다든지 하는 그런 나만의 아니 그 누구나 수긍할 수 있는 설득력 있는 기반을 만든거 같다.

참고 논문과 서적은 아래와 같다. 작년에 새로 나온 가장 최근의 논문도 참고했다. ^^

Improved word-aligned binary compression for text indexing
Anh, V.N.; Moffat, A.;
Knowledge and Data Engineering, IEEE Transactions on
Volume 18,  Issue 6,  June 2006 Page(s):857 – 861

Inverted Index Compression Using Word-Aligned Binary Codes / Anh, Vo Ngoc ; Moffat, Alistair ( Information retrieval, v.8 no.1, 2005, pp.151-166)

Information Retrieval : Algorithm and Heuristics (Springer. 2005)

Introduction to Information Retrieval, (Cambridge University Press. 2007.)

첫번째 논문에서 나온 word-aligned 에서 carry 방법을 개선한 slide 방법은 확실히 압축률은 좋아졌긴 하나 성능에 의구심이 간다. 물론 논문에서 많은 실험을 거쳤겠지만 약간 의심이 가는건 어쩔수 없다. 이부분은 직접 구현해보고 실험 해보면서 사용여부를 알아보면 되겠지만 아직까지는 Relative-10 방법의 Word-aligned compression 방법이 가장 무난한듯 하다. (비트단위가 아닌 워드나 바이트 단위의 접근 방식이 OS에 친근하니 말이다.)

두개의 논문과 함께 2권의 책에 나온 index compression 부분을 통독하다보니 이제 어느정도 정리가 되는듯 하다.

내 나름대로 정리한 결론을 내리자면 …

1. 이론적인 bit 기반의 코딩 방식은 일단 OUT (압축률은 무지 좋으나 현실적이지 않다.)
2. Variable Byte encoding 방식은 가장 일반적인 무난한 방식의 압축이다.(여기 저기 널리 쓰인다. 심지어 Lucene에서도…)
3. 일단 Doc ID가 정렬이 어느정도 되어 있어서 한 Posting file의 Doc Id Gap의 분포가 일정하다면 Word-aligned 방법이 가장 좋을 것이다. 물론 그렇지 않더라도 Variable Byte encoding 방식에 그리 뒤지지 않는다.

이상 자세한것은 발표자료나 논문 자료를 보는걸 추천하고…

오늘 질문 해주셨고 함께 고민해 준 오픈마루 검색팀 분들께 감사를 전하고 싶다.

발표문서 첨부합니다…^^

XMuLMFDpXr.pdf