• 색인 구축(Index construction) or 색인(Indexing)
• 역색인을 구축하는 과정
• 색인기(Indexer)
• 색인을 수행하는 프로세스 또는 장치
• 정렬 기반 블록화 색인(Blocked sort-based indexing)
• 정렬 기반 색인보다 확장성을 갖춘 버전으로 정적 컬렉션을 위해 설계된 효율적인 단일 장비 알고리즘
• 동적 색인(Dynamic indexing)
• 컬렉션의 내용이 바뀌면 색인에 즉시 반영하는 방법

4.1 하드웨어 기반

• 캐싱(Cashing)
• 자주 접근하는 자료를 주기억장치에 저장하는 기법
• 탐색 시간(Seek time)
• 디스크 읽기 또는 쓰기를 수행할 때, 디스크 헤드가 특정 자료가 있는 위치로 이동하는 시간
• 버퍼(Buffer)
• 디스크로부터 하나의 바이트를 읽을 때 전체 블록을 읽는 데 드는 시간만큼 소요되는데 블록의 크기는 일반적으로 8, 16, 32, 64 kb이며 읽히고 써진 블록 영역이 저장되는 주 기억장치의 일부를 버퍼라고 함

4.2 정렬 기반 블록화 색인

• 비위치 색인(Nonpositional index)에서 소규모 컬렉션의 경우 모든 과정을 기억장치에서 수행할 수 있지만, 대형 컬렉션의 경우 보조 저장장치를 필요로 함
• 주기억장치의 크기가 컬렉션의 규모에 비해 충분하지 않을 때는 디스크를 사용하는 외부 정렬 알고리즘(External sorting algorithm)을 사용할 필요가 있으며, 이를 빠르게 수행하기 위해서는 정렬하는 동안 디스크 탐색 횟수를 최소화하는 것이 중요하며, 정렬 기반 블록화 색인 알고리즘(BSBI, Blocked sort-based indexing algorithm)이 사용됨
• BSBI의 특징
• 컬렉션을 동일한 크기로 나눔
• 기억장치 상에서 각 부분의 termID-docID 상을 정렬함
• 정렬의 중간 결과를 디스크에 저장함
• 중간 정렬 결과를 최종 색인으로 병합함

4.3 단일 단계 기억장치 내 색인

• 정렬 기반 블록화 색인은 뛰어난 크기 조정 속성을 가지고 있으나, 용어를 termID로 사상시키는 자료 구조가 사전에 구비되어야 함
• 따라서 대용량 컬렉션에서는 이 자료 구조를 기억장치 상에 구현하기에 적합하지 않음
• 단일 패스 메모리 색인(SPIMI, Single-pass in-memory indexing)
• termID 대신 용어를 그대로 사용하여 각 블록의 사전을 디스크에 기록하는 방법이기 때문에 디스크에 여유 공간이 있는 한 어떤 크기의 컬렉션도 색인할 수 있으며, 새로운 블록에 대해서는 새로운 사전으로 다시 시작함
• 전체 컬렉션에 대해 처리가 끝날 때까지 SPIMI-Invert 함수는 반복적으로 호출되며, 호출되는동안 토큰은 한 번에 하나씩 처리됨
• 만약 어떤 용어가 처음 출현하면 사전에 추가하고 새로운 포스팅 목록이 생성됨
• 용어의 포스팅 목록이 얼마나 큰지 알 수 없기 때문에 처음 시작할 때는 적은 공간을 할당하고, 전부 사용할 때마다 두 배의 공간을 할당하여, 기억장치는 낭비되지만 중간 자료구조에서 termID를 생략하여 기억장치를 절약할 수 있음
• SPIMI에서 동적으로 구성된 한 블록의 색인에 필요한 총 기억장치 요구량은 BSBI보다 항상 작음

4.4 분산 색인

• 강력한 분산 색인을 위해 필요한 요구사항 중 하나는 장애가 발생하더라도 작업을 쉽게 할당하고 재할당할 수 있는 덩어리로 분할하는 것임
• 마스터 노드(Master node)
• 개별 작업 노드에 과업의 할당 및 재할당 처리를 지시함
• MapReduce는 일반적으로 키-값 쌍(Key-value pair)의 처리를 위해 재계산함으로써 대형 계산 문제를 더 작은 부분으로 분할함
• 사상 단계(Map phase)
• 입력 자료의 조각들을 키-값 쌍으로 바꿈
• 파서(Parser)
• 사상 단계를 수행하는 기계
• 파서는 처리 결과를 세그먼트 파일(Segment file)이라고 하는 지역 중간 파일에 기록함
• 축약 단계(Reduce phase)
• 해당 키에 대한 모든 값들을 밀접하게 함께 저장하여 신속하게 읽고 처리할 수 있음
• 즉, 키들을 j개의 용어 파티션들에 넣고, 파서가 각 용어 파티션마다 키-값 쌍을 개별 세그먼트 파일에 기록하여 실행함
• 인버터(Inverter)
• 할당된 키에 대응하는 모든 값을 수집하여 하나의 목록으로 만드는 일을 수행함
• 각 용어 파티션(각 파서에 하나씩 r개의 세그먼트 파일에 해당)은 하나의 인버터에 의해 처리됨
• 자료를 축약하기 이전에 기록하는데 소요되는 시간을 단축하기 위해 각 파서는 세그먼트 파일을 지역 디스크(Local disk)에 기록함
• 마스터 서버는 각 용어 파티션을 다른 인버터에 할당하고, 오류가 있거나 느린 인버터의 경우 용어 파티션을 재할당함

4.5 동적 색인

• 만약 새로운 문서를 신속하게 포함해야 하는 경우, 한 가지 해결책은 두 가지 색인으로 처리하는 것임
• 보조 색인(Auxiliary index)
• 대형 주 색인과 새로운 문서들을 저장할 수 있는 색인으로 기억장치 내에 유지함
• 검색은 두 색인에 함께 적용하여 결과를 병합함
• 보조 색인이 너무 커지게 되면 주 색인에 병합함
• 무효 비트 벡터(Invalidation bit vector)
• 제거 대상을 저장함
• 하지만 포스팅 목록 당한 파일 방법(One-file-per-postings-list scheme)은 대부분의 파일 시스템이 크기가 매우 큰 파일들을 효율적으로 처리할 수 없기 때문에 실행이 불가능함
• 로그 병합(Logarithmic merging)
• 포스팅들이 이 일련의 색인에 스며들어 각 수준에서 단지 한 번만 처리됨
• n개까지의 포스팅은 기억장치 상의 Z0 보조 색인에 축적되고 n 값에 도달할 때, Z0에 있는 2^0Xn개의 포스팅은 디스크에 생성되는 새로운 색인 I0로 변환됨
• 하지만 정보 검색 시스템의 모든 측면에서 로그 병합은 시스템을 더 복잡하게 만듦
• 따라서 대형 시스템에서는 동적으로 색인을 구성하지 않으며, 주기적으로 새로운 색인을 구축함