Logarithmic merging

IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったので、改めて復習してみました。

Dynamic indexing

頻繁に検索対象の文書群に更新が発生する場合の問題点は、(postings ファイルはディスク上にあるので) 転置インデックスをその都度構築し直すコストが高くなってしまうというところです。かといって更新をしないと、検索結果が古いままでヒットすべきものがヒットしなくなってしまいます。そこで Dynamic indexing の戦略を採ります。ディスク上の大きなインデックスであるメインのインデックスに加えて、インメモリの小さな補助インデックスを用意し、更新は補助インデックスに対して行います。クエリに対する検索は補助とメイン両方のインデックスに対して行い結果はマージして返す、というのが基本方針です。これで補助インデックスにその更新を反映させることができるので、新鮮なデータも、索引全体を再構築せずとも検索できるようになります。

当然、インメモリの補助インデックスに文書が追加され続けると、インデックスをメモリで保持しきれなくなります。そこで補助インデックスがある程度のサイズになったらメインインデックスにマージします。このマージ処理が少々厄介で、補助インデックスひとつ + メインインデックスの構成では、補助インデックスのサイズを n、T を postings の総数 (文書の総数) としたとき Θ(T2/n) の計算量が必要になってしまいます。マージ作業中はディスク上の巨大なインデックスに触れることになるので、この計算の間はパフォーマンスが低下してしまいます。もう少し速く処理を完了させたいところです。

マージしない方式

別の極端な戦略としては、一切マージしないという方法もあります。この場合、補助インデックスのサイズが満タンになったら補助インデックスをディスク上に書き出して、インメモリのインデックスは初期化します。メインインデックスとはマージしません。クエリは補助インデックスと、ディスク上にあるすべてのインデックスに対して行います。つまり、補助インデックスのサイズが満タンになる度クエリ対象のインデックスが増えるというものです。

これなら確かにマージ作業が必要ないので、マージに伴うパフォーマンス劣化はありません。一方で、インデックス個数が文書数に線形に増えていくことになるので、文書数の増加に伴いクエリ時間が劣化してしまいます。

Logarithmic merging

このように、クエリ時間とインデックスの更新にはトレードオフがあります。

Logarithmic merging はこのトレードオフをちょうどバランス良くしようというマージ方法です。マージしない方式ではインデックス個数が文書数に線形に増えていましたが、仮にこのインデックス個数を対数オーダーに抑えられると、クエリ時間の劣化もまあ許容できそうです。(クエリ時間を犠牲にしない全部マージの最初の方式に比べて) ある程度クエリ時間の劣化は許容したからにはマージの時間も抑えられるはず、というので、この方式ならマージにかかる計算量を Θ (T2/n) から Θ (Tlog(T/n)) に抑えることができます。

実際にどうするかというと、補助インデックスが満タンになった場合のマージを毎回ではなく時々、かつ、なるべく分割された一部のブロックにしか発生しないようにします。メインインデックスの索引は分割しつつ世代管理し、補助インデックスから作られた最初のメインインデックスの世代を 0、マージ操作で作成されたインデックスの世代を、g を最古の世代としたとき g + 1 とします。もし補助インデックスから新規にメインインデックスを作った場合に、同じ世代の別のインデックスがあったらそれらをマージする･･･ というアルゴリズムです。擬似コードは http://nlp.stanford.edu/IR-book/html/htmledition/dynamic-indexing-1.html にあります。

これだけだと良くわからないのでパワーポイントでアニメーションさせてみました。

アニメーションの最後のスライドにもあるように、世代が 0, 1, 2 とある時にメインインデックス側が満タンの場合は以下のように、20n, 21n, 22n サイズのインデックスができます。このまま続けていくと、世代が i の時に 2in サイズのインデックスが log T/n 個になります。

この方式だとマージ作業の計算量は Θ(Tlog(T/n)) で全体をマージする場合に比べて抑えられますし、インデックスの個数の増加も緩やかです。

パフォーマンスの比較

ここまでに出た3つの方式それぞれのクエリ時間とのトレードオフを考察した "Indexing Time vs. Query Time Trade-offs in Dynamic Information Retrieval Systems (PDF)" では、文書数が極端に少ないときにはマージしない方式が最良で、以降は Logarithmic merging がベストだという記述があります。

ちなみに Apache Lucene ではこの方式のマージがサポートされているそうです。

Python による Logarithmic merging の実装

