CURSO DE BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO
CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
RECUPERAÇÃO DE INFORMAÇÃO B

Última alteração: 16. Janeiro 2007

${2}^{\underline{\rm o}}$ semestre de 2005
Professor: Nivio Ziviani (ICEx - Sala 4024)
Monitor: Álvaro Pereira Jr
Trabalho Prático 2: 11/10/2005
Data de Entrega: 05/12/2005

Processamento de Consultas

O objetivo deste trabalho é projetar e implementar um sistema de programas para responder eficiente e eficazmente consultas realizadas sobre o índice gerado a partir dos programas do Trabalho Prático 1.

Características do Sistema de Consultas

O sistema deverá:

1. Realizar ordenação (ranking) usando o modelo de espaço vetorial, mas utilizando filtro para considerar consulta booleana sobre o conjunto resposta, notadamente consultas com conector AND. Uma implementação ingênua da medida do cosseno é potencialmente cara, pois a lista invertida de todos os termos da consulta tem que ser percorrida integralmente para que a contribuição parcial do termo em cada documento seja adicionada no acumulador do documento em questão. Discuta possibilidades de tornar o processamento de consultas AND muito eficiente com relacao ao tempo de resposta (ou em relação ao número de consultas processadas por segundo), mas sem perder muita precisão nos documentos de topo do rank.

   O algoritmo normalmente utilizado para a implementação de consultas AND a partir do modelo vetorial pode ser visto abaixo.
   
   

   1. Inicialize a estrutura de acumuladores (A).
   2. Ordene os termos da consulta a partir dos valores de f_t.
   3. Calcule as similaridades entre documentos e consultas 
      (a) Processe a lista invertida do primeiro termo (menor f_t}) 
          da consulta de forma equivalente ao modelo vetorial padrão. 
      (b) Para os outros termos t_i da consulta faça: 
          i. Para cada dupla [d_j, tf_{i,j}] na lista do termo t_i faça: 
              Se existe um acumulador para o documento d_j então faça: 
                   A_j = A_j + w_{i,j} * w_{i,q}, 
   4. Remova os acumuladores dos documentos que não 
      possuam todos os termos da consulta. 
   5. Divida cada acumulador A_j pela norma do documento d_j. 
   6. Determine os k maiores acumuladores e retorne os
      documentos correspondentes.
   

2. Realizar ordenação (ranking) usando os seguintes modelos:
3. O algoritmo utilizado para a implementação de consultas AND mostrado acima.
4. O algoritmo que utiliza o model BM25, conforme a especificação mostrada aqui (texto adaptado da tese [1]).

Experimentos

As implementações deverão ser comparadas. Para realizar experimentos cada aluno deverá usar as coleções CACM, CISI e CFC em /pkg/texto2/collections/. Neste endereco estão os documentos (arquivos sgml), as consultas e os documentos relevantes relacionados com cada consulta.

Os experimentos devem medir:

• Eficiência do sistema (tempo de resposta e/ou número de consultas processadas por segundo).
• Eficácia do sistema de consultas (qualidade do ranking), através de curvas de precisão $\times$ revocação.

Observações

1. Utilizem um valor de $k$ igual a 200 documentos nos experimentos referentes a eficácia do sistema de consultas.
2. Apresentem os resultados dos modelos implementados comparados com o resultado obtido para o modelo vetorial padrão.
3. Está disponivel na página do curso uma biblioteca para o cálculo das medidas de revocação e precisão.

Referências

[1] B. A. V. Pôssas. Set-Based Vector Space Model: A new Approach for Correlation Based Model. Tese de Doutorado, Departamento de Ciência da Computação, UFMG, 22 de agosto de 2005.

[2] S. E. Robertson and K. S. Jones. Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3):129-146, May-June 1976.

[3] S. E. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford. Okapi at trec-3. In Proceedings of the Third Text Retrieval Conference (TReC-3), pages 109-126. NIST Special Publication 500-225, April 1995.

[4] Ian H. Witten, Alistair Moffat e Timothy C. Bell: Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, 1999, second edition.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 ri05tp2

The translation was initiated by Nivio Ziviani on 2007-01-16