ds2i
1.0.0
Estruturas de dados para índices invertidos (ds2i) é uma biblioteca de estruturas de dados para representar as sequências inteiras usadas em índices invertidos.
Este código foi usado nos experimentos dos artigos a seguir.
Giuseppe Ottaviano, Rossano Venturini, Índices Elias-Fano Particionados , ACM SIGIR 2014.
Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, Trocas ótimas de espaço-tempo para índices invertidos , ACM WSDM 2015.
O código foi testado em Linux com GCC 4.9 e OSX Yosemite com Clang.
As seguintes dependências são necessárias para a construção.
O código depende de vários submódulos git. Se você clonou o repositório sem --recursive , você precisará executar os seguintes comandos antes de compilar:
$ git submodule init
$ git submodule update
Para construir o código:
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make
Também é preferível realizar um make test , que executa os testes unitários.
O diretório test/test_data contém uma pequena coleção de documentos usados nos testes unitários. O formato binário da coleção é descrito na seção a seguir.
Para criar um índice use o comando create_freq_index . Os tipos de índice disponíveis estão listados em index_types.hpp . Por exemplo, para criar um índice usando o algoritmo de particionamento ideal usando a coleção de testes, execute o comando:
$ ./create_freq_index opt ../test/test_data/test_collection test_collection.index.opt --check
onde test/test_data/test_collection é o nome base da coleção, que é o nome sem as extensões .{docs,freqs,sizes} e test_collection.index.opt é o nome do arquivo do índice de saída. --check executa uma etapa de verificação para verificar a exatidão do índice.
Para realizar consultas no BM25 é necessário construir um arquivo adicional contendo os parâmetros necessários para calcular a pontuação, como o comprimento do documento. O arquivo pode ser construído com o seguinte comando:
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
Agora é possível consultar o índice. O comando queries analisa cada linha da entrada padrão como uma coleção de ids de termos separados por tabulações, onde o i-ésimo termo é a i-ésima lista na coleção de entrada. Um exemplo de conjunto de consultas está novamente em test/test_data .
$ ./queries opt and test_collection.index.opt test_collection.wand < ../test/test_data/queries
Isso executa consultas conjuntivas ( and ). No lugar de and outros operadores podem ser usados ( or , wand , ..., consulte queries.cpp ), e também vários operadores separados por dois pontos ( and:or:wand ).
Para construir um índice de tempo ótimo para uma determinada distribuição de consulta e orçamento de espaço é necessário seguir os seguintes passos.
Primeiro, um índice baseado em bloco deve ser criado na coleção. Isso será usado para coletar as estatísticas de acesso ao bloco.
$ ./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
Então, dada uma sequência de consultas amostradas da distribuição de consultas, podemos produzir as estatísticas.
$ ./profile_queries block_optpfor ranked_and:wand:maxscore
test_collection.index.block_optpfor test_collection.wand
< ../test/test_data/queries
> query_profile
Para prever o tempo de decodificação do bloco, precisamos medi-lo em uma amostra.
$ ./profile_decoding block_optpfor test_collection.index.block_optpfor 0.1 > decoding_times.json
0,1 é a fração de blocos amostrados. Para índices grandes, um número muito pequeno pode ser usado. Os tempos medidos podem ser usados para treinar o modelo linear.
$ ./dec_time_regression.py parse_data decoding_times.json decoding_times.pandas
$ ./dec_time_regression.py train decoding_times.pandas > linear_weights.tsv
O script acima requer Numpy, Scipy, Pandas e Theano.
Podemos finalmente construir o novo índice, por exemplo, algo um pouco menor que o índice block_optpfor gerado acima.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 4000000 test_collection.index.block_mixed
Os pontos críticos calculados no algoritmo ganancioso são armazenados em cache no arquivo lambdas.bin , que pode ser reutilizado para produzir outros índices com diferentes compensações espaço-temporais. Para recalculá-los (por exemplo, se o perfil da consulta for alterado), basta excluir o arquivo.
Agora podemos consultar o índice.
$ ./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
...
Observe que o novo índice é mais rápido e menor que o antigo. É claro que estamos trapaceando aqui porque o estamos testando com as mesmas consultas nas quais o treinamos; em um conjunto de treinamento e teste de aplicação real seria independente.
Também é possível gerar uma amostra da curva de trade-off com o seguinte comando.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 0 lambdas.tsv
O arquivo lambdas.tsv conterá uma amostra de triplos (lambda, espaço, tempo estimado).
Uma sequência binária é uma sequência de inteiros prefixados por seu comprimento, onde tanto os inteiros de sequência quanto o comprimento são escritos como inteiros sem sinal little-endian de 32 bits.
Uma coleção consiste em 3 arquivos, <basename>.docs , <basename>.freqs , <basename>.sizes .
<basename>.docs começa com uma sequência binária singleton onde seu único número inteiro é o número de documentos na coleção. É então seguido por uma sequência binária para cada lista de postagem, na ordem dos IDs dos termos. Cada lista de postagem contém a sequência de IDs de documentos que contêm o termo.
<basename>.freqs é composto por uma sequência binária por lista de postagens, onde cada sequência contém as contagens de ocorrências das postagens, alinhadas com o arquivo anterior (observe, porém, que este arquivo não possui uma lista singleton adicional em seu início).
<basename>.sizes é composto por uma única sequência binária cujo comprimento é igual ao número de documentos na coleção, e o i-ésimo elemento da sequência é o tamanho (número de termos) do i-ésimo documento.
