Curso de Pós-graduação em Ciência da Computação
Recuperação de Informação II

Última alteração: 15. Fevereiro 2006

2º semestre de 2005
Carga horária: 60 horas
Horario : A ser definido.
Professor: Nivio Ziviani (ICEx - Sala 4024)
Monitor: Alvaro Prereira Jr

Introdução

Recuperação de Informação (RI) é a atividade de recuperar itens de informação armazenados em um meio que possa ser acessado por computador. Um item de informação é geralmente constituído de texto (tais como documentos diversos, páginas Web, livros, etc.), embora possa conter outros tipos de dados tais como fotografias, gráficos e figuras. RI lida com a representação, armazenamento, organização e acesso a itens de informação. A representação e organização dos itens de informação deve prover ao usuário acesso facilitado à informação de seu interesse.

A área de RI cresceu muito em importância com a introdução da Web. A despeito de seu sucesso, a Web introduziu uma série de problemas por si mesma. De fato, encontrar informação util na Web é frequentemente uma tarefa tediosa e difícil. A maior dificuldade é a ausência de um modelo de dados claramente definido. Isto implica que a semântica e a estrutura dos dados é frequentemente mal definida e de baixa qualidade. Tais dificuldades tem atraído a atenção para a área de RI e suas técnicas como soluções promissoras.

O principal objetivo da disciplina é estudar algoritmos e estruturas de dados para construir sistemas de RI. Um sistema de RI localiza documentos a partir das necessidades de informação colocadas pelo usuário, através de uma consulta formal. Entretanto, caracterização da necessidade de informação do usuário é um problema não trivial. Em sistemas reais, essa necessidade de informação deve primeiro ser traduzida em termos de um conjunto de palavras chave que são então usados na formulação de uma consulta. Dada a consulta do usuário, o objetivo maior de um sistema de RI é obter informação que é útil ou relevante para o usuário. A enfase é na recuperação de informação e não na recuperação de dados.

Objetivos Específicos da Disciplina

Um dos objetivos gerais da disciplina é investigar o projeto e implementação de técnicas e ferramentas que possibilitem o desenvolvimento de sistemas avançados de informação para a WWW. Por sistemas avançados entenda-se sistemas dotados de: técnicas eficientes de indexação, técnicas eficazes de ordenação de documentos por ordem de relevância para o usuário, e interfaces cooperativas que auxiliem o usuário a formular consultas. Ao final do curso o aluno deverá conhecer em profundidade os principais componentes de um sistema de RI, tal como uma máquina de busca para documentos Web.

A disciplina terá dois objetivos principais:

• Estudo detalhado de técnicas de indexação na forma de aulas expositivas, seminários e prova. Vamos disponibilizar uma biblioteca para geração de um índice para coleções de documentos textuais (por exemplo, documentos web).
• Estudo e implementação dos principais modelos de recuperação de informação disponíveis na literatura. Esses modelos correspondem as estratégias de ranking implementadas pelos sistemas de recuperação de informação.

Ementa

A ementa do curso cobre os tópicos seguintes: indexação, modelagem, consultas, classificação, categorização, sistemas de informação para a Web.

Programa

1. Indexação: Arquivos invertidos e listas invertidas, compressão de textos, compressão de listas invertidas, arquivos de assinaturas, o que deve ser indexado, outros tipos de índices.
2. Modelagem: Modelos de RI, modelos clássicos de RI (booleano, vetorial e probabilístico), modelos algébricos alternativos, modelos probabilísticos alternativos, redes de inferência.
3. Avaliação da Recuperação: Precisão e revocação, coleções de referência.
4. Consultas: Consultas lógicas, consultas ordenadas por relevância, estruturas de acesso ao vocabulário, busca sequencial no vocabulário, busca exata e aproximada.
5. Sistemas de Informação para a Web: Caracterização da Web, Diretórios, Metabuscadores, Máquinas de busca: coleta de páginas na Web, indexação, consultas, interfaces.
6. Sistemas Paralelos e Distribuídos para RI: Geração paralela de índices, consulta em bases de dados distribuídas, arquiteturas MIMD.

