먼저 인덱싱을 하기전에 문서를 reordering을 한다면 문서의 압축 효율이 좋아진다는 논문이 있다.(Blsndford and Blelloch, 2002, Silvestri et al., 2004)

reordering이 왜 필요하냐면 문서의 포스팅 파일을 만들기 위해 텀에 대한 문서 번호를 색인에 쓸때 문서의 d-gap을 줄이기 위해서 사용한다.

예를들어 term t가 나오는 문서가 D1, D100, D600 에 해당한다면 이들의 doc no를 색인에 쓸때 1, 99, 500의 숫자가 쓰여진다. 이런 숫자의 범위 자체가 커지기 때문에 전에 포스팅한  색인 압축 알고리즘을 쓰더라도 그렇게 좋은 압축 효율은 기대하기 어렵다.

그래서 제시한것이 문서를 비슷한 문서끼리 클러스터링을 한 다음에 그 문서를 쓰는것이다.

이  아이디어의 기본 컨셉은 비슷한 문서는 비슷한 텀을 가지고 있을 가능성이 많고 이 것들을 기준으로 정렬을 하면 색인의 용량을 줄일 수 있다는것이다.

만일 위의 문서 gap을 1~2 정도로 줄일수만 있다면 색인의 용량을 줄어들것임에 틀림이 없다.

물론 문서 d개를 ordering하는 방법은 2^d 개이기 때문에 그 ordering 정도에 대한 문제점이 제기될 수 있다.

여기에는 Top-Down 방법과 Bottom-up 방법이 있고, 둘다 익히 잘 알고 있는 cosine similality를 기반으로 하고 있다.

Top-Down 방법은

1. center selection
2. redistribution
3. recursion  1~2
4. merging

위의 순서로 이루어 지며,
전체의 컬렉션에서 2개의 그룹을 선정하는것이 1번이다.(2개의 포스팅 리스트를 출력하기 위함이 아닐까한다.)
그리고 나머지 문서중에서 두 그룹들에 가장 유사도가 높은 문서를 포함시켜 가는것이 2번의 작업이다.
다시 1번과 2번의 과정을 반복함으로써 2개의 그룹이 변함없이 굳혀질때 iteration이 끝나게 된다.
그리고 merging 작업은 그 해당 클러스터링 그룹의 iteration때마다 추가된 문서의 순서대로 ordering을 하게 되는 작업을 하게된다.

그리고 Bottom-up 방식은 몇개의 문서를 기반으로 클러스터링을 해가는 k-means 방법을 쓴다.
그리고 k-means 방법의 종료조건과 과정을 간소화한 k-scan 방법을 쓰기도 한다.(k-means 방법론은 복잡도가 매우 높은 단점이 있다.)

Top-Down방법은 전체 컬렉션 기반이고, Bottom-up 방법은 개별 문서 기반의 클러스터링이 되겠다.

문서를 클러스터링 하는 방법은 여러 방법이 있으니 문서를 reordering 방법도 찾아보면 많으리라 본다. 개인적인 생각으로는 색인시간을 reordering하는데 많이 쓰기 보다는 적절한 타협점을 찾아서 적절하게(?) 적용하는게 좋을듯 싶다.

인덱싱을 하기전에 어느정도 문서에 대한 ordering을 한다면… by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.