Instituto Superior Técnico
Recuperação de Informação
Efficient Phrase Querying with
an Auxiliary Index
(SIGIR) 2002
Prof. Dr. Pável Pereira Calado
Trabalho realizado por:
João Casteleiro Alves
1
Estrutura da apresentação

Introdução

Propriedades das “queries”
Índices Invertidos
Pré - Processamento da imagem
 Índices “Nextword”

Abordagem combinada de avaliação de “queries”
Abordagem 1: Detecção de Contornos
 Resultados experimentais


Conclusões 2: Extracção de Características
Abordagem
2
Introdução
 Procura de informação na Web é dependente de
motores de busca.
Eficiência
Eficácia
 Para fazer a busca de informação na Web é então
necessário
Download dos textos/informação
Indexar o conteúdo
Querie
3
Introdução
 Crescimento da Web (consequências)
- Invisibilidade
- Mapeamento dos indíces em relação
conteúdo público indexável.
A 08-Jul-2006 o Google
indexava cerca de
24.000.000.000 páginas
 Dificuldades ao nivel das consultas (podem ser vagas)
 As consultas são normalmente feitas através de simples
palavras
4
Introdução
 Solução:
- Pesquisa por frases
Não é ambigua na definição do conceito
 Para se fazer uma pesquisa por frases é então
necessário os motores de busca possuirem métodos
apropriados.
- Índices invertidos
- Índices “nextword”
5
Introdução
 Os métodos de avaliação de frases “querie” podem no
entanto requisitar muitos Mb, tornando o seu uso limitado.
Soluções apresentadas:
- Usar “stopping words”
- Indexar frases directamente
 Devido às limitações apresentadas pelas soluções
anteriores é assim proposta uma nova solução:
- Combinação de índices invertidos e de
índices “nextword”.
6
Estrutura da apresentação

Introdução

Propriedades das “queries”
Índices Invertidos
Pré - Processamento da imagem
 Índices “Nextword”

Abordagem de avaliação da query combinada
Abordagem 1: Detecção de Contornos
 Resultados experimentais


Conclusões 2: Extracção de Características
Abordagem
7
Propriedades das “queries”
 De modo a estudar as caracteristicas das “queries” foi
analisado um grande conjunto de registos de “queries”.
- Foram usados dados do “Excite”
 Após se retirar as “queries” de conteúdo obsceno,
obtiveram-se 1,583,922 consultas.
132,576 ou 8,3% dizem
respeito a frases “queries”.
5% contém uma palavra que
não ocorre nos 21.9 Gb de
dados usados
41% das “queries” que não são
frases correspondem a uma
frase nos 21.9Gb usados
8
Propriedades das “queries”
 Estudando apenas as frases “queries” verifica-se que,
11,103 ou 8.4% incluem uma das três palavras mais
comuns no conjunto de dados.
 14,4% das frases “queries” contêm uma das vinte
palavras mais comuns.
QUESTÃO: As palavras comuns são
importantes ou não???
SIM
Não
9
Propriedades das “queries”
 Posto isto, usar o método de “stopping” nas palavras
comuns leva a um resultado imprevísivel.
 Fazer o “stopping” das palavras comuns da query “tower
of London” resulta em avaliar “tower --- London”.
 Foram estudado os documentos encontrados para todas as “queries”
com diferentes valores de “stopping” para as palavras comuns.
- “Stopping” ás 3 palavras mais comuns
390 x 10^6
- “Stopping” ás 20 palavras mais comuns
490 x 10^6
- “Stopping” ás 254 palavras mais comuns
1693 x 10^6
Nem todas as correspondências são correctas
10
Estrutura da apresentação

Introdução

Propriedades das “queries”
Índices Invertidos
Pré - Processamento da imagem
 Índices “Nextword”

Abordagem combinada de avaliação de “query”
Abordagem 1: Detecção de Contornos
 Resultados experimentais


Conclusões 2: Extracção de Características
Abordagem
11
Índices Invertidos
 Os índices invertidos são o método standard de suporte
de “queries” em grandes bases de dados de texto.
 Um índice invertido é uma estrutura de dois níveis:
- O nível mais acima contém todos os índices dos
termos da colecção (palavras pertencentes ao texto).
- O nível mais baixo é um conjunto de listas de
“postings”, uma por cada índice de termo.
12
Índices Invertidos
 Cada “posting” é assim composto por três elementos.
- d é o identificador do documento que contém o termo t.
- f d,t é a frequência de t em d.
- o é o valor das posições em d em que t é observado.
13
Índices Invertidos
 Vocabulário de 5 palavras em que cada uma tem uma
lista de “postings”.
 É então aliciante aplicar um índice invertido na busca por
um único termo.
14
Índices Invertidos
 QUESTÃO: Como funcionam os índices invertidos para frases
(mais do que um termo) ???
A idéia é fazer multiplas pesquisas, procurando ocorrências
sucessivas dos termos nos documentos.
O primeiro termo é procurado, resultando uma lista temporária
de documentos e posições do termo nos documentos
O próximo termo é pesquisado na lista temporária, sendo
retirados os documentos em que o termo não ocorre na
posição na posição correcta.
O processo repete-se até que o último termo seja encontrado
ou que a lista temporária fique vazia.
15
Índices Invertidos
 Temos então um custo linear para o processo de busca e
também para o custo do espaço.
 A ordem de busca dos termos da frase é fundamental.