Bibliografia Básica

• Ian H. Witten, Alistair Moffat e Timothy C. Bell: Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, 1999, second edition.
• Ricardo Baeza-Yates and Berthier Ribeiro-Neto: Modern Information Retrieval, Addison Wesley, 1999, 513 pages.
• Tutoriais das conferências ACM SIGIR de 2001 e 2002
• Artigos técnicos especializados que serão fornecidos mais adiante.
• Principais conferências e periódicos:
• World Wide Web Conference, 1999, 2000, 2001, 2002, 2003, 2004 e 2005.
• ACM SIGIR Conference on Research and Development in Information Retrieval
• String processing and Information Retrieval (SPIRE)
• ACM CIKM Information and Knowledge Management
• Conferências de bancos de dados: por ex. Very Large Data Bases (VLDB)
• ACM Transactions on Information Systems (TOIS)
• Journal of the American Society for Information Science and Technology (JASIST)
• IEEE Transactions on Knowledge and Data Engineering (TKDE)
• Information Management and Processing
• World Wide Web Journal (w3j.com)

Avaliação da Aprendizagem

Os alunos serão avaliados através de (i) projeto final de curso sobre um tópico de pesquisa a ser escolhido pelo aluno, possivelmente envolvendo implementação, com redação de um artigo técnico, (ii) prova referente as primeiras aulas do curso, que cobrem indexação, processamento de consultas lógicas, estruturas de armazenamento do vocabulário, revocação x precisão e coleções de referência, além dos tópicos de pequisa apresentados (mesmo que superficialmente), (iii) dois trabalhos práticos, (iv) seminários em sala de aula. A ordem dos pesos na avaliação, do maior para o menor, será projeto final, trabalhos práticos, prova e seminários em sala.

OBS: O conteúdo dos trabalhos práticos será apresentado posteriormente.

Links úteis

1. Pacote completo de transparências
2. Parser para documentos SGML
3. Programa para geração de curvas revocação vs. precisão

Descrição dos Tópicos de Pesquisa

1. Indexação

Esta linha de pesquisa tem por objetivo principal a geração eficiente de índices para grandes bases de dados textuais.

Principais tópicos: Arquivos invertidos, arranjos de sufixos, geração paralela de listas invertidas e arranjos de sufixos, busca exata e permitindo erros (ou busca aproximada), compressão de índice e texto, estudo das características de bases de dados textuais (distribuição de palavras, auto-similaridade), indexação por passagens, coleções dinâmicas com adição ao final.

Referências:

• Managing Gigabytes: Compressing and Indexing Documents and Images, Witten, Moffat, Bell. Second Edition, Morgan Kaufmann, San Francisco, 1999
• Compression and Coding Algorithms, Moffat, Turpin. Kluwer Academic Publishers, February 2002
• Block Merging for Off-Line Compression, Wan, Moffat. Proc. International Conference on Combinatorial Pattern Matching, Fukuoka, Japan, July 2002, 32-41
• Parsing Strategies for BWT Compression, Isal, Moffat. Proc. IEEE Data Compression Conference, Snowbird, Utah, March 2001, 429-438
• Adaptive Coding for Data Compression, Turpin, Moffat. Proc. 22nd Australasian Computer Science Conference, Auckland, New Zealand, January 1999, 63-74.
• Inverted Files Versus Signature Files for Text Indexing, Zobel, Moffat, Ramamohanarao. ACM Transactions on Database Systems, 23(4):453-490, December 1998.
• Compressed Inverted Files with Reduced Decoding Overheads, Anh, Moffat. Proc. 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Melbourne, Australia, August 1998, 290-297.
• Compression: A Key for Next-Generation Text Retrieval Systems. N. Ziviani, E. S. de Moura, G. Navarro and, R. Baeza-Yates. IEEE Computer, 33(11): 37-44, November, 2000.
• Adding Compression to Block Addressing Inverted Indices. G. Navarro, E. S. de Moura, M. Neubert and N. Ziviani and R. Baeza-Yates . Information Retrieval,3(1): 49-77, Kluwer Academic Publishers, 2000.
• Fast and flexible word searching on compressed text. E. S. de Moura, G. Navarro, N. Ziviani and R. Baeza-Yates . ACM Transactions on Information Systems (ACM TOIS), 18(2): 113-139, April 2000.
• Ziviani, N. and Moura, E.S. "Adding Compression to Next-Generation Text Retrieval Systems". In: Zelkowitz, M.V. (Ed.) Advances in Computers: Information Repositories, Academic Press, Volume 57, ISB N: 0-12-02157-3, 2003, 171-204.
• E. S. de Moura, Tese de Doutorado, DCC-UFMG, Belo Horizonte, Minas Gerais,Outubro, 1999.

