Was ist der jüngste Vergleich von Signaturdateien und invertierten Indizes?

7

Moderne Artikel zu Suchindizes enthalten häufig die Aussage, dass invertierte Indizes (Posting-Listen) Signaturdateien (Bloom-Filter) kategorisch überlegen sind. Hier einige Beispiele aus 2016 veröffentlichten Artikeln:

Während diese [Signaturdatei] -Technik einen relativ geringen Rechenaufwand bietet, haben Studien von Zobel et al. [1998] haben gezeigt, dass invertierte Dateien Signaturdateien deutlich übertreffen.

Invertierte Indizes wurden als die am besten verallgemeinerbare und leistungsfähigste Struktur bewertet (Zobel et al., 1998).

In jedem Artikel werden Zobel et al., Invertierte Dateien im Vergleich zu Signaturdateien für die Textindizierung , zitiert .

Wenn ich jedoch Zobel et al. Richtig, das Argument, das sie vorbringen, ist nicht grundlegend (z. B. eine asymptotische Grenze oder eine informationstheoretische Grenze). Vielmehr scheint das Argument zu sein, wenn Signaturdateien mit den Techniken X, Y und Z implementiert werden, verglichen mit invertierten Indizes, die mit den Techniken A, B und C implementiert wurden, und der aktuellen Technologie des Tages (Festplatten mit sehr hohem Such- / Zugriffsaufwand) ) sind invertierte Indizes überlegen, weil sie weniger Suchvorgänge erfordern und schneller sind.

Gibt es einen neueren Vergleich, der diese Techniken auf SSD, NVMe oder RAM vergleicht, oder gibt es einen neueren Vergleich, der sich mit "neuen" Techniken befasst, die seit 1998 erfunden wurden?

Dan
quelle

Antworten:

1

Ich kenne keine neuen Referenzen.

Aus dem Kopf:

Signaturdateien erfordern eine Kandidatenüberprüfung über Weiterleitungsdateien. Dies erfordert viele zufällige Zugriffe, im Grunde einen pro potenzieller Übereinstimmung. Ein zufälliger Speicherzugriff besteht aus mehr als 100 CPU-Zyklen. Sie können viel Arbeit in 100 CPU-Zyklen erledigen (z. B. können Sie mehr als 100 IDs Single Core http://boytsov.info/pubs/simdcompressionarxiv.pdf dekomprimieren ).

Die zufällige Zugriffsgeschwindigkeit ist bei Festplatten oder sogar SSDs noch schlechter. Tatsächlich besteht eine wachsende Lücke zwischen zufälliger und sequentieller Zugriffsgeschwindigkeit.

Bevor Sie diesen wahlfreien Zugriff vornehmen, können Sie keine Bereinigung, vorzeitige Beendigung usw. durchführen. Übrigens sollten Sie für die ausgefallenste aktuelle Datenstruktur wahrscheinlich die partitionierten Elias-Fano-Indizes überprüfen: http://pages.di.unipi.it/ rossano / wp-content / uploads / sites / 7/2015/11 / sigir14.pdf

Leonid Boytsov
quelle