ds2i
1.0.0
Data Structures for Inverted Indexes (ds2i) ist eine Bibliothek von Datenstrukturen zur Darstellung der in invertierten Indizes verwendeten Ganzzahlfolgen.
Dieser Code wurde in den Experimenten der folgenden Arbeiten verwendet.
Giuseppe Ottaviano, Rossano Venturini, Partitionierte Elias-Fano-Indizes , ACM SIGIR 2014.
Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, Optimale Raum-Zeit-Kompromisse für invertierte Indizes , ACM WSDM 2015.
Der Code wurde unter Linux mit GCC 4.9 und OSX Yosemite mit Clang getestet.
Die folgenden Abhängigkeiten werden für den Build benötigt.
Der Code hängt von mehreren Git-Submodulen ab. Wenn Sie das Repository ohne --recursive geklont haben, müssen Sie vor dem Erstellen die folgenden Befehle ausführen:
$ git submodule init
$ git submodule update
So erstellen Sie den Code:
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make
Es ist auch vorzuziehen, einen make test durchzuführen, der die Unit-Tests ausführt.
Das Verzeichnis test/test_data enthält eine kleine Dokumentensammlung, die in den Unit-Tests verwendet wird. Das Binärformat der Sammlung wird in einem folgenden Abschnitt beschrieben.
Um einen Index zu erstellen, verwenden Sie den Befehl create_freq_index . Die verfügbaren Indextypen sind in index_types.hpp aufgeführt. Um beispielsweise mithilfe der Testsammlung einen Index mit dem optimalen Partitionierungsalgorithmus zu erstellen, führen Sie den folgenden Befehl aus:
$ ./create_freq_index opt ../test/test_data/test_collection test_collection.index.opt --check
Dabei ist test/test_data/test_collection der Basisname der Sammlung, also der Name ohne die Erweiterungen .{docs,freqs,sizes} , und test_collection.index.opt ist der Dateiname des Ausgabeindex. --check führt einen Überprüfungsschritt durch, um die Richtigkeit des Index zu überprüfen.
Um BM25-Abfragen durchzuführen, muss eine zusätzliche Datei erstellt werden, die die zur Berechnung des Scores erforderlichen Parameter enthält, z. B. die Dokumentlängen. Die Datei kann mit dem folgenden Befehl erstellt werden:
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
Nun ist es möglich, den Index abzufragen. Die queries analysieren jede Zeile der Standardeingabe als tabulatorgetrennte Sammlung von Begriffs-IDs, wobei der i-te Begriff die i-te Liste in der Eingabesammlung ist. Ein Beispielsatz von Abfragen finden Sie wiederum in test/test_data .
$ ./queries opt and test_collection.index.opt test_collection.wand < ../test/test_data/queries
Dies führt konjunktive Abfragen ( and ) durch. Anstelle von and können andere Operatoren verwendet werden ( or , wand , ..., siehe queries.cpp ) und auch mehrere durch Doppelpunkt getrennte Operatoren ( and:or:wand ).
Um einen zeitoptimalen Index für eine bestimmte Abfrageverteilung und ein bestimmtes Speicherplatzbudget zu erstellen, müssen die folgenden Schritte ausgeführt werden.
Zunächst muss ein blockbasierter Index für die Sammlung erstellt werden. Dies wird zur Erfassung der Blockzugriffsstatistiken verwendet.
$ ./create_freq_index block_optpfor ../test/test_data/test_collection test_collection.index.block_optpfor
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
Anschließend können wir anhand einer Folge von Abfragen, die aus der Abfrageverteilung entnommen wurden, die Statistiken erstellen.
$ ./profile_queries block_optpfor ranked_and:wand:maxscore
test_collection.index.block_optpfor test_collection.wand
< ../test/test_data/queries
> query_profile
Um die Blockdekodierungszeit vorherzusagen, müssen wir sie an einer Stichprobe messen.
$ ./profile_decoding block_optpfor test_collection.index.block_optpfor 0.1 > decoding_times.json
0,1 ist der Anteil der abgetasteten Blöcke. Für große Indizes kann eine sehr kleine Zahl verwendet werden. Die gemessenen Zeiten können zum Trainieren des linearen Modells verwendet werden.
$ ./dec_time_regression.py parse_data decoding_times.json decoding_times.pandas
$ ./dec_time_regression.py train decoding_times.pandas > linear_weights.tsv
Das obige Skript erfordert Numpy, Scipy, Pandas und Theano.
Endlich können wir den neuen Index erstellen, zum Beispiel etwas, das etwas kleiner ist als der oben generierte block_optpfor -Index.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 4000000 test_collection.index.block_mixed
Die im Greedy-Algorithmus berechneten kritischen Punkte werden in der Datei lambdas.bin zwischengespeichert, die wiederverwendet werden kann, um andere Indizes mit unterschiedlichen Raum-Zeit-Kompromissen zu erstellen. Um sie neu zu berechnen (z. B. wenn sich das Abfrageprofil ändert), löschen Sie einfach die Datei.
Wir können jetzt den Index abfragen.
$ ./queries block_mixed ranked_and test_collection.index.block_mixed
test_collection.wand < ../test/test_data/queries
...
Mean: 9.955
...
$ ./queries block_optpfor ranked_and test_collection.index.block_optpfor
test_collection.wand < ../test/test_data/queries
...
Mean: 11.125
...
Beachten Sie, dass der neue Index sowohl schneller als auch kleiner ist als der alte. Natürlich schummeln wir hier, weil wir es mit denselben Abfragen testen, mit denen wir es trainiert haben; Auf einer realen Anwendung wäre der Trainings- und Testsatz unabhängig.
Mit dem folgenden Befehl ist es auch möglich, ein Beispiel der Kompromisskurve auszugeben.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 0 lambdas.tsv
Die Datei lambdas.tsv enthält eine Stichprobe von Tripeln (Lambda, Raum, geschätzte Zeit).
Eine Binärsequenz ist eine Folge von Ganzzahlen mit vorangestellter Länge, wobei sowohl die Ganzzahlen der Folge als auch die Länge als vorzeichenlose 32-Bit-Little-Endian-Ganzzahlen geschrieben werden.
Eine Sammlung besteht aus 3 Dateien: <basename>.docs , <basename>.freqs , <basename>.sizes .
<basename>.docs beginnt mit einer Singleton-Binärsequenz, deren einzige Ganzzahl die Anzahl der Dokumente in der Sammlung ist. Anschließend folgt für jede Beitragsliste eine Binärsequenz in der Reihenfolge der Begriffs-IDs. Jede Beitragsliste enthält die Sequenz von Dokument-IDs, die den Begriff enthalten.
<basename>.freqs besteht aus einer binären Sequenz pro Posting-Liste, wobei jede Sequenz die Vorkommensanzahl der Postings enthält, abgestimmt auf die vorherige Datei (beachten Sie jedoch, dass diese Datei am Anfang keine zusätzliche Singleton-Liste hat).
<basename>.sizes besteht aus einer einzelnen Binärsequenz, deren Länge mit der Anzahl der Dokumente in der Sammlung übereinstimmt, und das i-te Element der Sequenz ist die Größe (Anzahl der Begriffe) des i-ten Dokuments.
