逆索引がある場合 (たとえば、ブルータスのページのソート済みリスト、シーザーのページのソート済みリスト、およびカルプルニアのページのソート済みリストがある場合)、シーザー AND ブルータス AND カルプルニアを実行すると、どこかで読みました。 calpurnia と brutus のページ数が caesar のページ数よりも少ない場合は、caesar AND (brutus と calpurnia) を実行する必要があります。つまり、後者の AND を最初に評価する必要があります。一般に、一連の AND がある場合は常に、ページ数が最も少ないペアを最初に評価します。この背後にある理由は何ですか？なぜこれが効率的なのですか？
2 に答える
0
逆索引のすべてのケースに当てはまるわけではありません。転置インデックス全体を順次スキャンする必要がある場合は、最初にどのポスティング リスト交差を実行するかは問題ではありません。
ただし、逆リストがインデックス付きの関係に格納されているシナリオを想定してください。この場合、ドキュメントの出現回数が少ないペアを評価することは、選択性の高い関係を結合することと同じであり、評価の効率が向上します。
直感的に、小さなリストを交差させると、一致を見つけるためのインデックスへのフィードとして使用されるより強力なフィルターが作成されます。
キーワード query a b c、 where a、bおよびcare のドキュメント内の単語を評価することに関心があるとします。また、一致するドキュメントの数が次のとおりであるとします。
a --> 20
b --> 100
c --> 1000
a+b --> 10
a+c --> 15
b+c --> 50
a+b+c --> 5
(a JOIN b)has size10と(b JOIN c)has sizeに注意してください50。したがって、1つ目は10のインデックスにアクセスするc必要があり、2 つ目は50のインデックスにアクセスする必要がありますa。しかし、ハッシュベースまたはツリーベースのインデックスを使用すると、そのようなインデックスへのアクセスのコストは大きく変わらず、通常は 1 回の I/O で実行されます。
于 2011-04-16T01:55:25.523 に答える
0
認識すべき重要なことは、既に述べた並べ替えのおかげで、たとえばバイナリ検索を使用して、任意のドキュメント ID を非常に効率的に (通常は対数時間で)転置リストを検索できることです。
その効果を確認するために、 querycaesar AND brutusを想定し、 occ caesarページcaesarと occ brutusページがあると仮定しますbrutus(つまり、occ Xはターム Xのページ リストの長さを示します)。ここで、例のために、 occ caesar > occ brutus 、つまりcaesarコンテンツ内で よりも頻繁に発生すると仮定しbrutusます。
次に、すべてのページで最初の を反復処理し、ページ リストでそれぞれを検索してを検索します。実際にリストを対数時間で検索できる場合、これは必要なことを意味しますbrutus caesar
occブルータス・ログ(occ caesar )
両方の用語を含むすべてのページを識別するための計算手順。
これを逆に行った場合(つまり、リストを繰り返し処理し、caesarリスト内の各ページを検索するbrutus)、小さい方の数値が対数になり、大きい方の数値が係数になるため、評価にかかる合計時間は次のようになります。もっと長くなる。
そうは言っても、実際にはこれよりも複雑であることを認識することも重要です。なぜなら、(a) リストはソートされるだけでなく、圧縮されているため、検索が難しくなり、(b) リストの一部がつまり、計算ステップの総数よりも、ディスク アクセスの総数の方が圧倒的に重要です。したがって、上記のアルゴリズムはそのままでは適用できない可能性がありますが、原理は説明したとおりです。
于 2012-03-06T11:41:32.163 に答える