2. Modelagem

Esta linha de pesquisa tem por objetivo principal aumentar a precisão durante o processo de consulta.

Principais tópicos: Modelagem clássica (booleana, vetorial, probalística, redes de inferência), Modelagem avançada (vetorial generalizado, indexação semântica latente, modelo baseado em teoria de conjuntos (set-based model)).

Referências:

• R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999. Chapters: 2.
• Stephen E. Robertson and Karen Sparck Jones. Relevance weighting of search terms. Journal of the American Society for Information Science. 27(3), pp. 129-146, May-June, 1976.
• S. E. Robertson and S. Walker and S. Jones and M. M. Hancock-Beaulieu and M. Gatford. Okapi at TReC-3. Proceedings of the Third Text Retrieval Conference (TReC-3). NIST Special Publication 500-225, pp. 109-126, April, 1995.
• J. M. Ponte and W. B. Croft. A Language Modeling Approach to Information Retrieval. Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 275-281, August, 1998, Melbourne, Australia.
• Põssas, Bruno Augusto Vivas E; Ziviani, Nivio; Meira Jr, Wagner; Ribeiro Neto, Berthier. Set-Based Model: A New Approach for Information Retrieval. Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval. New York, NY, USA: ACM Press, 2002. 230-237.
• Põssas, Bruno Augusto Vivas E; Ziviani, Nivio; Ribeiro Neto, Berthier; Meira Jr, Wagner. Set-Based Vector Model: An Efficient Approach for Correlation-Based Ranking. ACM Transactions on Information Systems. To appear. October, 2005.

3. Interfaces

Esta linha tem por objetivo principal a facilidade de uso através de interfaces gráficas dos sistemas de busca.

Principais tópicos: Formação da consulta, visualização dos resultados e Relevance feedback.

Referências:

R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999. Chapters: 4, 5 and 10.

4. Sistemas de Informação para a Web

Principais tópicos:

• Caracterização da Web: Como medir o tamanho da Web: Web estática, Web dinâmica
  Referências:
• R. Albert, L. Jeong and A.-L. Barabasi. Diameter of the world wide web. Nature, 401:130-131, 1999.
• A. Broder, S. Kumar, F. Maghoul P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins and J. Wiener. Graph structure in the web: experiments and models. In Proceedings of WWW'9, Amsterdan, 2000.
• Modelagem da Web: Lei de Heaps, Lei de Zipf, caracterizaçãoo de hábitos de usuários Web
  Referências:
• Cap. 6 livro BYR99.
• M. Hearst. Tilebars: Visualization of term distribution in full text information access. In Proceedings of ACM SIGCHI'95, pages 59-66, Denver, 1995
• B. Huberman, P. Pirolli, J. Pitkow and R. Lukose. Strong regularities in world wide web surfing. Science, 280:95-97, 1998.
• Máquinas de busca
• Arquiteturas: centralizadas, distribuídas, gerais, personalizadas, cache para máquinas de busca
• Coleta de páginas na Web (Crawling)
• Indexação
• Consultas: centralizada X distribuída; ranking: modelagem vetorial, análise de links, indexação semântica latente; busca por frases; busca por imagens; busca por músicas e filmes
• Interfaces

Referências:

