Download PDF
ads:
Universidade Federal do Amazonas
Instituto de Ciˆencias Exatas
Departamento de Ciˆencia da Computa¸c˜ao
Programa de P´os-Gradua¸c˜ao em Inform´atica
Avalia¸c˜ao de localidade em m´etodos de poda de ´ındices
para a Web
Bruno dos Santos de Ara´ujo
Manaus – Amazonas
Maio de 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Bruno dos Santos de Ara´ujo
Avalia¸c˜ao de localidade em m´etodos de poda de ´ındices
para a Web
Disserta¸c˜ao apresentada ao Programa de P´os-
Gradua¸c˜ao em Inform´atica do Departamento de
Ciˆencia da Computa¸c˜ao da Universidade Fed-
eral do Amazonas, como requisito parcial para
obten¸c˜ao do T´ıtulo de Mestre em Inform´atica.
´
Area de concentra¸c˜ao: Bancos de Dados e Recu-
pera¸c˜ao de Informa¸c˜ao.
Orientador: Prof. Dr. Edleno Silva de Moura
ads:
Bruno dos Santos de Ara´ujo
Avalia¸c˜ao de localidade em m´etodos de poda de ´ındices
para a Web
Disserta¸c˜ao apresentada ao Programa de P´os-
Gradua¸c˜ao em Inform´atica do Departamento de
Ciˆencia da Computa¸c˜ao da Universidade Fed-
eral do Amazonas, como requisito parcial para
obten¸c˜ao do T´ıtulo de Mestre em Inform´atica.
´
Area de concentra¸c˜ao: Bancos de Dados e Recu-
pera¸c˜ao de Informa¸c˜ao.
Banca Examinadora
Prof. Dr. Edleno Silva de Moura – Orientador
Departamento de Ciˆencia da Computa¸c˜ao – UFAM/PPGI
Prof. Jo˜ao Marcos Bastos Cavalcanti, Ph.D.
Departamento de Ciˆencia da Computa¸c˜ao – UFAM/PPGI
Prof. Dr. Maur´ıcio Figueredo
FUCAPI
Manaus – Amazonas
Maio de 2008
`
A todos aqueles que consideram a busca pelo conhecimento um dos grandes objetivos do ser
humano.
Agradecimentos
Se vocˆe tem uma ma¸c˜a e eu tenho uma ma¸c˜a e
trocarmos estas ma¸c˜as, ent˜ao eu e vocˆe teremos
ainda apenas uma ma¸c˜a. Mas se eu tenho uma
id´eia e vocˆe tem uma id´eia, e trocarmos nossas
id´eias, ent˜ao cada um de n´os ter´a duas id´eias.
George Bernard Shaw
Resumo
M´aquinas de busca desenvolvidas para a Web procuram manter bases de dados contendo c´opias
locais das p´aginas de interesse para seus usu´arios. O desempenho ´e um fator cr´ıtico nestes
sistemas pois em geral o volume de dados armazenados localmente e a quantidade de usu´arios
atendida por estes sistemas s˜ao muito grandes. O processamento de consultas em m´aquinas de
busca utiliza ´ındices conhecidos como listas invertidas. Uma das alternativas para melhorar o
desempenho de m´aquinas de busca ´e a utiliza¸c˜ao de m´etodos de poda, cujo objetivo ´e descartar
ou deixar de processar entradas das listas invertidas cuja contribui¸c˜ao para a ordena¸c˜ao das
respostas seja nula ou irrelevante. Esta disserta¸c˜ao apresenta um estudo sobre a aplica¸c˜ao de
informa¸c˜ao sobre o posicionamento de palavras em p´aginas da Web, sua localidade, em m´etodos
de poda. S˜ao estudados diversos aspectos relacionados `a utiliza¸c˜ao da informa¸c˜ao de localidade
como elemento determinante na escolha de por¸c˜oes a serem eliminadas de ´ındices e tamb´em
novos m´etodos de poda baseados em localidade que permitem a realiza¸c˜ao de poda durante o
processamento de consultas. Os resultados obtidos mostram que m´etodos de poda baseados em
localidade s˜ao eficazes em diferentes cen´arios.
Palavras-chave: Recupera¸c˜ao de Informa¸c˜ao, M´aquinas de Busca, Indexa¸c˜ao, M´etodos de Poda.
Abstract
Search engines built for the Web try to keep databases containing local copies of pages of interest
for their users. Performance is a critical factor in these systems because normally the volume of
stored data and the number of users served are very large. Query processing in search engines
uses indexes known as inverted lists. An alternative to improve the search engine performance
is the usage of pruning methods, which aims to discard or ignore inverted lists entries whose
contribution for the answer ranking is null or irrelevant. This thesis presents a study about the
application of word positioning information in Web pages, their locality, in pruning methods.
Several aspects are studied, related to the usage of locality information as determinant element
in choosing the index portions to be discarded and also related to new pruning methods based in
locality which allow pruning while the query is being processed. The results show that pruning
methods based in locality are effective in different scenarios.
Keywords: Information Retrieval, Search engines, Indexing, Pruning methods.
Sum´ario
1 Introdu¸c˜ao 1
1.1 Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 M´etodos de poda est´atica . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 M´etodos de poda dinˆamica . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Contribui¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Organiza¸c˜ao da disserta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Conceitos b´asicos 6
2.1 M´aquinas de busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Modelo vetorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 M´etodos de poda de ´ındices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Avalia¸c˜ao dos resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.1 Precis˜ao e revoca¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.2 Distˆancia entre listas (m´etrica Kendall’s tau) . . . . . . . . . . . . . . . . 10
3 Ambiente experimental 12
3.1 Tipos de consulta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Cole¸c˜oes de referˆencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Fun¸c˜ao de ordena¸c˜ao de respostas . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Documentos atˆomicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Valida¸c˜ao de m´etodos de poda baseados em localidade 16
4.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Cen´arios alternativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
i
Sum
´
ario ii
4.2.1 Apenas texto dos documentos . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2.2 Amostras da cole¸c˜ao WBR . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.3 Remo¸c˜ao de termos raros . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3 Precis˜ao em 5 e precis˜ao em 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5
´
Indice em camadas para poda dinˆamica 23
5.1 Vis˜ao geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Constru¸c˜ao do ´ındice em camadas . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.3 Avalia¸c˜ao de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.3.1 N´umero de camadas processadas . . . . . . . . . . . . . . . . . . . . . . . 26
5.3.2 Distˆancia de listas entre camadas . . . . . . . . . . . . . . . . . . . . . . . 27
5.3.3 Desvio padr˜ao dos resultados . . . . . . . . . . . . . . . . . . . . . . . . . 31
6 Conclus˜oes e trabalhos futuros 33
Referˆencias Bibliogr´aficas 35
Lista de Figuras
2.1 Exemplo de um espa¸co vetorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1 Similaridade das respostas usando Kendall’s tau obtidas pelos m´etodos LBPM, Full
Coverage, Top Fragments, Random e Carmel na cole¸c˜ao WBR usando consultas
disjuntivas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 Similaridade das respostas usando Kendall’s tau obtidas pelos m´etodos LBPM, Full
Coverage, Top Fragments, Random e Carmel na cole¸c˜ao WBR usando consultas
conjuntivas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Similaridade das respostas usando Kendall’s tau obtidas pelos m´etodos LBPM, Full
Coverage, Top Fragments, Random e Carmel na cole¸c˜ao WBR usando consultas por
frase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 P@10 (a) e P@5 (b) obtidos processando consultas com ´ındices podados pelos
m´etodos LBPM, Full Coverage, Top Fragments, Random e Carmel com diferentes
n´ıveis de poda. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.1 Divis˜ao das listas invertidas em camadas . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2 Similaridade m´edia de consultas disjuntivas e conjuntivas usando o n´umero de ca-
madas como crit´erio de parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.3 Gr´aficos para poda dinˆamica na cole¸c˜ao WBR10: (a) Similaridade m´edia e (b) n´ıvel
de poda obtidos em fun¸c˜ao do limiar utilizado para a distˆancia de listas entre os
resultados obtidos entre camadas; (c) Similaridade m´edia em fun¸c˜ao do n´ıvel de poda. 28
5.4 Gr´aficos para poda dinˆamica na cole¸c˜ao WBR12: (a) Similaridade m´edia e (b) n´ıvel
de poda obtidos em fun¸c˜ao do limiar utilizado para a distˆancia de listas entre os
resultados obtidos entre camadas; (c) Similaridade m´edia em fun¸c˜ao do n´ıvel de poda. 29
iii
Sum
´
ario iv
5.5 Compara¸c˜ao dos resultados para entre est´atica e dinˆamica obtidos na cole¸c˜ao WBR10
com consultas disjuntivas e conjuntivas . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.6 Compara¸c˜ao dos resultados obtidos entre poda est´atica e dinˆamica na cole¸c˜ao WBR12
com consultas informacionais, navegacionais e conjuntivas . . . . . . . . . . . . . . . 30
Lista de Tabelas
5.1 Desvio padr˜ao da similaridade m´edia na cole¸c˜ao WBR10 nos n´ıveis de poda especi-
ficados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 Desvio padr˜ao da similaridade m´edia na cole¸c˜ao WBR12 nos n´ıveis de poda especi-
ficados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
v
Cap´ıtulo 1
Introdu¸c˜ao
A necessidade por sistemas de busca eficientes vem aumentando ao longo do tempo, `a medida
em que mais e mais pessoas se interessam e passam a ter acesso a World Wide Web. Ao mesmo
tempo, a quantidade de informa¸c˜ao dispon´ıvel na Web aumenta a passos largos, pois usu´arios
que h´a pouco tempo eram apenas consumidores de informa¸c˜ao est˜ao se tornando produtores
desta mesma informa¸c˜ao. Um exemplo disso s˜ao os blogs, cujas p´aginas s˜ao criadas em massa
nos dias de hoje [20].
M´aquinas de busca desenvolvidas para a Web, em geral, procuram manter bases de dados
contendo c´opias locais das p´aginas de interesse para seus usu´arios, comumente denominadas
cole¸c˜oes. O desempenho ´e um fator cr´ıtico nestes sistemas porque o volume de dados armazena-
dos e a quantidade de usu´arios normalmente atendida por estes sistemas s˜ao muito grandes.
Tais sistemas utilizam estruturas de dados chamadas ´ındices[23] para permitir o processamento
eficiente das consultas, e um dos tipos mais comuns de ´ındice ´e o arquivo invertido. Este tipo
de ´ındice ´e composto pelo vocabul´ario, que cont´em todos os termos que ocorrem na cole¸c˜ao,
e listas invertidas, que indicam para cada termo os documentos onde este aparece juntamente
com alguma informa¸c˜ao adicional.
Uma das alternativas para melhorar o desempenho das m´aquinas de busca ´e a utiliza¸c˜ao de
m´etodos de poda de ´ındices[19, 7, 9, 17, 1], cujo objetivo ´e descartar ou deixar de processar
entradas das listas invertidas cuja contribui¸c˜ao para a ordena¸c˜ao das respostas seja nula ou
irrelevante. Estes m´etodos podem realizar poda est´atica, quando removem entradas do ´ındice
em disco antes que as consultas sejam processadas, ou dinˆamica, quando determinam durante
o processamento da consulta quais entradas dos ´ındices dever˜ao ser utilizadas. M´etodos de
1
1. Introduc¸
˜
ao 2
poda est´atica podem ser considerados m´etodos de compress˜ao com perdas, pois h´a certa perda
de informa¸c˜ao devido ao descarte de entradas dos ´ındices, e possuem a vantagem de acelerar o
processamento das consultas ao mesmo tempo em que reduzem o espa¸co em disco necess´ario para
os ´ındices. M´etodos dinˆamicos, por sua vez, mantˆem os ´ındices integrais em disco e permitem
estrat´egias diversas para selecionar quais entradas dever˜ao ser lidas, com a desvantagem de
necessitar de processamento adicional para a aplica¸c˜ao de tais estrat´egias.
Um estudo foi feito por Santos[11] sobre m´etodos de poda est´atica baseados em localidade,
cujo princ´ıpio de funcionamento leva em considera¸c˜ao o local onde os termos ocorrem dentro
dos documentos, definindo tais locais pela divis˜ao do documento em unidades chamadas de
passagens. Tais m´etodos partem do pressuposto de que os termos de determinados tipos de
consulta tendem a aparecer pr´oximos um dos outros dentro dos documentos, uma constata¸c˜ao
´obvia para consultas por frase e que tamb´em foi comprovada para consultas conjuntivas atrav´es
de experimentos. Termos s˜ao ditos pr´oximos se pertencem a uma mesma passagem, e s˜ao v´arios
os crit´erios que podem ser usados para a divis˜ao do documento nestas passagens.
Esta disserta¸c˜ao apresenta uma avalia¸c˜ao de m´etodos de poda baseados em localidade. Foram
realizados diversos experimentos visando o estudo do desempenho dos m´etodos de poda em
cen´arios n˜ao considerados por Santos, e a partir deste estudo ´e proposto um ´ındice reorganizado
em camadas onde cada camada ´e equivalente a uma poda est´atica com determinado n´ıvel de
compress˜ao. Este ´ındice em camadas serve como base para um m´etodo de poda dinˆamica,
tamb´em proposto nesta disserta¸c˜ao, que determina quantas camadas dever˜ao ser processadas
para que o resultado da consulta seja satisfat´orio utilizando evidˆencias da consulta, dos termos
da consulta ou ainda obtidas durante o processamento desta.
1.1 Trabalhos relacionados
1.1.1 M´etodos de poda est´atica
O m´etodo proposto por Carmel et al.[7] utiliza a pr´opria fun¸c˜ao de ordena¸c˜ao da m´aquina de
busca para efetuar a poda est´atica. Neste m´etodo, cada termo do vocabul´ario ´e submetido como
uma consulta, obtendo-se uma lista de resultados cujos documentos do topo ser˜ao mantidos na
lista invertida deste termo. Os crit´erios para a obten¸c˜ao dos documentos do topo podem ser dois:
as k primeiras respostas, sendo k um inteiro positivo, ou as δ primeiras respostas, 0 < δ ≤ 1,
1. Introduc¸
˜
ao 3
onde documentos com similaridade ao menos δ vezes a similaridade do documento do topo da
resposta ser˜ao mantidos. Por exemplo, sendo δ = 0.7, documentos cujo valor de similaridade
esteja abaixo de 70% do valor do documento do topo ser˜ao podados por este crit´erio.
O m´etodo Locality-Based Pruning Method (LBPM), proposto por Moura et al.[9], divide
os documentos em fragmentos chamados passagens e seleciona a cada passo a passagem que
possui maior quantidade de termos importantes do documento, at´e que seja atingido o n´ıvel
de compress˜ao desejado, e s˜ao mantidas nas listas invertidas dos termos apenas as entradas
correspondentes a documentos onde tais termos estejam em ao menos uma passagem selecionada.
Como s˜ao mantidas no´ındice n˜ao s´o entradas correspondentes a termos importantes mas tamb´em
todas as entradas da mesma passagem, exploram-se poss´ıveis rela¸c˜oes entre os termos que seriam
perdidas se cada termo fosse tratado de maneira independente.
Os termos importantes de cada documento s˜ao obtidos utilizando-se o m´etodo de Carmel:
faz-se uma poda de ´ındices com este m´etodo, obtendo para cada termo t uma lista de resultados
R
t
(δ), e os termos importantes para um documento D, denotados por T (D), s˜ao definidos como
T (D) = {t|D ∈ R
t
(δ), ∀t ∈ V }, sendo V o vocabul´ario. Estes termos s˜ao aqueles cujo conjunto
R
t
(δ) contenha D. Desta forma, para cada documento D basta que suas passagens sejam
ordenadas de acordo com o n´umero de termos importantes presentes e selecionar passagens at´e
que o n´ıvel de compress˜ao desejado seja atingido.
O m´etodo Full Coverage, proposto por Santos[11], possui um funcionamento similar ao
LBPM, pois divide o documento em passagens para selecionar as mais importantes nos passos
posteriores diferindo na maneira de selecionar as passagens. A importˆancia de cada passagem
´e computada atrav´es de uma adapta¸c˜ao de uma t´ecnica de sumariza¸c˜ao de texto proposta por
Mallet, Elding e Nascimento[17], denotada full coverage summarizer. A id´eia principal deste
sumarizador ´e selecionar passagens que ”cubram totalmente“ (fully cover) o espa¸co de conceitos
de um documento, escolhendo a cada passo a passagem com maior similaridade vetorial com o
documento, removendo termos de passagens j´a selecionadas.
Os m´etodos Top Fragments e Random, tamb´em propostos por Santos, utilizam heur´ısticas
mais simples para selecionar as passagens. O primeiro m´etodo parte do princ´ıpio que as pas-
sagens iniciais do documento s˜ao as que melhor o descrevem, uma id´eia utilizada com relativo
sucesso em m´etodos de gera¸c˜ao autom´atica de resumos [3, 15]. O segundo m´etodo seleciona
aleatoriamente passagens do documento at´e que seja atingido o n´ıvel de compress˜ao desejado, e
1. Introduc¸
˜
ao 4
parte do princ´ıpio que as informa¸c˜oes importantes est˜ao distribu´ıdas uniformemente pelo docu-
mento. O m´etodo Random, apesar de ser uma abordagem um tanto simples do problema, pode
ser usado como referˆencia para os outros m´etodos citados.
Nesta disserta¸c˜ao os quatro m´etodos de poda baseados em localidade descritos (LBPM, Full
Coverage, Top Fragments e Random) ser˜ao avaliados tendo como referˆencia de compara¸c˜ao o
m´etodo de Carmel, a exemplo de como foi feito por Santos.
1.1.2 M´etodos de poda dinˆamica
O m´etodo de poda dinˆamica proposto por Persin [19] determina durante o processamento da con-
sulta quais termos ou entradas das listas invertidas ser˜ao consideradas no c´alculo da similaridade.
Neste m´etodo os termos da consulta s˜ao processados em ordem decrescente de idf e as entradas
de suas listas invertidas s˜ao ordenadas de forma decrescente por freq¨uˆencia, utilizando-se lim-
iares para indicar a freq¨uˆencia m´ınima que uma entrada precisa ter para que seja considerada
no processamento. Estes limiares s˜ao o limiar de inser¸c˜ao e o limiar de adi¸c˜ao, que indicam
quando uma entrada do ´ındice poder´a inserir um novo acumulador ou atualizar um j´a criado,
respectivamente. As entradas processadas primeiro s˜ao as que mais contribuem para a ordena¸c˜ao
das respostas, por terem as maiores freq¨uˆencias, determinando rapidamente esta ordena¸c˜ao e
permitindo que o processamento seja finalizado pelos limiares sem que seja preciso utilizar todas
as entradas das listas ou todos os termos. Al´em dos limiares de freq¨uˆencia, podem ser utilizados
tamb´em limiares para determinar o n´umero m´aximo de acumuladores, trazendo uma economia
adicional de mem´oria.
Anh e Moffat [1] propuseram um m´etodo de poda dinˆamica baseado em um ´ındice de im-
pactos, onde as entradas das listas invertidas s˜ao ordenadas de maneira decrescente de acordo
com a sua contribui¸c˜ao no c´alculo da similaridade dos documentos. A cada entrada ´e associado
um n´umero que varia de k a 1, associando n´umeros menores `as entradas de menos contribui¸c˜ao
segundo uma distribui¸c˜ao exponencial. Desta forma, as entradas que mais contribuem para
a ordena¸c˜ao das respostas s˜ao processadas primeiro, a exemplo do que ocorre no m´etodo de
Persin. O processamento da consulta ocorre em quatro fases, com um n´umero decrescente de
acumuladores processados em cada uma delas.
Estes dois m´etodos consistem na reordena¸c˜ao das listas invertidas e no uso de crit´erios para
determinar quais por¸c˜oes das listas dever˜ao ser utilizadas pelo processador de consultas. O
1. Introduc¸
˜
ao 5
m´etodo de poda dinˆamica a ser proposto no Cap´ıtulo 5 segue esta mesma linha, utilizando
heur´ısticas pr´oprias para determinar a reordena¸c˜ao das listas invertidas e os crit´erios de sele¸c˜ao
das por¸c˜oes das listas invertidas.
1.2 Contribui¸c˜oes
As principais contribui¸c˜oes deste trabalho s˜ao relacionadas a seguir:
• Um estudo feito sobre os m´etodos de poda est´atica baseados em localidade, que resultou
na publica¸c˜ao de um artigo no peri´odico ACM Transactions on Information Systems[10].
• Implementa¸c˜ao dos m´odulos indexador e processador de consultas com a inclus˜ao de
m´etodos de poda est´atica para uma m´aquina de busca experimental, que far´a parte do
projeto SIRIAA (SIstema de Recupera¸c˜ao de Informa¸c˜ao em Ambiente com Advers´arios).
• Implementa¸c˜ao de vers˜oes dos m´odulos indexador e processador de consultas com suporte
a um ´ındice em camadas e a um m´etodo de poda dinˆamico proposto.
1.3 Organiza¸c˜ao da disserta¸c˜ao
O Cap´ıtulo 2 ir´a tratar dos conceitos b´asicos necess´arios para o entendimento adequado das
informa¸c˜oes apresentadas nesta disserta¸c˜ao, e o ambiente onde os experimentos foram realizados
ser´a mostrado no Cap´ıtulo 3. No Cap´ıtulo 4 ser˜ao mostrados os experimentos sobre poda est´atica
baseada em localidade, contendo um resumo dos experimentos realizados por Santos[11] e a
descri¸c˜ao dos novos experimentos realizados com o intuito de validar tais m´etodos de poda. O
´ındice em camadas e o m´etodo de poda dinˆamica baseado em localidade ser˜ao propostos no
Cap´ıtulo 5, juntamente com experimentos iniciais demonstrando a sua efic´acia. Conclus˜oes e
trabalhos futuros ser˜ao mostrados no Cap´ıtulo 6.
Cap´ıtulo 2
Conceitos b´asicos
2.1 M´aquinas de busca
Uma m´aquina de busca ´e um sistema capaz de localizar informa¸c˜oes em uma cole¸c˜ao de docu-
mentos atrav´es de consultas com palavras-chave. M´aquinas de busca desenvolvidas para a Web
basicamente possuem trˆes m´odulos: coletor, indexador e processador de consultas[4].
O m´odulo coletor ´e respons´avel pela obten¸c˜ao e armazenamento das p´aginas Web no formato
de cole¸c˜ao. Em linhas gerais, as p´aginas a serem coletadas s˜ao dispostas em uma fila onde cada
p´agina coletada ´e armazenada na cole¸c˜ao e seus apontadores s˜ao extra´ıdos e postos no final
da fila, obedecendo crit´erios determinados de acordo com o tipo de coleta desejada. Devido
`a natureza dinˆamica da Web este processo pode ocorrer continuamente, pois a todo momento
novas p´aginas s˜ao criadas, alteradas ou removidas, sendo necess´ario atualizar a cole¸c˜ao local de
acordo com estas mudan¸cas.
Para que as consultas possam ser processadas de maneira eficiente, ´e necess´ario que existam
estruturas de dados especializadas para este fim, denominadas ´ındices[23]. O m´odulo indexador
´e respons´avel pela cria¸c˜ao dos ´ındices, cujo tipo mais comum ´e o arquivo invertido. O arquivo
invertido ´e composto do vocabul´ario, que cont´em todos os termos distintos da cole¸c˜ao, e de listas
invertidas, uma para cada termo presente no vocabul´ario. As listas invertidas s˜ao compostas
de pares no formato <docid,info>, sendo o primeiro item um identificador de documento e o
segundo item uma informa¸c˜ao complementar. Existem dois tipos de lista invertida comumente
utilizados em m´aquinas de busca para a Web: listas de freq¨uˆencia, que armazenam a freq¨uˆencia
do termo no documento, e listas posicionais, cuja informa¸c˜ao complementar ´e a posi¸c˜ao do termo
6
2. Conceitos b
´
asicos 7
dentro do documento em rela¸c˜ao ao in´ıcio deste.
Ap´os a indexa¸c˜ao o m´odulo processador de consultas ´e executado, cuja implementa¸c˜ao nor-
malmente ´e atrav´es de um servidor capaz de receber consultas e retornar os resultados. Este
m´odulo ´e baseado em um modelo matem´atico que determina como as listas invertidas dever˜ao
ser processadas, quais documentos ser˜ao considerados na resposta e como os documentos da
resposta dever˜ao ser ordenados. Um dos modelos matem´aticos mais conhecidos para esta tarefa
´e o modelo vetorial.
2.2 Modelo vetorial
O modelo vetorial, proposto por Salton[21], considera um espa¸co vetorial onde os documentos
s˜ao representados por vetores e cada termo do vocabul´ario corresponde a uma dimens˜ao neste
espa¸co. Desta forma, a cole¸c˜ao pode ser vista como um conjunto de vetores que ocupa um
hiperplano n-dimensional, sendo n equivalente ao n´umero de termos do vocabul´ario (Figura
2.1). As coordenadas de cada dimens˜ao dos vetores s˜ao dadas pelo peso de cada termo dentro
do documento.
Figura 2.1: Exemplo de um espa¸co vetorial
No espa¸co vetorial dado como exemplo, temos duas dimens˜oes correspondentes aos dois
termos do vocabul´ario p
a
e p
b
, e o documento d
j
e a consulta q representados por vetores. O
ˆangulo entre os vetores ´e dado por θ. O peso de cada termo em cada documento ´e expresso pela
f´ormula
2. Conceitos b
´
asicos 8
w(d, t) = tf(d, t) × idf(t) (2.1)
, onde w(d, t) (weight) ´e o peso do termo t no documento d; tf(d, t) (term frequency) ´e a
freq¨uˆencia do termo t dentro do documento d, partindo do pressuposto de que se um termo
´e muito freq¨uente em um documento, ´e representativo para este; e idf (t) (inverse document
frequency) ´e a freq¨uˆencia inversa do termo t na cole¸c˜ao e expressa a importˆancia de um termo
dentro desta, de forma que se um termo est´a presente na maioria dos documentos este termo
geralmente n˜ao representa bem nenhum deles, recebendo um idf baixo. De maneira an´aloga,
se a palavra aparece em poucos documentos, deve ter uma alta representatividade para estes,
recebendo um valor de idf mais alto.
O c´alculo do idf ´e feito atrav´es da f´ormula
idf(t) = ln
N
n
t
(2.2)
, onde N ´e n´umero total de documentos na cole¸c˜ao e n
t
o n´umero de documentos onde o
termo t ocorre.
Como a consulta tamb´em ´e formada por termos que normalmente constam no vocabul´ario,
esta tamb´em pode ser representada como um vetor neste hiperplano, de maneira an´aloga aos
documentos da cole¸c˜ao. O problema da busca pode ser reduzido, ent˜ao, ao problema de se
achar os vetores mais similares ao vetor consulta, que pode ser facilmente resolvido atrav´es da
´
Algebra pela obten¸c˜ao do cosseno do ˆangulo entre os vetores. O valor do cosseno ´e diretamente
proporcional `a proximidade entre os vetores, sendo usado como um valor para quantificar a
similaridade entre estes.
O cosseno entre os vetores ´e dado pela f´ormula
sim(d, q) = cos θ =
t
i=1
w(i, d) × w(i, q)
t
i=1
(w(i, d))
2
×
t
i=1
(w(i, q))
2
(2.3)
, onde w(i, d) ´e o peso do termo i no documento d e w(i, q) ´e o peso do termo i na consulta
q.
Esta f´ormula usa a defini¸c˜ao de cosseno como o produto interno dos vetores dividido pela
multiplica¸c˜ao de suas normas. Desta forma, ´e necess´ario apenas calcular os pesos dos termos
2. Conceitos b
´
asicos 9
em cada documento para que seja calculada a similaridade entre eles.
2.3 M´etodos de poda de ´ındices
M´etodos de poda de ´ındices[19, 7, 9, 17, 1] s˜ao utilizados para melhorar o desempenho de
sistemas de busca, eliminando ou ignorando entradas das listas invertidas cuja contribui¸c˜ao
para a ordena¸c˜ao das respostas seja nula ou irrelevante. Tais m´etodos podem efetuar poda
est´atica ou dinˆamica.
M´etodos de poda est´atica visam eliminar por¸c˜oes das listas invertidas em disco, descartando-
as permanentemente e resultando em ´ındices menores e mais f´aceis de se processar. S˜ao execu-
tados logo ap´os a indexa¸c˜ao e utilizam evidˆencias presentes na cole¸c˜ao para determinar quais
por¸c˜oes devem ser eliminadas, sendo desej´avel saber de antem˜ao quais os tipos de consulta que
ser˜ao processadas para que a poda est´atica possa ser melhor ajustada. Uma desvantagem da
utiliza¸c˜ao destes m´etodos ´e ter de execut´a-los todas as vezes que os ´ındices forem atualizados,
pois tais altera¸c˜oes poder˜ao incluir entradas nas listas que n˜ao sejam relevantes para a ordena¸c˜ao
das respostas, ou recriados. Um exemplo ´e o m´etodo de Carmel [7].
M´etodos de poda dinˆamica visam utilizar o m´ınimo poss´ıvel das listas invertidas durante o
processamento das consultas, utilizando apenas o suficiente para que a lista de respostas seja
satisfat´oria para o usu´ario. Podem utilizar evidˆencias tanto da base de dados quanto da pr´opria
consulta, aumentando as informa¸c˜oes dispon´ıveis para a decis˜ao de quais por¸c˜oes das listas ser˜ao
utilizadas, podendo inclusive empregar diferentes estrat´egias para diferentes tipos de consulta.
Podem incorrer em um custo computacional significativo em m´aquinas de busca de grande porte
devido ao grande volume de consultas processadas por estas. Um exemplo de m´etodo dinˆamico
´e o m´etodo de Persin [19].
2.4 Avalia¸c˜ao dos resultados
2.4.1 Precis˜ao e revoca¸c˜ao
Precis˜ao e revoca¸c˜ao s˜ao duas m´etricas comumente utilizadas em avalia¸c˜ao de sistemas de
busca[2]. S˜ao definidas com base nos documentos recuperados em uma consulta e nos documen-
tos relevantes recuperados nesta consulta, ou seja, os documentos que atendem a esta consulta.
2. Conceitos b
´
asicos 10
Sendo N o conjunto de documentos relevantes (identificados por especialistas no t´opico da con-
sulta) e R o conjunto de documentos retornados, a precis˜ao ´e definida por
|N∩R|
|R|
e a revoca¸c˜ao
definida como
|N∩R|
|N|
. Em linhas gerais, a precis˜ao mostra quantos documentos relevantes foram
retornados ao usu´ario at´e a posi¸c˜ao atual da lista de respostas, enquanto que a revoca¸c˜ao mostra
quantos documentos relevantes foram retornados do total de relevantes.
Para facilitar a visualiza¸c˜ao dos resultados obtidos ´e tra¸cado um gr´afico que mostra a
evolu¸c˜ao da precis˜ao em fun¸c˜ao da revoca¸c˜ao, que ´e chamado de curva de precis˜ao e revoca¸c˜ao.
Na avalia¸c˜ao de um sistema de busca normalmente s˜ao utilizadas v´arias consultas, cuja quan-
tidade de documentos retornados e relevantes pode variar, gerando v´arias curvas com pontos
localizados em valores diferentes de revoca¸c˜ao. Para facilitar a obten¸c˜ao de uma m´edia destes
pontos ´e utilizado um m´etodo de interpola¸c˜ao chamado precis˜ao em 11 pontos, pondo os valores
de precis˜ao desde um valor de revoca¸c˜ao de 0% at´e 100%, de 10% em 10%.
Uma outra maneira de apresentar os resultados ´e fazer uma m´edia dos pontos de precis˜ao
obtidos, obtendo uma medida chamada precis˜ao m´edia (mean average precision - MAP). Se a
m´edia ´e feita com os valores de precis˜ao interpolados nos 11 pontos ´e chamada MAP interpolado,
caso contr´ario denomina-se MAP n˜ao-interpolado. Pode-se tamb´em utilizar a precis˜ao acumu-
lada (sem interpola¸c˜ao) at´e o quinto documento relevante ou at´e o d´ecimo documento relevante,
medidas chamadas respectivamente de precis˜ao a 5 (P@5) e precis˜ao a 10 (P@10).
2.4.2 Distˆancia entre listas (m´etrica Kendall’s tau )
Uma das maneiras de avaliar os resultados obtidos com m´etodos de poda de ´ındices ´e atrav´es
da distˆancia de listas entre os resultados obtidos com os ´ındices originais e os obtidos com os
´ındices podados. Neste trabalho ser´a utilizada uma varia¸c˜ao do m´etodo Kendall’s tau proposta
em [13], que compara os k elementos do topo de duas listas e produz uma pontua¸c˜ao que
indica o qu˜ao similares estas listas s˜ao. Esta pontua¸c˜ao varia desde 0, indicando topos iguais,
at´e k (3k − 1) /2, indicando topos completamente diferentes. O resultado ´e ent˜ao normalizado
atrav´es de uma f´ormula proposta em [7], onde x ´e o resultado original e x
= 1 −
2x
k(3k−1)
o
resultado normalizado, que ir´a agora variar de 0 para topos totalmente diferentes at´e 1 para
topos iguais. O c´alculo da pontua¸c˜ao ´e descrito a seguir.
Sejam T
1
e T
2
as por¸c˜oes com k documentos do topo de cada resultado. Para cada par de
documentos distintos (i, j), onde i e j pertencem a T
1
T
2
, ´e atribu´ıda uma penalidade S(i, j)
2. Conceitos b
´
asicos 11
de acordo com os casos a seguir:
• Caso 1: i e j aparecem nos dois topos. Se estes documentos aparecem na mesma ordem,
ou seja, i aparece antes de j ou j aparece antes de i nas duas listas, S(i, j) = 0. Caso
contr´ario, S(i, j) = 1.
• Caso 2: i e j aparecem em uma das listas, mas apenas i ou apenas j aparecem na outra
lista. Supondo que i e j apare¸cam em T
1
e apenas i apare¸ca em T
2
, se i vier antes de j em
T
1
ent˜ao S(i, j) = 0, caso contr´ario S(i, j) = 1. Isso se deve ao fato de que se j n˜ao aparece
em T
2
ele dever´a estar abaixo do topo na lista, mantendo desta forma os documentos i e
j na mesma ordem nas duas listas. Se i e j estivessem na ordem contr´aria em T
1
, ent˜ao
pelo mesmo racioc´ınio a penalidade S(i, j) seria 1.
• Caso 3: Apenas i aparece em um dos topos, e apenas j aparece no outro topo. Neste
caso, S(i, j) = 1, pois seguindo o mesmo racioc´ınio do caso anterior o segundo documento
estar´a abaixo do topo nas duas listas, implicando que a ordem de i e j ´e obrigatoriamente
inversa.
• Caso 4: i e j aparecem em um dos topos, mas nenhum dos dois aparece no outro topo.
Neste caso n˜ao h´a informa¸c˜ao suficiente para determinar a penalidade, pois n˜ao ´e conhecida
a ordem entre i e j na outra lista, sendo utilizada neste caso uma penalidade neutra
S(i, j) = p. Ser´a utilizado neste trabalho p = 1/2, como proposto em [7].
A soma de todas as penalidades calculadas ser´a o resultado final, ao qual ser´a aplicada a
f´ormula de normaliza¸c˜ao.
Cap´ıtulo 3
Ambiente experimental
Neste cap´ıtulo ser´a descrito o ambiente onde os experimentos descritos foram realizados,
mostrando detalhes relevantes para a compreens˜ao dos resultados deste trabalho e de outros
que servir˜ao de referˆencia.
3.1 Tipos de consulta
M´aquinas de busca normalmente oferecem diversas op¸c˜oes de consulta para seus usu´arios. Em
geral, trˆes tipos de consultas s˜ao importantes para sistemas de busca: disjuntivas, conjuntivas e
por frase. Estes tipos s˜ao descritos a seguir:
• Disjuntivas: apenas um dos termos da consulta precisa estar presentes nos documentos.
Por exemplo, uma consulta pelos termos ”autom´ovel”e ”carro”retornaria documentos onde
constasse ao menos um destes termos.
• Conjuntivas: todos os termos da consulta precisam estar presentes em um documento
para que este seja considerado na resposta. Um exemplo seria uma consulta pelos termos
”carros usados Manaus”, onde apenas documentos com estes 3 termos ao mesmo tempo
seriam retornados.
• Frases: todos os termos da consulta precisam aparecer consecutivamente e na mesma
ordem dentro dos documentos da resposta. Por exemplo, uma consulta por ”la belle de
jour”(nome de um filme de 1967 e tamb´em de uma m´usica de Alceu Valen¸ca) retornaria
apenas documentos que possu´ıssem esta frase exata no seu interior.
12
3. Ambiente experimental 13
Consultas conjuntivas s˜ao as mais populares, sendo aparentemente usadas como padr˜ao
em m´aquinas de busca como Google
1
e Altavista
2
. Aproximadamente 81,1% das consultas do
log do WBR com mais de um termo s˜ao conjuntivas, em contraste a consultas por frase e
disjuntivas, que constituem respectivamente 18.3% e 0.6% das consultas submetidas com mais
de um termo. Consultas com apenas um termo podem ser vistas como um caso particular, pois o
resultado obtido independe do tipo de consulta especificado. Uma consulta por frase, disjuntiva
ou conjuntiva com apenas um termo resulta no mesmo conjunto de respostas.
Com rela¸c˜ao `a inten¸c˜ao do usu´ario, as consultas podem ser classificadas da seguinte forma[5]:
• Informacional: consultas por um determinado assunto/t´opico, normalmente atendidas por
mais de uma p´agina;
• Navegacional: consultas pelo endere¸co de uma p´agina, seja de uma empresa, de uma
pessoa, de uma institu¸c˜ao, etc.; em geral apenas um resultado ´e relevante para o usu´ario;
• Transacional: consultas com o objetivo de efetuar uma transa¸c˜ao. Exemplos: fazer uma
compra, pesquisar sobre pacotes de viagem, procurar arquivos para download, etc.
3.2 Cole¸c˜oes de referˆencia
A cole¸c˜ao WBR cont´em 10.077.722 p´aginas Web coletadas da Web brasileira em 1999, e foi
escolhida para que os experimentos pudessem ser feitos em um ambiente real de m´aquina de
busca, de forma a validar melhor as id´eias apresentadas. Foi utilizado nos experimentos um log
de 3 milh˜oes de consultas submetidas ao WBR por usu´arios reais. Este log ´e uma das raz˜oes
principais da escolha da cole¸c˜ao WBR para os experimentos, pois fornece informa¸c˜oes ´uteis
sobre as preferˆencias dos usu´arios da m´aquina de busca. Foram selecionadas aleatoriamente
do log consultas conjuntivas, disjuntinvas e por frase, cada categoria contendo 1000 consultas.
Tamb´em foram selecionadas consultas informacionais e navegacionais, cada conjunto contendo
200 consultas.
A cole¸c˜ao LAT faz parte da TREC[14] e ´e composta de artigos publicados no jornal Los
Angeles Times, contendo aproximadamente 132.000 documentos. Para esta cole¸c˜ao as consultas
foram selecionadas dos t´opicos 401 a 450 pertencentes `as sess˜oes ad-hoc da TREC 8. Foram
1
http://www.google.com
2
http://www.altavista.com
3. Ambiente experimental 14
utilizados os t´ıtulos dos t´opicos como consultas curtas, e estas consultas foram submetidas para
a m´aquina de busca como consultas disjuntivas e conjuntivas. A raz˜ao de se utilizar uma cole¸c˜ao
de documentos convencionais nos experimentos ´e a investiga¸c˜ao de poss´ıveis diferen¸cas entre a
aplica¸c˜ao dos m´etodos de poda em cole¸c˜oes Web e cole¸c˜oes convencionais.
3.3 Fun¸c˜ao de ordena¸c˜ao de respostas
Os experimentos descritos neste trabalho utilizaram cinco tipos de fun¸c˜oes para a ordena¸c˜ao das
respostas, cujo prop´osito ´e associar cada documento da resposta a um valor de similaridade com a
consulta s(d, q), sendo d o documento e q a consulta, para posterior ordena¸c˜ao destes documentos
pela similaridade. As evidˆencias utilizadas por estas fun¸c˜oes s˜ao relacionadas abaixo:
• s
c
: similaridade vetorial da consulta q com o documento d; [22, 2];
• s
a
: similaridade vetorial de q com a concatena¸c˜ao dos textos de ˆancora associados a d;
• s
h
: valor de autoridade de d, computado como descrito em [16, 6];
• s
p
: valor de PageRank de d[18].
As fun¸c˜oes de ordena¸c˜ao de respostas utilizadas nos experimentos s˜ao descritas a seguir:
1. s(d, q) = [1 − (1 − (s
c
(d, q)) × (1 − (s
a
(d, q)) × (1 − (s
h
(d, q))] - combina¸c˜ao bayesiana,
implementada como sugerido por Calado et al. [6];
2. s(d, q) = [1−(1−(s
c
(d, q))×(1−(s
a
(d, q))×(1−(s
p
(d, q))] - semelhante `a f´ormula anterior,
mas utilizando o valor de PageRank no c´alculo ao inv´es da autoridade;
3. s(d, q) = 0.8 × s
c
+ 0.2 × s
a
+ 0.1 × s
p
- combina¸c˜ao linear para consultas navegacionais
aleat´orias;
4. s(d, q) = 0.9 × s
c
+ 0.1 × s
a
- combina¸c˜ao linear para consultas informacionais aleat´orias;
5. s(d, q) = s
c
- similaridade vetorial com do texto dos documentos.
Para as quatro primeiras fun¸c˜oes os valores de todas as evidˆencias s˜ao normalizados, ou seja,
est˜ao no intervalo [0, 1]. As fun¸c˜oes 3 e 4 foram obtidas atrav´es de treinamento.
3. Ambiente experimental 15
3.4 Documentos atˆomicos
Quando se utilizam m´etodos baseados em localidade para poda de ´ındices, alguns documen-
tos n˜ao s˜ao afetados por estes m´etodos. Tais documentos s˜ao os documentos vazios, que s˜ao
retornados com base em outras evidˆencias al´em da textual, e documentos com apenas uma
passagem, pois os m´etodos de poda baseados em localidade possuem a caracter´ıstica de man-
ter ao menos uma passagem dos documentos. Estes documentos s˜ao chamados de documentos
atˆomicos, devido a sua propriedade de serem considerados sempre integralmente pelo m´etodo de
poda, e podem ser relevantes para seus usu´arios mesmo que n˜ao contenham ou contenham pouco
texto. Um exemplo disso s˜ao p´aginas de entrada de sites (home pages), que apesar de ter como
conte´udo apenas um texto curto ou uma imagem/anima¸c˜ao podem ser resultados relevantes
para consultas navegacionais.
Cap´ıtulo 4
Valida¸c˜ao de m´etodos de poda
baseados em localidade
4.1 Introdu¸c˜ao
Os experimentos realizados por Santos[11] comparam 4 m´etodos de poda est´atica baseados
em localidade (LBPM, Full Coverage, Top Fragments e Random) utilizando como referˆencia o
m´etodo de Carmel[7], nas cole¸c˜oes LAT e WBR. Os experimentos feitos com a cole¸c˜ao WBR
para avaliar a distˆancia entre listas utilizaram a fun¸c˜ao de ordena¸c˜ao de respostas 1 (mostrada na
Se¸c˜ao 3.3) e mostraram que para consultas disjuntivas todos os m´etodos produziram resultados
muito similares ao resultado original, com um valor de similaridade acima de 0.90 em todos os
n´ıveis de compress˜ao utilizados. Em consultas conjuntivas e por frase os m´etodos baseados em
localidade, incluindo os relativamente simples Top Fragments e Random, produziram resultados
ligeiramente melhores quando comparados ao m´etodo de Carmel, o que demonstra a efic´acia da
localidade como heur´ıstica para guiar o processo de poda.
Para a cole¸c˜ao LAT, cujas consultas foram processadas utilizando apenas o texto dos docu-
mentos como evidˆencia (fun¸c˜ao 5), os valores de similaridade obtidos com consultas disjuntivas
mostraram que o m´etodo de Carmel atingiu resultados melhores do que todos os outros m´etodos
com uma diferen¸ca significativa, um resultado esperado devido ao fato do m´etodo de Carmel
ter sido originalmente proposto levando em considera¸c˜ao este tipo de consulta e esta fun¸c˜ao
de ordena¸c˜ao de respostas. Em consultas conjuntivas todos os m´etodos produziram resulta-
dos semelhantes, embora os valores absolutos de similaridade entre listas tenham sido em geral
16
4. Validac¸
˜
ao de m
´
etodos de poda baseados em localidade 17
menores do que os valores obtidos na cole¸c˜ao WBR. Consultas por frase n˜ao foram experi-
mentadas na cole¸c˜ao LAT pois a maioria delas resultou em respostas vazias ou com poucas
respostas.
4.2 Cen´arios alternativos
Os resultados obtidos com os experimentos feitos por Santos [11] levantaram alguns questiona-
mentos sobre os m´etodos de poda utilizados e sobre propriedades das duas cole¸c˜oes utilizadas nos
experimentos. No intuito de tentar responder alguns destes questionamentos novos experimentos
foram realizados aqui considerando os seguintes cen´arios:
4.2.1 Apenas texto dos documentos
M´etodos de poda est´atica de ´ındices, por defini¸c˜ao, descartam entradas das listas invertidas em
disco para acelerar o processamento das consultas. Nos experimentos iniciais estes m´etodos de
poda foram aplicados `as listas invertidas dos termos dos documentos, e devido a isso a perda
na qualidade das respostas foi observada na similaridade vetorial do texto dos documentos. No
entanto, como a fun¸c˜ao de ordena¸c˜ao de respostas utilizada leva em considera¸c˜ao tamb´em a con-
catena¸c˜ao dos textos de ˆancora dos documentos e a autoridade de cada documento para produzir
a similaridade final, documentos da resposta que seriam perdidos devido `a poda est´atica podem
ter sido retornados atrav´es destas outras evidˆencias. Portanto, os experimentos iniciais feitos
com a fun¸c˜ao combinada de ordena¸c˜ao de respostas foram repetidos utilizando apenas a simi-
laridade vetorial (fun¸c˜ao 5 da Se¸c˜ao 3.3), para que se pudesse avaliar melhor o impacto isolado
dos m´etodos de poda nas respostas das consultas e tornar os experimentos mais abrangentes.
A Figura 4.1 mostra os resultados para a cole¸c˜ao WBR em um conjunto de consultas disjun-
tivas selecionadas aleatoriamente utilizando apenas a evidˆencia textual. A similaridade obtida
em todos os m´etodos foi superior a 0.75, o que indica que as respostas n˜ao mudam muito de
m´etodo para m´etodo. Este resultado era esperado para consultas disjuntivas, pois a probabili-
dade de conservar ao menos um dos termos da consulta no documento depois da poda ´e maior
do que a probabilidade de conservar todos os termos.
A Figura 4.2 mostra os resultados obtidos na cole¸c˜ao WBR com consultas conjuntivas uti-
lizando apenas a evidˆencia vetorial, lembrando que as consultas conjuntivas representam o tipo
4. Validac¸
˜
ao de m
´
etodos de poda baseados em localidade 18
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
50 55 60 65 70 75 80 85 90 95 100
Similaridade
Poda (%)
lbpm
full coverage
top fragments
random
carmel
Figura 4.1: Similaridade das respostas usando Kendall’s tau obtidas pelos m´etodos LBPM, Full
Coverage, Top Fragments, Random e Carmel na cole¸c˜ao WBR usando consultas disjuntivas.
mais popular de consulta. Neste caso, as conclus˜oes foram praticamente as mesmas obtidas com
os experimentos iniciais: todos os m´etodos baseados em localidade atingiram resultados ligeira-
mente melhores que o m´etodo de Carmel, sendo importante observar que mesmo as estrat´egias
baseadas em localidade mais simples, como Top Fragments e Random, atingiram resultados
competitivos. Outra observa¸c˜ao ´e que os m´etodos Full Coverage e LBPM possuem uma perfor-
mance bem similar quando se usa apenas a evidˆencia textual, o que se deve a similaridade entre
os algoritmos de sele¸c˜ao do m´etodo Full Coverage e o modelo vetorial adotado na ordena¸c˜ao das
respostas.
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
50 55 60 65 70 75 80 85 90 95 100
Similaridade
Poda (%)
lbpm
full coverage
top fragments
random
carmel
Figura 4.2: Similaridade das respostas usando Kendall’s tau obtidas pelos m´etodos LBPM, Full
Coverage, Top Fragments, Random e Carmel na cole¸c˜ao WBR usando consultas conjuntivas.
4. Validac¸
˜
ao de m
´
etodos de poda baseados em localidade 19
Na Figura 4.3 temos os resultados obtidos com consultas por frase para a cole¸c˜ao WBR,
novamente utilizando apenas a evidˆencia textual. Neste caso, tanto o ´ındice posicional quando o
de frequˆencia s˜ao podados e inclu´ıdos nos experimentos. Os resultados s˜ao bem parecidos com o
resultados obtidos nos experimentos iniciais, assim como ocorreu com as consultas conjuntivas,
com os m´etodos baseados em localidade obtendo resultados bem pr´oximos entre si. Os resultados
obtidos pelo m´etodo de Carmel nesse caso eram esperados, pois este n˜ao foi desenvolvido para
a poda de ´ındices posicionais.
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
50 55 60 65 70 75 80 85 90 95 100
Similaridade
Poda (%)
lbpm
full coverage
top fragments
random
carmel
Figura 4.3: Similaridade das respostas usando Kendall’s tau obtidas pelos m´etodos LBPM, Full
Coverage, Top Fragments, Random e Carmel na cole¸c˜ao WBR usando consultas por frase.
4.2.2 Amostras da cole¸c˜ao WBR
Um destes questionamentos trata da diferen¸ca entre os valores absolutos de similaridade entre
listas obtidos nas duas cole¸c˜oes, pois observou-se que os valores obtidos na cole¸c˜ao LAT s˜ao em
geral menores do que os obtidos na cole¸c˜ao WBR. Uma das raz˜oes para esta diferen¸ca ´e que
a cole¸c˜ao LAT n˜ao possui documentos atˆomicos, fazendo com que todos os documentos sejam
afetados pelos m´etodos de poda. Outra raz˜ao ´e que muitos termos nas consultas da cole¸c˜ao
LAT possuem listas invertidas muito curtas, ou seja, s˜ao termos raros, ao contr´ario dos termos
encontrados no log de consultas da cole¸c˜ao WBR.
Uma outra raz˜ao para a diferen¸ca nos resultados poderia ser a disparidade no tamanho das
cole¸c˜oes. Foram criadas trˆes amostras aleat´orias da cole¸c˜ao WBR com o mesmo tamanho da
cole¸c˜ao LAT, e os experimentos foram repetidos nessas amostras utilizando apenas a evidˆencia
4. Validac¸
˜
ao de m
´
etodos de poda baseados em localidade 20
textual. Em rela¸c˜ao ao desempenho relativo dos m´etodos experimentados, as conclus˜oes foram
exatamente as mesmas obtidas para a cole¸c˜ao WBR completa, com o m´etodo de Carmel sendo
o melhor para consultas disjuntivas e os m´etodos baseados em localidade sendo melhores para
consultas conjuntivas e por frase. Por exemplo, utilizando um nivel de poda de 50%, o m´etodo
LBPM atingiu uma similaridade m´edia de 0.48 para consultas conjuntivas, 0.88 para consultas
disjuntivas e 0.57 para consultas por frase, enquanto que o m´etodo de Carmel atingiu 0.28
para consultas conjuntivas, 0.97 para consultas disjuntivas e 0.31 para consultas por frase. No
entanto, assim como na cole¸c˜ao LAT, os valores absolutos da similaridade de Kendall’s tau s˜ao
tamb´em menores do que na cole¸c˜ao WBR, o que sugere que o tamanho da cole¸c˜ao pode tamb´em
afetar a qualidade da poda est´atica.
4.2.3 Remo¸c˜ao de termos raros
Outros experimentos foram feitos usando a cole¸c˜ao LAT removendo termos raros e os resulta-
dos gerais obtidos foram ligeiramente melhores para todos os m´etodos, especialmente para os
m´etodos baseados em localidade. Por exemplo, removendo as consultas com termos que ocor-
rem em menos de 200 posi¸c˜oes, os resultados comparativos foram bem pr´oximos aos obtidos
utilizando a cole¸c˜ao WBR, com os m´etodos baseados em localidade sendo ligeiramente melhores
para consultas conjuntivas e ligeiramente piores para consultas disjuntivas. Este comportamento
´e uma consequˆencia de como o m´etodo de Carmel faz a poda das listas invertidas de termos
raros, preservando suas entradas, enquanto que o m´etodo LBPM e os outros baseados em local-
idade tendem a podar mais entradas das listas destes termos. Por exemplo, enquanto com um
n´ıvel de poda em torno de 70% o m´etodo de Carmel mant´em 96.5% das entradas para termos
com menos de 200 itens, o m´etodo LBPM mant´em apenas 46% destas entradas. A remo¸c˜ao de
termos raros com menos de 200 ocorrˆencias das amostras da cole¸c˜ao WBR n˜ao mudou os resul-
tados relativos, mas da mesma forma os maiores ganhos foram obtidos pelos m´etodos baseados
em localidade.
Estes resultados sugerem que os m´etodos baseados em localidade podem ser competitivos
mesmo para cole¸c˜oes semelhantes a LAT se o processamento de termos raros for feito como um
caso especial. Esta estrat´egia n˜ao causaria uma perda significativa na compress˜ao, pois estes
termos possuem listas invertidas curtas.
4. Validac¸
˜
ao de m
´
etodos de poda baseados em localidade 21
4.3 Precis˜ao em 5 e precis˜ao em 10
Uma importante m´etrica de qualidade para m´aquinas de busca ´e a precis˜ao dos m´etodos nos
resultados do topo. A Figura 4.4 mostra o desempenho dos m´etodos considerando os resultados
de P@10 (a) e P@5 (b). Aplicando m´etodos de significˆancia os resultados podem ser considerados
empate para todos os m´etodos, exceto para o m´etodo de Carmel em todos os n´ıveis de compress˜ao
maiores do que 70% nos dois casos. Outra observa¸c˜ao importante ´e que todos os m´etodos
baseados em localidade produzem resultados pr´oximos ao sistema sem poda. Por exemplo, a
diferen¸ca relativa entre o sistema sem poda e o sistema podado com um n´ıvel de 80% com o
m´etodo Top Fragments ´e menor que 2% em P@10.
30
35
40
45
50
55
0 10 20 30 40 50 60 70 80 90 100
Precisao a 10
Compressao (%)
lbpm
full coverage
top fragments
random
carmel
(a) precis˜ao @10
30
35
40
45
50
55
0 10 20 30 40 50 60 70 80 90 100
Precisao em 5
Compressao (%)
lbpm
full coverage
top fragments
random
carmel
(b) precis˜ao @5
Figura 4.4: P@10 (a) e P@5 (b) obtidos processando consultas com ´ındices podados pelos
m´etodos LBPM, Full Coverage, Top Fragments, Random e Carmel com diferentes n´ıveis de
poda.
4. Validac¸
˜
ao de m
´
etodos de poda baseados em localidade 22
Estes experimentos refor¸cam que os resultados obtidos com m´etodos baseados em locali-
dade s˜ao extremamente competitivos. Os valores de precis˜ao obtidos s˜ao ligeiramente melhores
para o m´etodo Top Fragments, indicando que pode ser melhor preservar as passagens do topo
quando comparado com a heur´ıstica Random. Resultados anteriores com m´etodos de suma-
riza¸c˜ao tamb´em indicaram que selecionar as senten¸cas do topo de um texto pode ser uma boa
estrat´egia para capturar os termos mais importantes do texto, pois os autores tendem a apre-
sentar as id´eias principais do texto nas primeiras senten¸cas[15, 12].
Cap´ıtulo 5
´
Indice em camadas para poda
dinˆamica
5.1 Vis˜ao geral
Um dos problemas observados com m´etodos de poda est´atica ´e a rela¸c˜ao custo-benef´ıcio entre o
n´ıvel de compress˜ao e a qualidade dos resultados das consultas, pois quanto maior a compress˜ao
aplicada menor ´e a qualidade de resultados obtidos. Como observado por Moura et al. [9],
diferentes tipos de consulta podem precisar de n´ıveis de compress˜ao diferentes para que obten-
ham um resultado adequado. Por exemplo, consultas disjuntivas (OR) podem ser processadas
com ´ındices bastante comprimidos, enquanto consultas conjuntivas (AND) precisam de ´ındices
com n´ıvel de compress˜ao menor para que sejam obtidos resultados satisfat´orios. M´etodos de
poda dinˆamica, por sua vez, visam finalizar o processamento da consulta o mais cedo poss´ıvel,
e por esse motivo tamb´em apresentar˜ao perdas de qualidade dependendo do crit´erio de parada
utilizado. De maneira semelhante ao que acontece com a poda est´atica, tipos diferentes de
consultas poder˜ao precisar de crit´erios de parada diferentes para que obtenham um resultado
aceit´avel.
Neste cap´ıtulo ser´a proposta uma estrutura de ´ındice adaptada para poda dinˆamica, denom-
inada ´ındice em camadas, que ´e constru´ıda atrav´es da aplica¸c˜ao de m´etodos de poda est´atica
baseados em localidade para reorganizar o ´ındice nestas camadas. Com base neste ´ındice, ser´a
proposto um m´etodo de poda dinˆamica que poder´a utilizar estrat´egias diversas para determinar
quais por¸c˜oes deste ´ındice em camadas dever˜ao ser processadas para atender satisfatoriamente
23
5.
´
Indice em camadas para poda din
ˆ
amica 24
a uma consulta. Estas estrat´egias poder˜ao utilizar v´arias evidˆencias dispon´ıveis, como o tipo
da consulta (conjuntiva, disjuntiva, por frase), objetivo (informacional, navegacional, transa-
cional), raridade do termo (idf ), dentre outras a serem estudadas, ou podem ainda ser uti-
lizadas estat´ısticas coletadas durante o processamento da consulta. A utiliza¸c˜ao deste ´ındice
em camadas juntamente com uma estrat´egia de poda dinˆamica visa combinar as vantagens das
duas abordagens para poda de ´ındices: a divis˜ao em camadas simplifica o processamento das
listas invertidas, pois apenas o n´umero de camadas ´e necess´ario para deteminar quais por¸c˜oes
devem ser lidas, e cada consulta poder´a ser processada de maneira diferenciada de acordo com
suas caracter´ısticas.
A Figura 5.1 ilustra a id´eia de organiza¸c˜ao do ´ındice em camadas. Nesta figura temos as
listas invertidas dos termos t
i
, t
j
e t
k
, e pode-se observar que o tamanho das camadas das listas
invertidas n˜ao ´e o mesmo para todos os termos, podendo variar dependendo do tamanho da lista
e dos documentos onde este termo ocorre. O termo t
i
n˜ao possui nenhuma entrada na ´ultima
camada, e por isso as camadas c
9
e c
10
coincidem.
Figura 5.1: Divis˜ao das listas invertidas em camadas
Como as camadas com menores n´ıveis de compress˜ao contˆem as camadas com maiores n´ıveis,
elimina-se a redundˆancia de entradas presente em podas est´aticas com n´ıveis diferentes de com-
press˜ao, tornando o ´ındice em camadas uma representa¸c˜ao eficiente
1
de v´arias podas est´aticas
do mesmo ´ındice. Um exemplo disso ´e a camada c
2
, que ´e composta pelas entradas da camada
1
Em rela¸c˜ao ao espa¸co em disco utilizado pelo ´ındice.
5.
´
Indice em camadas para poda din
ˆ
amica 25
c
1
juntamente com entradas adicionais.
5.2 Constru¸c˜ao do ´ındice em camadas
Em um indexador padr˜ao, as listas invertidas s˜ao geradas inicialmente como listas tempor´arias,
que s˜ao preenchidas at´e o limite da mem´oria dispon´ıvel e despejadas em disco, e posteriormente
´e feita a intercala¸c˜ao dessas listas tempor´arias para a gera¸c˜ao das listas invertidas finais[2]. As
listas tempor´arias s˜ao compostas por triplas que possuem, no sistema de busca utilizado para
os experimentos, o formato (id termo, id documento, posi¸c˜ao). Para o ´ındice em camadas, a
primeira altera¸c˜ao foi adicionar a informa¸c˜ao da camada onde esta entrada se encontra a estas
triplas, resultando em qu´adruplas no formato (id termo, id documento, posi¸c˜ao, camada). Desta
forma, na fase de intercala¸c˜ao destas listas tempor´arias para a gera¸c˜ao das listas invertidas finais,
basta que o crit´erio de ordena¸c˜ao das qu´adruplas (antigas triplas) seja modificado para levar em
considera¸c˜ao a informa¸c˜ao da camada, formando estas no interior de cada lista.
Para a determina¸c˜ao da camada a qual pertence cada entrada das listas invertidas, ´e utilizado
um m´etodo de poda est´atica integrado ao indexador, na fun¸c˜ao de gera¸c˜ao das listas tempor´arias.
S˜ao utilizados C −1 n´ıveis de compress˜ao decrescentes, onde C ´e o n´umero de camadas desejado,
e os n´ıveis de compress˜ao s˜ao determinados como
100 −
i ×
100
C

%, onde i ´e o n´umero da
camada. Como exemplo, supondo C = 5, para as camadas c
1
, c
2
, c
3
e c
4
os n´ıveis de compress˜ao
ser˜ao respectivamente 80%, 60%, 40% e 20%. A camada c
5
ser´a composta pelas entradas que
n˜ao fizerem parte de nenhuma camada, equivalendo a lista invertida completa (compress˜ao de
0%). Em um primeiro momento o n´ıvel m´aximo de compress˜ao ´e aplicado, 80%, e as passagens
obtidas com este n´ıvel ser˜ao indexadas na primeira camada do ´ındice; em seguida, ao inv´es de
repetir o processo integralmente, novas passagens s˜ao adicionadas ao fragmento de 80% at´e que
o n´ıvel de compress˜ao alcance 60%, e estas novas passagens ser˜ao indexadas na segunda camada.
O processo segue at´e o menor n´ıvel de compress˜ao, 20% no caso, e ap´os a aplica¸c˜ao deste as
passagens que restarem no documento ser˜ao indexadas como parte da ´ultima camada, c
5
. Se
todas as passagens forem selecionadas antes que todos os n´ıveis de compress˜ao sejam utilizados,
as camadas seguintes ser˜ao mapeadas para a camada corrente. Seguindo o exemplo atual, se
todas as passagens de um documento forem selecionadas na compress˜ao de 40% (c
3
), c
4
e c
5
seriam mapeadas para a mesma posi¸c˜ao de c
3
.
5.
´
Indice em camadas para poda din
ˆ
amica 26
´
E necess´ario tamb´em alterar o processador de consultas para que este possa levar em con-
sidera¸c˜ao as camadas e aplicar os crit´erios de poda. O processamento das consultas ´e feito
utilizando-se uma camada de cada vez, e no final de cada camada ´e aplicado um crit´erio para
determinar se a pr´oxima camada dever´a ser processada. Este crit´erio pode utilizar informa¸c˜oes
diversas, como exemplificado na Se¸c˜ao 5.1, sendo poss´ıvel que cada consulta utilize um con-
junto diferenciado de informa¸c˜oes para determinar quais camadas processar, resultando em um
m´etodo de poda dinˆamica adapt´avel a cada consulta submetida.
5.3 Avalia¸c˜ao de resultados
Os experimentos com o ´ındice em camadas e o m´etodo de poda dinˆamica descritos nesta dis-
serta¸c˜ao foram realizados com o intuito de fazer uma compara¸c˜ao com os experimentos com
m´etodos de poda est´atica baseados em localidade, al´em de verificar a efic´acia de uma estrat´egia
proposta para sele¸c˜ao das camadas a serem processadas: a similaridade entre o topo da resposta
obtida com a camada anterior e o topo da resposta obtida com a camada atual. Nestes experi-
mentos foi utilizado o m´etodo de poda est´atica Top Fragments para a reorganiza¸c˜ao dos ´ındices,
devido `a sua facilidade de implementa¸c˜ao e resultados pr´oximos aos m´etodos mais sofistica-
dos, como mostrado no Cap´ıtulo 4. Por raz˜oes operacionais
2
, foram utilizadas duas vers˜oes da
cole¸c˜ao WBR: a vers˜ao utilizada no Cap´ıtulo 4, que ser´a referenciada como WBR10, e uma
vers˜ao mais atual com aproximadamente 12 milh˜oes de documentos e coletada em 2003, que
ser´a denominada WBR12.
5.3.1 N´umero de camadas processadas
O objetivo deste experimento ´e verificar se os resultados obtidos com o ´ındice em camadas
proposto neste cap´ıtulo s˜ao equivalentes aos resultados obtidos com m´etodos de poda est´atica,
utilizando como crit´erio de parada o processamento de n camadas (n < 20) onde n ´e passado
juntamente com a consulta.
A Figura 5.2 mostra resultados obtidos com consultas disjuntivas e conjuntivas na cole¸c˜ao
WBR10, usando apenas a similaridade vetorial do texto. Estes resultados possuem comporta-
mento semelhante aos obtidos no cap´ıtulo anterior para o m´etodo Top Fragments nas Figuras
2
A cole¸c˜ao WBR utilizada no Cap´ıtulo 4 n˜ao se encontra mais dispon´ıvel integralmente, permitindo apenas
a utiliza¸c˜ao da evidˆencia vetorial do texto dos documentos.
5.
´
Indice em camadas para poda din
ˆ
amica 27
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 10 20 30 40 50 60 70 80 90 100
Similaridade
Compressao (%)
conjuntivas
disjuntivas
Figura 5.2: Similaridade m´edia de consultas disjuntivas e conjuntivas usando o n´umero de
camadas como crit´erio de parada
4.1 e 4.2 a partir de 50% de compress˜ao, indicando que o ´ındice em camadas poderia ser utilizado
da mesma forma que uma poda est´atica do ´ındice e demonstrando a id´eia de que o ´ındice em
camadas equivale a uma representa¸c˜ao condensada de v´arias podas est´aticas do mesmo ´ındice.
5.3.2 Distˆancia de listas entre camadas
Neste experimento ser´a avaliado um dos crit´erios para escolha autom´atica das camadas a serem
processadas. O crit´erio em quest˜ao ´e a similaridade entre o topo do resultado obtido com a
camada anterior com o topo do resultado obtido com a camada atual, utilizando o m´etodo
Kendall’s tau para determinar tal similaridade, da mesma forma como feito com os resultados
finais das consultas. Em outras palavras, as camadas ser˜ao processadas at´e que haja uma
determinada convergˆencia do topo dos resultados obtidos, ponto a partir do qual ser´a considerado
que as pr´oximas camadas ter˜ao pouca ou nenhuma influˆencia na ordena¸c˜ao dos resultados. Uma
implica¸c˜ao deste crit´erio ´e que ao menos duas camadas ser˜ao processadas, ou seja, n˜ao ´e poss´ıvel
atingir a compress˜ao m´axima. Ser˜ao mostrados resultados obtidos com as cole¸c˜oes WBR10,
utilizando a fun¸c˜ao 5 (similaridade vetorial do texto) e WBR12, utilizando fun¸c˜oes espec´ıficas
para os 3 tipos de consulta. Foram utilizados limiares variando de 0.8 at´e 1.0, em incrementos
de 0.01.
Na Figura 5.3c temos a similaridade para consultas disjuntivas e conjuntivas na cole¸c˜ao
WBR10, utilizando como crit´erio de parada a distˆancia de listas entre os resultados parciais
obtidos com cada camada. Assim como nos resultados obtidos com a poda est´atica, consultas
5.
´
Indice em camadas para poda din
ˆ
amica 28
disjuntivas obtˆem um resultado bem alto independente do limiar utilizado, sendo ligeiramente
melhores para a poda dinˆamica. Os resultados para consultas conjuntivas foram ligeiramente
melhores do que os obtidos com a poda est´atica, a exemplo do que houve com as consultas
disjuntivas. Uma compara¸c˜ao entre os dois tipos de poda ´e feito mais a frente na Figura5.5.
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1
Similaridade
Limiar
conjuntivas
disjuntivas
0
10
20
30
40
50
60
70
80
90
100
0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1
Nivel de poda (%)
Limiar
conjuntivas
disjuntivas
(a) Similaridade × limiar (b) N´ıvel de poda × limiar
(c) Similaridade × n´ıvel de poda
Figura 5.3: Gr´aficos para poda dinˆamica na cole¸c˜ao WBR10: (a) Similaridade m´edia e (b) n´ıvel
de poda obtidos em fun¸c˜ao do limiar utilizado para a distˆancia de listas entre os resultados
obtidos entre camadas; (c) Similaridade m´edia em fun¸c˜ao do n´ıvel de poda.
Nas Figuras 5.3a e 5.3b pode-se observar a influˆencia do limiar utilizado para a distˆancia
de listas entre camadas tanto na similaridade das respostas quanto no n´ıvel de poda obtido.
Nota-se que os valores de similaridade tendem a subir a medida que o limiar aumenta, enquanto
que os n´ıveis de poda tendem a cair. O limiar 0.96 pode ser considerado um ponto ´otimo neste
caso, pois neste ponto os n´ıveis de poda ainda n˜ao apresentam uma grande queda e os valores
de similaridade aumentaram numa propor¸c˜ao ligeiramente maior. Deste ponto em diante os
n´ıveis de poda caem de maneira mais acentuada, se aproximando de 0% e tornando o ganho de
desempenho no processamento da consulta desprez´ıvel.
5.
´
Indice em camadas para poda din
ˆ
amica 29
A Figura 5.4c mostra os resultados obtidos com consultas conjuntivas, informacionais e
navegacionais na cole¸c˜ao WBR12. Os melhores resultados foram obtidos com consultas nave-
gacionais, o que pode ser devido `a maior influˆencia que o texto de ˆancora possui neste tipo de
consulta, possibilitando utilizar n´ıveis de poda maiores sem grandes perdas no resultado.
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1
Similaridade
Limiar
informacionais
navegacionais
conjuntivas
0
10
20
30
40
50
60
70
80
90
100
0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1
Nivel de poda (%)
Limiar
informacionais
navegacionais
conjuntivas
(a) Similaridade × limiar (b) N´ıvel de poda × limiar
(c) Similaridade × n´ıvel de poda
Figura 5.4: Gr´aficos para poda dinˆamica na cole¸c˜ao WBR12: (a) Similaridade m´edia e (b) n´ıvel
de poda obtidos em fun¸c˜ao do limiar utilizado para a distˆancia de listas entre os resultados
obtidos entre camadas; (c) Similaridade m´edia em fun¸c˜ao do n´ıvel de poda.
A influˆencia do limiar utilizado na similaridade das respostas e no n´ıvel de poda na cole¸c˜ao
WBR12 ´e mostrada respectivamente nas Figuras 5.4a e 5.4b. O comportamento destes dois
gr´aficos ´e semelhante ao observado na cole¸c˜ao WBR10, sendo tamb´em o limiar 0.96 ´otimo neste
caso.
As Figuras 5.5 e 5.6 mostram as compara¸c˜oes entre poda est´atica e dinˆamica nas cole¸c˜oes
utilizadas nos experimentos. Pode-se observar nestas figuras que os valores obtidos com as duas
cole¸c˜oes s˜ao bem pr´oximos entre si, mesmo com um aumento de 20% no tamanho e uma diferen¸ca
de 4 anos entre as cole¸c˜oes WBR10 (1999) e WBR12 (2003). Este resultado demonstra que os
5.
´
Indice em camadas para poda din
ˆ
amica 30
(a) Conjuntivas (b) Disjuntivas
Figura 5.5: Compara¸c˜ao dos resultados para entre est´atica e dinˆamica obtidos na cole¸c˜ao WBR10
com consultas disjuntivas e conjuntivas
(a) Informacionais (b) Navegacionais
(c) Conjuntivas
Figura 5.6: Compara¸c˜ao dos resultados obtidos entre poda est´atica e dinˆamica na cole¸c˜ao
WBR12 com consultas informacionais, navegacionais e conjuntivas
5.
´
Indice em camadas para poda din
ˆ
amica 31
m´etodos de poda baseados em localidade mant´em a sua efic´acia mesmo quando as cole¸c˜oes s˜ao
atualizadas, uma caracter´ıstica essencial para a utiliza¸c˜ao destes m´etodos em cole¸c˜oes Web.
Outro ponto a ser observado nestas figuras ´e que, nos experimentos realizados, a poda
dinˆamica n˜ao atingiu os mesmos n´ıveis de poda obtidos pela poda est´atica. Uma poss´ıvel
explica¸c˜ao para esse fato est´a relacionada aos valores dos limiares utilizados na similaridade
das respostas entre camadas, que variaram de 0.8 at´e 1.0. Limiares menores possivelmente
resultariam em n´ıveis de poda mais altos, mas n˜ao foram utilizados pois a similaridade m´edia
com o menor limiar experimentado n˜ao foi muito satisfat´oria, possivelmente tendendo a degradar
mais ainda com a diminui¸c˜ao do limiar.
5.3.3 Desvio padr˜ao dos resultados
A avalia¸c˜ao dos resultados ´e feita atrav´es da similaridade m´edia do resultado das consultas com
o resultado original. Uma caracter´ıstica inerente a m´edia ´e que resultados pr´oximos entre si
podem resultar na mesma m´edia que resultados bastante d´ıspares. Torna-se interessante, ent˜ao,
conhecer tamb´em a dispers˜ao dos valores dos resultados para um melhor entendimento destes,
sendo uma maneira de quantificar tal dispers˜ao o desvio padr˜ao. As compara¸c˜oes da similaridade
m´edia e desvio padr˜ao entre poda est´atica e dinˆamica foram feitas com o maior n´ıvel de poda
onde foi poss´ıvel fazer uma compara¸c˜ao direta entre os dois tipos. As duas t´ecnicas de poda
foram avaliadas em pontos discretos, e buscamos a combina¸c˜ao de pontos onde os percentuais
de poda foram coincidentes para facilitar a compara¸c˜ao.
N´ıvel de poda Tipo das consultas Tipo da poda M´edia Desvio padr˜ao
35% Disjuntivas Est´atica 0.9265 0.1195
Dinˆamica 0.9686 0.0621
16% Conjuntivas Est´atica 0.6046 0.3332
Dinˆamica 0.6804 0.2852
Tabela 5.1: Desvio padr˜ao da similaridade m´edia na cole¸c˜ao WBR10 nos n´ıveis de poda especi-
ficados
As Tabelas 5.1 e 5.2 mostram a m´edia e o desvio padr˜ao da similaridade das respostas, nos
n´ıveis de poda especificados. Em todos os casos o desvio padr˜ao foi ligeiramente menor para a
poda dinˆamica, mesmo nos casos onde a m´edia foi menor do que a obtida com a poda est´atica,
indicando que os resultados obtidos com esta foram mais pr´oximos da m´edia e portanto mais
5.
´
Indice em camadas para poda din
ˆ
amica 32
N´ıvel de poda Tipo das consultas Tipo da poda M´edia Desvio padr˜ao
25% Conjuntivas Est´atica 0.5004 0.3052
Dinˆamica 0.5196 0.2917
25% Informacionais Est´atica 0.5802 0.3145
Dinˆamica 0.5752 0.2749
28% Navegacionais Est´atica 0.7248 0.2537
Dinˆamica 0.7111 0.2318
Tabela 5.2: Desvio padr˜ao da similaridade m´edia na cole¸c˜ao WBR12 nos n´ıveis de poda especi-
ficados
est´aveis. Esta estabilidade ´e desej´avel pois torna mais consistente a experiˆencia do usu´ario com
o sistema de busca, aumentando a aceita¸c˜ao deste.
Cap´ıtulo 6
Conclus˜oes e trabalhos futuros
Nesta disserta¸c˜ao foi feito um estudo sobre a aplica¸c˜ao da localidade em m´etodos de poda
de ´ındices, demonstrando a efic´acia de m´etodos de poda est´atica e dinˆamica em cole¸c˜oes Web.
Quatro m´etodos de poda baseados em localidade foram avaliados no Cap´ıtulo 4 em trˆes diferentes
cen´arios, al´em de uma medi¸c˜ao da precis˜ao dos documentos do topo das respostas, e os resultados
obtidos demonstraram que a utiliza¸c˜ao da localidade como heur´ıstica para poda de ´ındices
continua eficaz mesmo utilizando-se apenas a evidˆencia vetorial do texto para a ordena¸c˜ao das
respostas. Foram verificadas tamb´em algumas caracter´ısticas que pudessem explicar a diferen¸ca
nos resultados obtidos com uma cole¸c˜ao convencional (LAT) e com uma cole¸c˜ao Web (WBR), e
observou-se que o tamanho da cole¸c˜ao e a raridade dos termos das consultas poderiam influenciar
na qualidade dos resultados dos m´etodos de poda estudados.
O ´ındice reorganizado em camadas proposto no Cap´ıtulo 5 pode ser utilizado tanto como
uma representa¸c˜ao condensada de v´arias podas est´aticas, como demonstrado nos experimentos,
quanto como base para a utiliza¸c˜ao do m´etodo de poda dinˆamica baseado em localidade proposto.
Este m´etodo, embora obtendo similaridades m´edias pr´oximas `as obtidas com a poda est´atica
nos experimentos, obteve desvio padr˜ao dos resultados ligeiramente menor, indicando que os
valores dos resultados foram mais pr´oximos da m´edia e portanto mais est´aveis. V´arios aspectos
deste m´etodo de poda poder˜ao ser explorados em trabalhos futuros, inclusive com a utiliza¸c˜ao
de outras cole¸c˜oes Web conhecidas, como a WT10g
1
e a GOV2
2
.
Uma proposta para a melhoria do m´etodo de poda dinˆamica proposto ´e a utiliza¸c˜ao de outros
1
http://linkinghub.elsevier.com/retrieve/pii/S0306457302000845
2
http://ir.dcs.gla.ac.uk/test collections/gov2-summary.htm
33
6. Conclus
˜
oes e trabalhos futuros 34
crit´erios para a sele¸c˜ao de camadas a serem processadas, em especial a utiliza¸c˜ao de t´ecnicas
de aprendizagem de m´aquina para fazer a combina¸c˜ao das evidˆencias da consulta e dos termos
para tal sele¸c˜ao, tais como classificadores SVM[8] ou algoritmos gen´eticos. Outra melhoria a
ser estudada ´e a utiliza¸c˜ao de novas evidˆencias extra´ıdas da consulta, dos termos da consulta
ou durante o processamento desta. Em rela¸c˜ao ao ´ındice em camadas, outra possibilidade a ser
explorada ´e a utiliza¸c˜ao de outros m´etodos de poda est´atica para a reorganiza¸c˜ao do´ındice, como
por exemplo os m´etodos LBPM e Full Coverage, que possuem diferentes crit´erios de sele¸c˜ao de
passagens e poder˜ao resultar em uma reorganiza¸c˜ao mais eficaz das listas invertidas. Pode-se
tamb´em variar a maneira de dividir o documento em passagens, utilizando outros crit´erios como
a divis˜ao em par´agrafos ou janelas (passagens com n´umero fixo de termos).
Referˆencias Bibliogr´aficas
[1] Vo Ngoc Anh and Alistair Moffat. Pruned query evaluation using pre-computed impacts.
In SIGIR ’06: Proceedings of the 29th annual international ACM SIGIR conference on
Research and development in information retrieval, pages 372–379, New York, NY, USA,
2006. ACM Press.
[2] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, 1999.
[3] R. Brandow, K. Mitze, and L. F. Raul. Automatic condensation of electonic publications
by sentence selection. Information Processing and Management, 31(5):675–685, 1995.
[4] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search
engine. In Proceedings of the 7th International World Wide Web Conference, pages 107–
117, April 1998.
[5] Andrei Broder. A taxonomy of web search. SIGIR Forum, 36(2):3–10, 2002.
[6] P´avel Pereira Calado, E. S. de Moura, Berthier Ribeiro-Neto, Ilm´erio Silva, and Nivio
Ziviani. Local versus global link information in the web. ACM Transactions on Information
Systems (TOIS), 21(1):42–63, 2003.
[7] D. Carmel, D. Cohen, R. Fagin, E. Farchi, M. Herscovici, Y. S. Maarek, and A. Soffer. Static
index pruning for information retrieval systems. In Proceedings of the 24th Annual Inter-
national ACM SIGIR Conference on Research and Development in Information Retrieval,
pages 43–50, New Orleans, Louisiana, USA, September 2001.
[8] Nello Cristianini and John Shawe-Taylor. An introduction to support Vector Machines:
and other kernel-based learning methods. Cambridge University Press, New York, NY,
USA, 2000.
35
6. Conclus
˜
oes e trabalhos futuros 36
[9] Edleno S. de Moura, C´elia F. dos Santos, Daniel R. Fernandes, Altigran S. Silva, Pavel Cal-
ado, and M´ario A. Nascimento. Improving web search efficiency via a locality based static
pruning method. In Proceedings of the 14th International World Wide Web Conference,
pages 235–244, Chiba, Japan, Maio 2005.
[10] Edleno Silva de Moura, Celia Francisca dos Santos, Bruno dos Santos de Ara´ujo, Alti-
gran Soares da Silva, Pavel Calado, and Mario A. Nascimento. Locality-based pruning
methods for web search. ACM Trans. Inf. Syst., 26(2):1–28, 2008.
[11] C´elia Francisca dos Santos. M´etodos de Poda Est´atica para
´
Indices de M´aquinas de Busca.
Disserta¸c˜ao de mestrado, Universidade Federal do Amazonas, 2006.
[12] H. P. Edmundson. New methods in automatic extraction. Journal of the ACM, 16(2):264–
285, 1968.
[13] R. Fagin, R. Kumar, and D. Sivakumar. Comparing top k lists. In Proceedings of the
fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 28–36, 2003.
[14] D. Hawking, E. Voorhees, P. Bailey, and N. Craswell. Overview of trec-8 web track. In
Proc. of TREC-8, pages 131–150, Gaithersburg MD, November 1999.
[15] E. H. Hovy and C-Y Lin. Automated Text Summarization in SUMMARIST, chapter Intel-
ligent Scalable Summarization Text Summarization, pages 81–94. Mit press, 1998.
[16] Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings
of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 668–677, San
Francisco, California, USA, January 1998.
[17] Daniel Mallett, James Elding, and Mario A. Nascimento. Information-content based sen-
tence extraction for text summarization. In ITCC ’04: Proceedings of the International
Conference on Information Technology: Coding and Computing (ITCC’04) Volume 2, page
214. IEEE Computer Society, 2004.
[18] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation
ranking: Bringing order to the Web. Technical report, Stanford Digital Library Technologies
Project, 1998.
6. Conclus
˜
oes e trabalhos futuros 37
[19] Michael Persin. Document filtering for fast ranking. In Proceedings of the 17th Annual
International ACM-SIGIR Conference on Research and Development in Information Re-
trieval. Dublin, Ireland, 3-6 July 1994 (Special Issue of the SIGIR Forum), pages 339–348,
1994.
[20] Andrew Rosenbloom. The blogosphere: Introduction. Communications of the ACM,
47(12):30–33, 2004.
[21] G. Salton, A. Wong, and C. S. Yang. A vector space model for automatic indexing. Com-
mun. ACM, 18(11):613–620, 1975.
[22] Gerard Salton and M. J. McGill. Introduction to Modern Information Retrieval. McGraw-
Hill, 1st edition, 1983.
[23] Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing
and Indexing Documents and Images. Morgan Kaufmann Publishers, 2nd edition, 1999.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo