ds2i
1.0.0
Les structures de données pour les index inversés (ds2i) sont une bibliothèque de structures de données pour représenter les séquences entières utilisées dans les index inversés.
Ce code a été utilisé dans les expériences des articles suivants.
Giuseppe Ottaviano, Rossano Venturini, Index Elias-Fano partitionnés , ACM SIGIR 2014.
Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, Compromis spatio-temporels optimaux pour les index inversés , ACM WSDM 2015.
Le code est testé sous Linux avec GCC 4.9 et OSX Yosemite avec Clang.
Les dépendances suivantes sont nécessaires pour la construction.
Le code dépend de plusieurs sous-modules git. Si vous avez cloné le référentiel sans --recursive , vous devrez exécuter les commandes suivantes avant de construire :
$ git submodule init
$ git submodule update
Pour construire le code :
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make
Il est également préférable d'effectuer un make test , qui exécute les tests unitaires.
Le répertoire test/test_data contient une petite collection de documents utilisés dans les tests unitaires. Le format binaire de la collection est décrit dans une section suivante.
Pour créer un index, utilisez la commande create_freq_index . Les types d'index disponibles sont répertoriés dans index_types.hpp . Par exemple, pour créer un index à l'aide de l'algorithme de partitionnement optimal à l'aide de la collection de tests, exécutez la commande :
$ ./create_freq_index opt ../test/test_data/test_collection test_collection.index.opt --check
où test/test_data/test_collection est le nom de base de la collection, c'est-à-dire le nom sans les extensions .{docs,freqs,sizes} , et test_collection.index.opt est le nom de fichier de l'index de sortie. --check effectue une étape de vérification pour vérifier l'exactitude de l'index.
Pour effectuer des requêtes BM25, il est nécessaire de construire un fichier supplémentaire contenant les paramètres nécessaires au calcul du score, tels que la longueur des documents. Le fichier peut être construit avec la commande suivante :
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
Il est désormais possible d'interroger l'index. Les queries de commande analysent chaque ligne de l'entrée standard comme une collection d'identifiants de termes séparés par des tabulations, où le i-ème terme est la i-ème liste de la collection d'entrée. Un exemple d'ensemble de requêtes se trouve à nouveau dans test/test_data .
$ ./queries opt and test_collection.index.opt test_collection.wand < ../test/test_data/queries
Cela effectue des requêtes conjonctives ( and ). À la place de and d'autres opérateurs peuvent être utilisés ( or , wand , ..., voir queries.cpp ), ainsi que plusieurs opérateurs séparés par deux points ( and:or:wand ).
Pour construire un index optimal dans le temps pour une distribution de requêtes et un budget d'espace donnés, il est nécessaire de suivre les étapes suivantes.
Tout d’abord, un index basé sur des blocs doit être construit sur la collection. Ceci sera utilisé pour collecter les statistiques de blocage d’accès.
$ ./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
Ensuite, à partir d’une séquence de requêtes échantillonnées à partir de la distribution des requêtes, nous pouvons produire les statistiques.
$ ./profile_queries block_optpfor ranked_and:wand:maxscore
test_collection.index.block_optpfor test_collection.wand
< ../test/test_data/queries
> query_profile
Pour prédire le temps de décodage des blocs, nous devons le mesurer sur un échantillon.
$ ./profile_decoding block_optpfor test_collection.index.block_optpfor 0.1 > decoding_times.json
0,1 est la fraction de blocs échantillonnés. Pour les grands index, un très petit nombre peut être utilisé. Les temps mesurés peuvent être utilisés pour entraîner le modèle linéaire.
$ ./dec_time_regression.py parse_data decoding_times.json decoding_times.pandas
$ ./dec_time_regression.py train decoding_times.pandas > linear_weights.tsv
Le script ci-dessus nécessite Numpy, Scipy, Pandas et Theano.
Nous pouvons enfin construire le nouvel index, par exemple quelque chose de légèrement plus petit que l'index block_optpfor généré ci-dessus.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 4000000 test_collection.index.block_mixed
Les points critiques calculés dans l'algorithme glouton sont mis en cache dans le fichier lambdas.bin , qui peut être réutilisé pour produire d'autres index avec des compromis spatio-temporels différents. Pour les recalculer (par exemple si le profil de requête change), supprimez simplement le fichier.
Nous pouvons maintenant interroger l'index.
$ ./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
...
Notez que le nouvel index est à la fois plus rapide et plus petit que l'ancien. Bien sûr, nous trichons ici parce que nous le testons avec les mêmes requêtes sur lesquelles nous l'avons formé ; sur une application réelle, la formation et l'ensemble de tests seraient indépendants.
Il est également possible de générer un échantillon de la courbe de compromis avec la commande suivante.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 0 lambdas.tsv
Le fichier lambdas.tsv contiendra un échantillon de triplets (lambda, espace, temps estimé).
Une séquence binaire est une séquence d'entiers préfixés par sa longueur, où les entiers de la séquence et la longueur sont écrits sous forme d'entiers non signés little-endian de 32 bits.
Une collection se compose de 3 fichiers, <basename>.docs , <basename>.freqs , <basename>.sizes .
<basename>.docs commence par une séquence binaire singleton où son seul entier est le nombre de documents de la collection. Elle est ensuite suivie d'une séquence binaire pour chaque liste de publication, par ordre d'identifiant de terme. Chaque liste de publication contient la séquence d'identifiants de document contenant le terme.
<basename>.freqs est composé d'une séquence binaire par liste de publications, où chaque séquence contient le nombre d'occurrences des publications, aligné sur le fichier précédent (notez cependant que ce fichier n'a pas de liste singleton supplémentaire à son début).
<basename>.sizes est composé d'une seule séquence binaire dont la longueur est la même que le nombre de documents de la collection, et le i-ème élément de la séquence est la taille (nombre de termes) du i-ème document.
