Recuperação de Informação Distribuída por Fontes Autónomas com
Sobreposição
Tese de Doutoramento em Informática
Departamento
de Informática da Universidade
do Minho
Braga - Portugal
Setembro de 2001
Joaquim Melo Henriques de Macedo
A Recuperação de Informação em Rede é uma área recente de investigação,
definida com a intenção de repensar o campo já estabelecido da Recuperação da
Informação (RI) no contexto do WWW e da crescente digitalização e acesso na
Internet de fontes de informação das Bibliotecas convencionais.
O principal objectivo é disponibilizar ao utilizador final um sistema de RI
centralizado virtual, construindo programas que permitam seleccionar, de um
largo número de fontes de informação, aquelas que são relevantes para
uma determinada necessidade de informação do utilizador. Adicionalmente, deve
ser devolvido ao utilizador um único conjunto ordenado de documentos
pontuados.
Para que a recuperação da informação em rede se torne uma verdadeira
alternativa à recuperação de informação centralizada, é necessário encontrar
soluções eficientes e eficazes para um conjunto de problemas bem
definidos.
O primeiro aspecto é a selecção das fontes relevantes para uma dada
interrogação do utilizador -- o problema da selecção das Bases de Dados. Esta
selecção é feita com base em resumos dos conteúdos das fontes
(disponibilizados pelas próprias fontes ou construídos com base em
interrogações com um único termo), e deve ser introduzida para
substituir a simples difusão da interrogação, não escalável na presença dum
grande número de fontes de informação.
Como diferentes motores de busca podem ter linguagens de interrogação
diferentes, a abordagem comum é usar um conjunto reduzido das funcionalidades
comuns como linguagem de interrogação do sistema distribuído. Nesse
contexto, a correspondência de interrogações é uma tarefa trivial. Uma
abordagem mais eficiente, mas também mais complexa, é usar ao máximo a
capacidade de cada motor. Neste último caso, o problema da correspondência da
interrogação tem que ser
resolvido.
Outra questão pertinente é o problema da fusão dos resultados devolvidos por
fontes potencialmente heterogéneas que usam modelos, heurísticas e
algoritmos de pontuação diferentes. Este problema já se colocava
na recuperação de informação tradicional quando se combinavam diferentes
estratégias de recuperação de informação para melhorar a qualidade da
resposta. Também é possível que os items de informação devolvidos por cada
documento no conjunto de resposta variem
de sistema para sistema, colocando-se o problema da correspondência da
meta-informação.
Como em qualquer aplicação distribuída, na recuperação distribuída de
informação a replicação é usada para diminuir tempos de respostas e aumentar
a fiabilidade e disponibilidade do sistema. Portanto, a transparência
da replicação tem que ser assegurada ao nível de cada documento e de cada
fonte. Dito por outras palavras, o problema da sobreposição tem que ser
resolvido.
O principal objectivo desta tese é o estudo da sobreposição na recuperação da
informação em rede, principalmente no seu relacionamento com a selecção de
base de dados e a fusão de resultados. Assim, são propostos algoritmos de
selecção de bases de dados e fusão de resultados que consideram a
sobreposição como parâmetro de entrada. Esses algoritmos são avaliados
usando métodos e figuras de estilo normalizados. A introdução deste parâmetro
permite melhorar a eficácia
do resultado.
Um resultado colateral importante do trabalho realizado é a concepção e
concretização duma arquitectura que pode ser usada como bancada para
investigação e desenvolvimento dos tópicos mais em foco na recuperação de
informação em rede, apresentados nos parágrafos anteriores. O sistema
resultante, designado por Webtrieve (Web reTRIEVE), baseado no modelo do
espaço vectorial, pode também ser usado para iniciativas pedagógicas ou de
prestação de serviço de recuperação de informação.
Conteúdo
Cap.1:
Introdução
Motivação
Contexto da tese
Objectivos
As contribuições desta tese
A estrutura do documento
Cap.2:
Recuperação da Informação
Introdução
Modelos
Explicitação iteractiva de necessidades de informação
Avaliação
Recuperação distribuída da informação
Trabalho Relacionado
Cap. 3:
Arquitectura do Webtrieve
Descrição geral da arquitectura
Clientes
Robot
Indexador de Documentos
Base de Dados de Texto
Encaminhador de Interrogações
Realimentação de relevância
Actualizações incrementais dos ficheiros invertidos
Interacção entre diferentes componentes
Avaliação
Discussão
Cap. 4:
Sobreposição de Bases de Dados
Introdução
O que é a sobreposição?
Sobreposição
dinâmica
Sobreposição entre
documentos
Objectivos
Cálculo da sobreposição estática
Matriz de sobreposição
entre BDTs
Estimação com base nas
respostas às interrogações
Alocação de Documentos com sobreposição
Concretização
Replicação aleatória
com parâmetro de sobreposição
Variância na sobreposição
Experiências realizadas
Resultados para
sequências
Trabalho relacionado
Discussão
Cap.5:
Fusão de Resultados
Introdução
Definição formal do problema
Exemplos
Realimentação de
preferência
O problema
Trabalho relacionado
Ordem versus
pontuação
Combinação em
BDTs sobrepostas
Combinação em
BDT disjuntas
Discussão
Abordagem proposta
Descrição do
algoritmo
Arquitectura do
Fusor
Resultados experimentais
Compararação das
lógicas de fusão
Variação do
número de documentos
Variação com o
nível de sobreposição e número de BDTs
Discussão
Cap.6:
Selecção de Bases de Dados
Introdução
O problema da selecção de BDTs
Utilização da meta-informação
Métricas para avaliação da selecção
Utilização da informação de sobreposição
Abordagem Proposta
Um exemplo
Síntese do
algoritmo
Arquitectura do selector
Resultados Experimentais
Método proposto versus
CORI
CORI e sobreposição
Trabalho relacionado
Discussão
Cap. 7:
Concretização do Protótipo
Introdução
As razões de algumas opções
Cenários de utilização
O Ciclo de vida de uma fonte
Formatos para troca de informação
Extração de Informação
Dicionário de Termos
Motor de Busca e Encaminhador de Interrogações
Meta-informação
Comunicação entre os componentes
Avaliação da eficácia
Avaliação de eficiência
Ambiente utilizado
Abordagem utilizada
Resultados obtidos
Discussão
Cap. 8:
Conclusões e Trabalho Futuro
Conclusões
A Bancada Webtrieve
Sobreposição
Fusão
Selecção
Trabalho Futuro
Modularidade e
extensibilidade
Processamento das
Interrogações
Migração para Web
Eficiência e escala
Alocação e Replicação
Várias línguas
Vários média
Resumindo e concluindo
Bibliografia
Glossário
Bancada Experimental: Webtrieve
Foi concebida e concretizada uma arquitectura de motor de busca
distribuído que contempla todos os componentes necessários como Robot, BDT,
EI, Alocador de Documentos e Clientes.
Foram além disso concebidos e concretizados um conjunto um conjunto de
programas auxiliares que permitem a automatização da criação de fontes
suportadas por BDT distribuídas ou centralizadas. Essas fontes podem ser
avaliadas em termos de eficácia e eficiência usando metodologias usadas na
maior parte dos trabalhosreportados na literatura. Destaque-se em particular
a utilização das colecções de teste TREC
para avaliação da eficácia do sistema.
Foram utilizados procotocolos normalizados como o HTTP e STARTS para
comunicação entre os diversos componentes da arquitectura. A inclusão do STARTS
arantiu uma abordagem completa e abrangente à problemática da RI distribuída
O Dicionário de Termos foi concebido usando uma abordagem dual, para
suportar as listas de ocorrência longas e curtas, que permite a utilização do
Webtrieve emcenários dinâmicos como o WWW.
O Alocador de Documentos dispõe de algoritmos de alocação e replicação que
permitem a simulação em Laboratório de cenários de replicação coordenada e não
coordenada. Nesta tese utilizaram-se cenários de replicação não coordenada.
O protótipo Webtrieve foi concretizado usando a linguagem Java usando uma
abordagem modular e extensível. Já foi testado em laboratório em
ambiente multi-plataforma.
Para além da experiência adquirida e dos
resultados obtidos neste trabalho, construiu-se uma verdadeira bancada de
experiências para recuperação distribuída de informação textual. Esta bancada
permite realizar trabalho futuro em que seja possível concentrar, ao
contrário do que passou neste trabalho, as energias no problema concreto a
resolver sem ter de se criar condições a usar como ponto de partida.
Joaquim Macedo, António Costa and Vasco Freitas
Selection of
Overlapped Databases
Relatório Técnico
Joaquim Macedo, António Costa and Vasco Freitas
WEBTRIEVE:
A Testbed System for Distributed Information Retrieval
3rd Asian Digital Libraries Conference (ICADL), Seoul, Korea, Dec 6-8,
2000
Joaquim Macedo, António Costa and Vasco Freitas
Fusion
of Overlapped Result Sets
4th European Conference on Research and Advanced Technology for Digital
Libraries,
ERCIM, Lisbon, Portugal, Sep 18-20, 2000
Joaquim Macedo, António Costa and Vasco Freitas
WEBTRIEVE
- A Distributed Retrieval Architecture for Text Data Bases
Actas da 1ª Conferência de Redes de Computadores (CRC98), pp 127-130,
FCCN, Coimbra, Portugal, Nov 9-10, 1998 (in Portuguese)
Descargas
Documento completo da tese (em postscript): tese.ps
Acetatos usados na oral (em
PowerPoint): defesa.ppt
|