ds2i
1.0.0
Estructuras de datos para índices invertidos (ds2i) es una biblioteca de estructuras de datos para representar las secuencias de números enteros utilizadas en índices invertidos.
Este código se utilizó en los experimentos de los siguientes artículos.
Giuseppe Ottaviano, Rossano Venturini, Índices Elias-Fano particionados , ACM SIGIR 2014.
Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, Compensaciones óptimas de espacio-tiempo para índices invertidos , ACM WSDM 2015.
El código está probado en Linux con GCC 4.9 y OSX Yosemite con Clang.
Se necesitan las siguientes dependencias para la compilación.
El código depende de varios submódulos de git. Si ha clonado el repositorio sin --recursive , deberá realizar los siguientes comandos antes de compilarlo:
$ git submodule init
$ git submodule update
Para construir el código:
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make
También es preferible realizar un make test , que ejecuta las pruebas unitarias.
El directorio test/test_data contiene una pequeña colección de documentos utilizados en las pruebas unitarias. El formato binario de la colección se describe en la siguiente sección.
Para crear un índice utilice el comando create_freq_index . Los tipos de índice disponibles se enumeran en index_types.hpp . Por ejemplo, para crear un índice utilizando el algoritmo de partición óptimo utilizando la colección de prueba, ejecute el comando:
$ ./create_freq_index opt ../test/test_data/test_collection test_collection.index.opt --check
donde test/test_data/test_collection es el nombre base de la colección, es decir, el nombre sin las extensiones .{docs,freqs,sizes} y test_collection.index.opt es el nombre de archivo del índice de salida. --check realiza un paso de verificación para comprobar la exactitud del índice.
Para realizar consultas BM25 es necesario crear un archivo adicional que contenga los parámetros necesarios para calcular la puntuación, como la longitud de los documentos. El archivo se puede construir con el siguiente comando:
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
Ahora es posible consultar el índice. Las queries de comando analizan cada línea de la entrada estándar como una colección de identificadores de términos separados por tabulaciones, donde el i-ésimo término es la i-ésima lista en la colección de entrada. Un conjunto de consultas de ejemplo se encuentra nuevamente en test/test_data .
$ ./queries opt and test_collection.index.opt test_collection.wand < ../test/test_data/queries
Esto realiza consultas conjuntivas ( and ). En lugar de and se pueden utilizar otros operadores ( or , wand , ..., consulte queries.cpp ), y también varios operadores separados por dos puntos ( and:or:wand ).
Para construir un índice óptimo en el tiempo para una distribución de consultas y un presupuesto de espacio determinados, es necesario seguir los siguientes pasos.
Primero, se debe crear un índice basado en bloques en la colección. Esto se utilizará para recopilar las estadísticas de acceso al bloque.
$ ./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
Luego, dada una secuencia de consultas tomadas de la distribución de consultas, podemos producir las estadísticas.
$ ./profile_queries block_optpfor ranked_and:wand:maxscore
test_collection.index.block_optpfor test_collection.wand
< ../test/test_data/queries
> query_profile
Para predecir el tiempo de decodificación del bloque necesitamos medirlo en una muestra.
$ ./profile_decoding block_optpfor test_collection.index.block_optpfor 0.1 > decoding_times.json
0,1 es la fracción de bloques muestreados. Para índices grandes se puede utilizar un número muy pequeño. Los tiempos medidos se pueden utilizar para entrenar el modelo lineal.
$ ./dec_time_regression.py parse_data decoding_times.json decoding_times.pandas
$ ./dec_time_regression.py train decoding_times.pandas > linear_weights.tsv
El script anterior requiere Numpy, Scipy, Pandas y Theano.
Finalmente podemos construir el nuevo índice, por ejemplo algo ligeramente más pequeño que el índice block_optpfor generado anteriormente.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 4000000 test_collection.index.block_mixed
Los puntos críticos calculados en el algoritmo codicioso se almacenan en caché en el archivo lambdas.bin , que puede reutilizarse para producir otros índices con diferentes compensaciones de espacio-tiempo. Para volver a calcularlos (por ejemplo, si cambia el perfil de consulta), simplemente elimine el archivo.
Ahora podemos consultar el í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
...
Tenga en cuenta que el nuevo índice es más rápido y más pequeño que el anterior. Por supuesto que estamos haciendo trampa aquí porque lo estamos probando con las mismas consultas con las que lo entrenamos; en una aplicación real, el conjunto de entrenamiento y prueba sería independiente.
También es posible generar una muestra de la curva de compensación con el siguiente comando.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 0 lambdas.tsv
El archivo lambdas.tsv contendrá una muestra de tripletas (lambda, espacio, tiempo estimado).
Una secuencia binaria es una secuencia de números enteros con el prefijo de su longitud, donde tanto los números enteros de la secuencia como la longitud se escriben como enteros sin signo little-endian de 32 bits.
Una colección consta de 3 archivos, <basename>.docs , <basename>.freqs , <basename>.sizes .
<basename>.docs comienza con una secuencia binaria singleton donde su único número entero es el número de documentos de la colección. Luego le sigue una secuencia binaria para cada lista de publicaciones, en orden de identificadores de términos. Cada lista de publicaciones contiene la secuencia de identificadores de documentos que contienen el término.
<basename>.freqs se compone de una secuencia binaria por lista de publicaciones, donde cada secuencia contiene los recuentos de ocurrencias de las publicaciones, alineados con el archivo anterior (tenga en cuenta, sin embargo, que este archivo no tiene una lista singleton adicional al principio).
<basename>.sizes se compone de una única secuencia binaria cuya longitud es la misma que la cantidad de documentos en la colección, y el i-ésimo elemento de la secuencia es el tamaño (número de términos) del i-ésimo documento.
