Curso de Pós-graduação em Ciência da Computação
Recuperação de Informação - Máquinas de Busca na Web

Última alteração: 14 de Fevereiro de 2010

1º semestre de 2010
Carga horária: 60 horas
Pré-requisito para a disciplina: Algoritmos e Estruturas de Dados III
Horario : Segunda: 09:25 - 11:05, Quarta: 09:25 - 11:05
Professores: Berthier Ribeiro-Neto e Nivio Ziviani
Monitor: Rickson Guidolini

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 máquinas de busca na Web. Um máquina de busca localiza documentos a partir das necessidades de informação colocadas pelo usuário, por meio de uma consulta formal. Em máquinas de busca, 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 uma máquina de busca é obter informação que é útil ou relevante para o usuário.

Objetivos Específicos da Disciplina

O objetivo principal da disciplina é investigar o projeto e implementação de técnicas e ferramentas que possibilitem o desenvolvimento de máquinas de busca para a WWW. Ao final do curso o aluno deverá conhecer em profundidade os principais componentes de uma máquina de busca para documentos Web.

A disciplina terá três objetivos principais:

• Estudar os coletores de páginas Web.
• Estudar técnicas para geração de um índice para coleções de 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 pelas máquinas de busca.

Cada aluno terá que construir protótipos dos três principais componentes de uma máquina de busca para a Web: coletor, indexador e processador de consultas. Faz parte também das atividades de cada aluno a coleta de parte da Web usando seu próprio coletor, o qual deverá colocar as páginas coletadas em um repositório central. A partir das páginas coletadas deverá ser criado um índice para ser utilizado pelo processador de consultas.

Programa

1. Coleta: arquitetura de um coletor de páginas web, principais problemas envolvidos.
2. Indexação: Arquivos invertidos e listas invertidas, compressão de textos, compressão de listas invertidas.
3. 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.
4. Avaliação da Recuperação: Precisão e revocação, coleções de referência.
5. Consultas: Consultas lógicas, consultas ordenadas por relevância, estruturas de acesso ao vocabulário, busca sequencial no vocabulário, busca exata e aproximada.

Bibliografia Básica

• Ricardo Baeza-Yates and Berthier Ribeiro-Neto: Modern Information Retrieval, Addison Wesley, 1999, 513 pages.
• Ian H. Witten, Alistair Moffat e Timothy C. Bell: Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, 1999, second edition.
• 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, 2005, 2006, 2007, 2008, 2009.
• 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 por meio de:

• Construção dos principais componentes de uma máquina de busca na web: coletor, indexador e processador de consultas. Cada alunos deve coletar páginas da Web, indexá-las e permitir que consultas sejam submetidas para a máquina de busca.
• Duas provas
• Seminários em sala de aula.

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 (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)

Links úteis

1. Codigo para ser usado no TP1
2. Search Engines Information Retrieval in Practice
3. Information Retrieval Resources
4. High Performance Index and Query Evaluation for IR
• Justin Zobel
• Alistair Moffat
5. Programa para geração de curvas revocação vs. precisão

--->

Aulas, Transparências e TPs

Aula	Mês	Dia	Assunto	Referência	TPs
01	Mar	08	Apres (Berthier e Nivio)	Apresentacao
02		10	Indexing (Nivio)	Apres, Indexing	TP1 (E)
03		15	Indexing (Nivio)	Vocabulario, Tese-Fabiano
04		17	Compressão do índice (Edleno)	Index compression
05		22	Boolean, Term weighting (Berthier)	Models
06		24	Vector, prober)at. models (Berthier)	Models
07		29	Set-based, ext.boolean, fuzzy models (Berthier)	Models
08		31	Generalized vector, latent semantic index, neural network models (Berthier)	Models
09	Abr	05	BM25, language, belief networks (Berthier)	Models
10		07	Avaliação (Berthier)	Evaluation
11		12	Avaliação (Berthier)	Evaluation
12		14	Prova 1
13		19	Processamento de consultas (Nivio)	Querying
14		26	Processamento de consultas (Rickson)	Querying	TP2 (E)
15		28	Processamento de Consultas (Rickson)	Querying
16	Mai	03	Processamento de Consultas (Nivio)	Querying
17		05	Avaliacao de relevancia (Rickson)	Pooling
18		10	Processamento de Consultas (Nivio)	Querying
19		12	Compressão de textos (Nivio)	Text compression, Z8.2
20		17	Modelos (Berthier)	Models
21		19	Modelos (Berthier)	Models
22		24	Modelos (Berthier)	Models
23		26	Modelos (Berthier)	Models
23		31	Classificacao (Rickson)	Classificacao
24	Jun	02	Classificacao (Rickson)	Classificacao
25		07	Classificacao (Rickson)	Classificacao
26		09	Classificacao (Berthier)	Classificacao
27	Jun	14	Seminarios 1 e 2	Lista de seminarios
28		16	Seminarios 3 e 4	Lista de seminarios	TP3 (E)
29		18	Seminarios 5 e 6 (AULA 08:30 HS)	Lista de seminarios
28		21	Seminarios 7 e 8	Lista de seminarios
29		23	Prova 2
30		28	Seminarios 9 e 10	Lista de seminarios
31		30	Seminarios 11 e 12	Lista de seminarios
32	Jul	02	Seminarios 13 e 14	Lista de seminarios
33		05	Seminarios 15 e 16	Lista de seminarios
34		07	Seminarios 17 e 18	Lista de seminarios