たつをさんが以前に公開されていた Perl での実装を参考に、Python で Logarithmic merging をシミュレーションしてみました。たつをさんの例に同じく、token を整数で表してそれをひたすら追加しています。実際には token => postings list の key, value を追加していくことになります。

indexes という dict (ハッシュ) でアクティブな世代番号を管理して、アクティブな同世代のインデックスが被ったところで玉突きでマージ作業を行っていきます。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class LogarithmicIndex:
    n       = 2
    I       = [[]]
    Z       = [[]]
    indexes = {}

    @staticmethod
    def merge(p1, p2):
        p1.extend(p2)
        return sorted(p1)

    def add_token (self, token):
        I       = self.I
        Z       = self.Z
        indexes = self.indexes
        n       = self.n

        Z[0] = LogarithmicIndex.merge(Z[0], [ token ])
        if len(Z[0]) == n:
            i = 0
            while True:
                if i in self.indexes:
                    m = LogarithmicIndex.merge(I[i], Z[i])
                    if len(Z) > i + 1:
                        Z[i + 1] = m
                    else:
                        Z.append(m)
                    del indexes[i]
                else:
                    if len(I) >= len(Z):
                        I[i] = Z[i]
                    else:
                        I.append(Z[i])
                    indexes[i] = True
                    break
                i += 1
            Z[0] = []

    def find(self, token):
        if token in self.Z[0]:
            return True
        for i in self.indexes.keys():
            if token in self.I[i]:
                return True
        return False

    def print_indexes(self):
        print "indexes: %s" % self.indexes
        print "Z[0]: %s (%d)" % (self.Z[0], len(self.Z[0]))
        for i in xrange(len(self.I)):
            if i in self.indexes:
                print "I[%d]: %s (%d)" % (i, self.I[i], len(self.I[i]))
        print

idx = LogarithmicIndex()
for i in xrange(1, 10):
    idx.add_token(i)
    idx.print_indexes()

print idx.find(0)  # False
print idx.find(5)  # True
print idx.find(9)  # True
print idx.find(10) # False

以下は実行結果です。

% python logarithmic_merging.py
indexes: {}
Z[0]: [1] (1)

indexes: {0: True}
Z[0]: [] (0)
I[0]: [1, 2] (2)

indexes: {0: True}
Z[0]: [3] (1)
I[0]: [1, 2] (2)

indexes: {1: True}
Z[0]: [] (0)
I[1]: [1, 2, 3, 4] (4)

indexes: {1: True}
Z[0]: [5] (1)
I[1]: [1, 2, 3, 4] (4)

indexes: {0: True, 1: True}
Z[0]: [] (0)
I[0]: [5, 6] (2)
I[1]: [1, 2, 3, 4] (4)

indexes: {0: True, 1: True}
Z[0]: [7] (1)
I[0]: [5, 6] (2)
I[1]: [1, 2, 3, 4] (4)

indexes: {2: True}
Z[0]: [] (0)
I[2]: [1, 2, 3, 4, 5, 6, 7, 8] (8)
...

Logarithmic merging と二項ヒープ

IIR 4章には Logarithmic merging のインデックスのマージの遷移が wikipedia:二項ヒープ に似ているよ、という話があります。二項ヒープは二項木の集合でヒープを実現するデータ構造ですが、確かに二項ヒープも、次数が 0, 1, 2, 3 ... の木を持っていて、新しい節が追加されると Logarithmic merging と同じような増え方をします。二項ヒープについて詳しくはアルゴリズムイントロダクションでも解説されています。

この Logarithmic merging や二項ヒープでの各要素の増え方は、2進カウンタとして考えることができます。2進の各桁が 1, 2, 4, 8 ... とサイズを表していて、インデックスや節を追加するのは 2 進に 1 を加えたものと対応します。繰り上がりがマージ処理の発生箇所に対応します。

00000000 : 初期状態
00000001 : I[0] (サイズ 20n) が加わる
00000010 : I[0] + Z[0] = I[1] (20n)
00000011 : I[0], I[1] (20n, 21n)
00000100 : I[1] + Z[1] = I[2] (22n)
...

先のアニメーションと一緒に見ると、対応しているのがよく分かると思います。スライドの最後の状態は 00000111 です。

参考文献

[1] の第4章が主題です。HTML 版が http://nlp.stanford.edu/IR-book/html/htmledition/dynamic-indexing-1.html にて公開されています。[2] には各マージ手法のパフォーマンス比較が載っています。二項ヒープの解説は [3] が詳しいです。

Introduction to Information Retrieval

Introduction to Information Retrieval