Informate Retrieval - Index Construction

결국 Inverted-Index 를 만드는 과정이다. 하지만 in-memory 에 다 올릴 수 없으니 disk 에 저장하는 방식으로 해야함.

BSBI (Blocked Sort-Based Indexing)

위에서 말했던 이유로 in-memory 에 다 올릴 수 없으니 block 단위로 처리한다.

그리고 그 block 들을 external sort 를 사용해서 정렬한다. 그런 다음 block 들을 merge 해서 최종적인 index 를 만든다.

BSBIndexConstruction()
    n <- 0
    while (all documents are not processed):
        do n <- n + 1
            block <- ParseNextBlock()
            BSBI-Invert(block)
            WriteBlockToDisk(block, fn)
    MergeIndexFiles(f1, f2, ... fn, f_merged)

SPIMI (Single-Pass In-Memory Indexing)

BSBI는 sort 를 사용해야하지만 SPIMI 는 sort 를 사용하지 않는다.

  • idea 1: 각 block 마다 dictionary 를 만든다.
  • idea 2: sorting을 하지 않는다.
SPIMI-Invert(token_stream)
    output_file <- NewFile()
    dictionary <- NewHashMap()
    while (free memory available)
    do token <- NextToken(token_stream)
        if term(token) not in dictionary:
            then postings_list <- AddToDictionary(dictionary, term(token))
        else:
            postings_list <- GetFromDictionary(dictionary, term(token))
        AddToPostingsList(postings_list, doc(token))
    sorted_terms <- SortTerms(dictionary)
    WriteBlockToDisk(sorted_terms, output_file)

    return output_file

token_stream에서 수집된 문서들 문서 번호 순서대로 차례대로 가져와서 postings list 는 정렬된 상태로 들어오고 계속 추가되면 된다. 그리고 term 을 정렬하면 끝!

Distributed Index Construction

구글의 MapReduce 를 사용해서 분산 처리를 한다.

해당 관련해서는 논문 리뷰를 했다. MapReduce 논문 리뷰

BSBI, SPIMI 는 분산 환경이 아닌 상황에서 설명이다. 분산 환경에서 여러 서버가 어떻게 에러 핸들링하고 하는 것이 어려워서 MapReduce를 한다. Map에서 Parsing 하고 Reduce에서 Invert 한다.

Dynamic Indexing

인덱스를 실시간으로 업데이트 한다. 이전에는 고정된 데이터를 인덱싱 했지만 이제는 실시간으로 업데이트 해야한다.

구성

  • 메인 인덱스: 디스크
  • 보조 인덱스: 인 메모리

보조 색인 꽉차면 메인 색인과 합친다. 보조 색인의 크기는 2배 씩 증가 시켜서 O(nlogn)O(n log n)에 끝내게 한다.