- Devemos iniciar a busca pelo termo menos frequente
(fazendo a pesquisa em ordem diferente da ordem de
ocorrência dos termos na frase, mas nunca perdendo a
sua posição inicial).
- Minimizamos tempo e espaço, já que a lista
temporária inicial terá o menor tamanho possível
Iniciar uma pesquisa por um termo muito comum nos
documentos pode levar a uma lista intratável.
16
Índices Invertidos
 Podem ser usadas diversas técnicas de optimização da consulta
por frases com índices invertidos.
 Uma optimização importante é o uso de técnicas de compressão.
17
Estrutura da apresentação

Introdução

Propriedades das “queries”
Índices Invertidos
Pré - Processamento da imagem
 Índices “Nextword”

Abordagem combinada de avaliação de “query”
Abordagem 1: Detecção de Contornos
 Resultados experimentais


Conclusões 2: Extracção de Características
Abordagem
18
Índices “Nextword”
 Os ficheiros invertidos permitem a avaliação de “queries” por frases,
no entanto, as técnicas de indexação de frases orientadas são mais
eficientes.
 Uma dessas técnicas é conhecida como índices “nextword”
 Um índice “nextword” é uma estrutura de 3 niveis:
- No primeiro nível temos as palavras do vocabulário, a
que se chamam de “firstwords”.
- No segundo nível temos o índice para a próxima palavra
- No último nível, para cada “nextword” existe uma lista de
“postings” das posições em que o par “firstword-nextword”
ocorrem.
19
Índices “Nextword”
- Neste exemplo existem 2 “firstword”  “in” e “new”.
- Existem algumas “nextword”  “all”, “new”, “age”, etc.
- Para cada par “firstword-nextword” existe uma lista de postings.
20
Índices “Nextword”
 Facilmente se percebe que o tamanho das listas de “postings” para
os índices “nextword” é normalmente pequeno.
A maioria dos pares não aparece frequentemente
“boulder municipal employees credit union”
“boulder”.”municipal”, “employess”.”credit” e ”credit”.”union”
“boulder”.”municipal”, “municipal”.” employess” e ”credit”.”union”
Qual o conjunto de pares que deve ser avaliado???
21
Índices “Nextword”
 Método de escolha da ordem de avaliação dos pares
- Se o número dos termos querie for par, a query consiste em n/2
pares dijuntos.
- Se o número dos termos da querie for impar, a query consiste em
n/2 pares conjuntos.
Exemplo: “The man who is”
22
Índices “Nextword”
 O índice “nextword” obtido para a colecção de dados usada tinha o
tamanho de 4487 Mb, muito maior que um índice invertido.
 O tempo de avaliação de “queries” reduziu significativamente
(quando comparado com os índices invertidos).
23
Estrutura da apresentação

Introdução

Propriedades das “queries”
Índices Invertidos
Pré - Processamento da imagem
 Índices “Nextword”

Abordagem combinada de avaliação de “query”
Abordagem 1: Detecção de Contornos
 Resultados experimentais


Conclusões 2: Extracção de Características
Abordagem
24
Abordagem de avaliação da query combinada

Esta abordagem tenta obter o melhor dos dois métodos
apresentados antes (listas ínvertidas e listas “nextword”).
Objectivo: Manter a eficiência das consultas, diminuindo o
tamanho dos índices gerados.

É então usado um esquema de “top frequency”.
- Apenas as palavras mais comuns são usadas como
índice “nextword”.
- As restantes palavras são indexadas como um índice
invertido.
25
Abordagem de avaliação da query combinada
“historic railroads in new hampshire”
 “historic” e “railroads” são processados tendo em
conta o índice invertido.
 “in” e “new” são palavras comuns, logo o par
“in”.”new” deve ser procurado nos índices “nextword”.
 “new”.”hampshire” ou “hampshire”???
26
Estrutura da apresentação

Introdução

Propriedades das “queries”
Índices Invertidos
Pré - Processamento da imagem
 Índices “Nextword”

Abordagem combinada de avaliação de “query”
Abordagem 1: Detecção de Contornos
 Resultados experimentais


Conclusões 2: Extracção de Características
Abordagem
27
Resultados experimentais
Índice “Nextword”
Índice combinado
Abordagem 1: Detecção de Contornos

Usar um índice “nextword” permite a avaliação de
todas as frase “queries” de um modo rápido.

Verifica-se que se consegue obter tamanhos de
índices de menores dimênsões.

Os tempos obtidos pela abordagem combinada são os
melhores.
28
Estrutura da apresentação

Introdução

Propriedades das “queries”
Índices Invertidos
Pré - Processamento da imagem
 Índices “Nextword”

Abordagem combinada de avaliação de “query”
Abordagem 1: Detecção de Contornos
 Resultados experimentais


Conclusões 2: Extracção de Características
Abordagem
29
Conclusões

Foi proposto o uso de um índice auxiliar pequeno para
frases “queries” de grandes coleccções de texto

Todas as palavras estão indexadas num índice
invertido, no entanto as mais comuns estão também
num índice “nextword” (abordagem combinada).

O custo dos índices de avaliação de frases foi
substancialmente reduzido.

Estes resultados demonstram ainda que não é
necessário fazer “stopping” nas frases.

O sistema pode ser melhorado, especialmente na
escolha de pares durante a avaliação da querie.
30
FIM
31