GHHITS – Mining the Web Link Structure

GHHITS – Mining the Web Link GHHITS – Mining the Web Link Structure Structure

Universidade Federal de Pernambuco Centro de Informática

Roberta CoelhoSilvio Meira

GHHITS – Minerando a Estrutura GHHITS – Minerando a Estrutura de Links da Webde Links da Web

Universidade Federal de Pernambuco Centro de Informática

Roberta CoelhoSilvio Meira

3

RoteiroRoteiro

• Motivação e Problema • Abordagem• Metodologia Empregada• Detalhamento da Solução• Contribuições para a Área e Originalidade do

Tema • Publicações Geradas

4

• Alternativa mais efetiva para se encontrar informações na Web: engenhos de busca

• Exemplo de uma arquitetura centralizada para um engenho de busca:

Crawler

Index

IndexingServer

Link Server

Crawler

Query Engine

Interface

Users

Crawler

Crawler-Indexer Module Search Module

Ranking

Metodologia DetalhamentoContribuições e

Originalidade PublicaçõesAbordagem

Motivação e Problema

5

Desafios enfrentados pelos engenhos de busca:

1. Desafio de Precisão (tópicos gerais)

• 85,2% dos usuários visualiza apenas a 1a. página resposta

2. Usuários inexperientes

• 70% das consultas: 1 termo

792.356


Originalidade PublicaçõesAbordagem

Motivação e Problema

6

• Algoritmos de busca textual: não associam o conceito de importância insuficientes ao processo de RI na Web.

.


Originalidade PublicaçõesMotivação e Problema Abordagem

• Links funcionais: Opinião coletiva dos usuários da Web.

• Algoritmos sendo desenvolvidos para explorar a estrutura de links da Web.

Documentos Web Documentos “flat” Hiperlinks: navegacionais,comerciais, funcionais

7

• Melhorar a eficácia de recuperação de um engenho de busca a partir da utilização da análise de links em conjunto a análise textual no momento do ranqueamento.


Originalidade PublicaçõesMotivação e Problema Abordagem

8

1. Estudo dos algoritmos de AL existentes.– PageRank (Google), HITS (IBM),CLEVER

Project (IBM), Web Archeology Research

(COMPAQ)

HITS - Hyperlink Induced Topic Search

• Autoridade uma pagina referenciada por

várias páginas é considerada “importante”.

• Hub uma página que aponta para muitas

páginas “importantes” (“Bookmark”).

a(i) = h (j) j B(i)

h(i) = a (j) i F (i) i

B(i)F(i)

Abordagem DetalhamentoContribuições e

Originalidade PublicaçõesMotivação e Problema Metodologia

9

2. Elaboração de um algoritmo de AL.

Algoritmo Proposto: Global Hybrid HITS (GHHITS)

• Pesos de Autoridade e Hub de cada página da Web indexada são pre-computados Off-line.

• Utiliza heurísticas de Limpeza (filtros de IP).

a(i) = h (j) * aut_wt(j,i) + InitAut(i) j B(i)

h(i) = a (j) * hub_wt(i,j) + InitHub(i) i F (i)

(CLEVER)

(PageRank)

(COMPAQ)



10

cod_pagina : peso_aut : peso_hub

<url _origem> |<link_destino_1> |...|<link_destino_n>

3. Implementação de um sistema para validação do algoritmo:- Armazenamento e análise de links

Ranking = a * TEXT + b*AUT



11

4. Elaboração de uma fórmula de ranqueamento para combinar:

o peso de IMPORTÂNCIA (AUT) o peso de provável RELEVÂNCIA (TEXT)




12

Objetivo do Experimento

Analisar o impacto na performance de recuperação em um EB que utiliza o peso de autoridade em conjunto com o textual.

Consultas TOP 100 consultas do Radix durante (Set. Out. e Nov 2001)

2 termos (11%)

1 termo (85%)

3 termos (4%)

5. Avaliar o impacto desta combinação na eficácia de recuperação.



13

Coleção de Testes

3.742.983 páginas (11,14% da Web Brasileira)

Estratégias Diferentes combinações de a e b

(1) Estratégia Textual (TEXT);

(2) Peso de Autoridade (AUT);

(3) 0.85TEXT_0.15AUT;

(4) 0.75TEXT_0.25AUT;

(5) 0.65TEXT_0.35AUT


Técnica de Avaliação

Julgamento Cego utilizando as métricas

Precisão@10, PMTS@10



14

MetodologiaAbordagemContribuições e

Originalidade PublicaçõesMotivação e Problema Detalhamento

Lista de Consultas1.2....100.

Engenho de Busca 1

Engenho de Busca 2

Processador de Consultas

Cache 1

Cache 2

Resposta Sistema 1

1.2....30.

Resposta Sistema 2

1.2....30.

Lista de páginas resposta

1.2.3....60.

Pool de Páginas

Resposta

PoolJulgamento

de Releância

Módulo de ArmazenamentoMódulo de Julgamento de Relevância

Lista de Consultas1.2....100.

Engenho de Busca 1

Engenho de Busca 2

Processador de Consultas

Cache 1

Cache 2

Resposta Sistema 1

1.2....30.

Resposta Sistema 2

1.2....30.

Lista de páginas resposta

1.2.3....60.

Pool de Páginas

Resposta

PoolJulgamento

de Releância

Módulo de ArmazenamentoMódulo de Julgamento de Relevância

Sistema de Julgamento de Relevância

15

Resultados do experimento



16

Discussão dos resultados:• 0.85TEXT_0.15AUT, 0.75TEXT_0.25AUT,

0.65TEXT_0.35AUT obtiveram melhor performance de recuperação que a estratégia TEXT

• 0.75TEXT_0.25AUT: melhoria mais significativa com relação a estratégia TEXT (CR_TEXT): – precisão@10= 9,42% – PMTS@10=14,64%

• AUT: pior performance neste experimento pois despreza características intrínsecas da página

TOP 100 autoridades foram “.com”



17

• Um novo Algoritmo de Análise de Links:- O tempo de resposta atende aos requisitos de tempo dos

EB comerciais (TR do HITS =~30 min)- Pesos de Hub e Autoridade calculados Off-line para todo o

grafo.- GHHITS reduz os requisitos de memória principal

necessários ao HITS estratégia de join orientado a blocos.

• Elaboração de um Sistema para Armazenamento e Análise de Links.

• Levantamento de características de um subgrafo da Web Brasileira (11,4%).- Número de forwardlinks e backlinks extrínsecos, intrínsecos.

• Sistema de Julgamento de Relevância.

MetodologiaAbordagem DetalhamentoPublicaçõesMotivação e

Problema

Contribuições e Originalidade

Documents

GHHITS – Mining the Web Link Structure