• Managing Gigabytes: Compressing and Indexing Documents and Images, Witten, Moffat, Bell. Second Edition, Morgan Kaufmann, San Francisco, 1999
• R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999.
• S. Chakrabarti, M. van den Berg and B. Dom. Focused crawling: A new approach to topic-specific web resource discovery. In Proceedings of WWW'8, Toronto, 1999.
• J. Cho and H. Garcia-Molina. The evolution of the web and implications for an incremental crawler. In Proceedings of the 26th International Conference on Very Large Databases, 2000.
• J. Cho, H. Garcia-Molina and L. Page. Efficient crawling through url ordering. In Proceedings of WWW'7, pages 161-172, Brisbane, 1998.
• S. Deerwester, S. Dumais, G. Furnas, T. Landauer and R. Harshman. Indexing by latent semantic analysis. Journal of American Society for Information Science, 41(6):391-407, 1990.
• J. Rocchio. Relevance feedback in information retrieval. In G. Salton, editor, The Smart System: Experiments in Automatic Document Processing, pages 313-323. Prentice-Hall, Englewood Cliffs, NJ, 1971.
• L.A. Barroso, j. Dean e U. Holzle. Web Search for a Planet: The Google Cluster Architecture. IEEE Micro, pages 22-28, Mar-Abr 2003.
• K.M. Risvik, Y. Aasheim e M. Lidal. Multi-tier Architecture for Web Search Engines. La-Web, Santiago, Chile, Nov. 2003.

5. Diretórios

Como construir e avaliar, geração automática

Referências:

• Daniela Ferreira da Mota, Geração Semi-Automática de Diretórios para a Web.. M.Sc. in Computer Science, DCC/UFMG, 21 de setembro de 2001.

6. Metabuscadores

Geração de agentes e multi-agentes de busca, fusão de resultados

Referências:

• Victor Fernando Ribeiro, A Família Miner de Agentes para a World Wide Web, Dissertação de Mestrado, DCC/UFMG, 26 de fevereiro de 1998 (vide http://busca.uol.com.br/multibusca/).
• N. Craswell, D. Hawking and P. Thistlewaite. Merging results from isolated search engines. In Proceedings of the 10th Australasian Database Conference. Auckland, NZ, pages 189-200. Spinger-Verlag, 1999.
• D. Dreilinger and A. E. Howe. Experiences with selecting search engines using metasearch. ACM Transactions on Information Systems, 15(3):195-222, 1997.

7. Filtragem de documentos

Referências:

• Tânia de Fatima Acris Jesini, Filtragem de Informação: Uma Máquina de Busca para Notícias. 05 de outubro de 2001.

8. Categorização e classificação de documentos

Referências:

• E. Amitay. Using common hypertext links to identify the best phrasal description of target web documents. in Proceedings of ACM SIGIR'00, pages 296-303, Athens, Greece, 2000.
• E. Amitay. Automatically summarizing web sites - is there a way aroung it? In ACM 9th International Conference on Information and Knowledge Management (CIKM'00), Washington, DC, 2000.
• K. Bharat and M. Henzinger. Improved algoritms for topic distillation in a hyperlinked enviroment. In Proceedings of ACM SIGIR'98, pages 104-111, 1998.
• A. Broder, S. Glassman, M. Manasse and G. Zweig. Syntactic clustering of the web. In Proceedings of WWW'6, pages 391-404, 1997.
• Calado, P., Cristo, M., Moura, E.S., Ziviani, N., e Ribeiro-Neto, B. "Combining Link-Based and Content-Based Methods for Web Document Classification", ACM Twelfth International Conference on Information and Knowledge Management (CIKM'03), New Orleans, USA, November 2003.
• Cristo, M., Calado, P., Moura, E.S., Ziviani, N., e Ribeiro-Neto, B. "Link Information as a Similarity Measure in Web Classification", Proc. 10th String Processing and Information Retrieval Symposium (SPIRE'03), Springer-Verlag Lecture Notes in Computer Science, Manaus, Brazil, October 2003.
• Fonseca, B.M., Golgher, P.B., Moura, E.S. e Ziviani, N. "Using Association Rules to Discover Related Queries on Search Engines", First Latin American Web Congress, Santiago, Chile, November 2003.

Ontologias

Referências:

• Carr, Leslie et al Conceptual Linking: Ontology-Based Open Hypermedia, WWW10, may 2001.
• Sebastniani, F. Machine Learning in Automatic Text Categorization, ACM Computing Surveys 34 (1), 1-47.
• Han, E.H. Clustering Based on Association Rule Hypergraphs, SIGMOD 1997 Workshop on Research Issues on Data Mining and Knowledge Discovery.

Vocabulários controlados, uso de contexto (por ex., CEP)

Acesso a Bibliotecas Online

Mais instruções no site www.biblioteca.icex.ufmg.br seguindo a opç ao Sites de Pesquisa dentro de links (ou com a bibliotecária).

• Portal Periódicos da CAPES (www.periodicos.capes.gov.br) permite acesso a várias bibliotecas, inclusive a todo IEEE, a partir de qualquer endereço da UFMG, podendo ser acessado via site da biblioteca do ICEx (www.biblioteca.icex.ufmg.br)
• ACM: acesso a todas as publicações e conferências, de qualquer máquina do DCC/UFMG (www.acm.org/dl)
• Computer Science Bibliography, permite busca por autor, titulo de papers em geral (www.acm.org/sigs/sigmod/dblp/db/)
• IEEE: acesso a vários títulos da biblioteca online (www.computer.org), acesso via portal Periódicos da CAPES permite um acesso de cada vez, pegar senha com a bibliotecária
• Web of Science: contém informação bibliográfica de três bancos de dados: Science Citation Index Expanded, Social Science Citation Index, Arts and Humanities Citation Index (www.webofscience.fapesp.br)
• USENIX: Advanced Computing Systems Association (www.usenix.org), pegar senha com a bibliotecária
• Mathscinet (www.ams.org/mathscinet): acesso aos banco de dados Association Mathematical Society com cobertura nas áreas de matemática e computação, podendo ser acessado via site da biblioteca do ICEx (www.biblioteca.icex.ufmg.br)

Referências Úteis

• High Performance Index and Query Evaluation for IR
• Justin Zobel
• Alistair Moffat

Planejamento das Aulas

Aula	Mês	Dia	Assunto	Referência	TPs
01	Ago	02	Apresentacao do Curso	WMB99
02		04	Indexação: arquivos invertidos (AI)	WMB99
03		09	AI: constr.mem.sec. (intercalação mult.caminhos)	WMB99	TP1 (E)
04		11	Tópicos em RI (escolha projeto)	Tut.Sigir
05		15	Proc.consultas lógicas	WMB99
06		17	AI: como armaz. e acessar vocab.	WMB99
07		23	Compres. indices: unario, Elias, Golomb	WMB99, BYR99
08		25	Compres. texto: met. estat. e dicion.	WMB99, BYR99, Z8.2
09		30	Huffman, byte-Huf., canonico	WMB99, BYR99, Z8.2
10	Set	01	Reserva
11		03	Hashing perfeito mínimo	CHM92,HMWC93
12		06	Recall x precision, test collections	WMB99, BYR99
13		13	Reserva
14		15	Reserva
15		20	Semin. proj.pesq. (cada aluno fala 5 min.)
16		22	Semin. proj.pesq. (cada aluno fala 5 min.)
17		27	MIR: cap1	BYR99
18		29	MIR: cap2	BYR99
19	Out	04	VSM: intr., form. cosseno	WMB99
20		06	VSM: implem. sem poda	WMB99
21		11	VSM: com limit. acum. (quit e continue)	WMB99	TP2 (E)
22		13	VSM: usando Persin	WMB99
23		18	VSM: impl. eficiente	WMB99
24		20	VSM: impl. eficiente	WMB99
25		25	Outros modelos: redes Bayesianas	BYR99
26		27	Outros modelos: anal. links	BYR99
27	Nov	01	Outros modelos: Set-based model	BYR99
28		03	Seminários
29		08	Seminários
30		10	Seminários
28		15	Seminários
29		17	Seminários
30		22	Seminários