Introduction to Information Retrieval
Introduction to
Information Retrieval
CS276
Information Retrieval and Web Search
Christopher Manning and Prabhakar Raghavan
Lecture 16: Web search basics
(Fundamentos da busca Web)
Eduardo Augusto Silvestre
Introduction to Information Retrieval
História breve (não-técnica)
 Engines baseadas em palavras chave ca. 19951997
 Altavista, Excite, Infoseek, Inktomi, Lycos
 Ranking de busca paga: Goto (transformado
em Overture.com  Yahoo!)
 Sua busca no ranking dependente de quanto você
pagou
 Leilão para palavras chave: casino era caro!
Introduction to Information Retrieval
História breve (não-técnica)
 1998+: Ranking baseado em link, guiado pelo Google
 Jogue longe todas as outras engines de antes salvo Inktomi
 Grande experiência do usuário de um modelo de negócios
 Enquanto isso os ganhos anuais do Goto/Overture’s foram próximos
de $1 bilhão
 Resultado: Google adicionou busca paga “ads”, independente
dos resultados de busca
 Yahoo seguiu se adaptando, adquirindo Overture (para busca paga) e
Inktomi (para busca)
 2005+: Google ganha parte da busca, dominando na Europa e
muito forte na América do Norte
 2009: Yahoo! eMicrosoft propõem oferecer busca paga combinada
Introduction to Information Retrieval
Paid
Search Ads
Algorithmic results.
Sec. 19.4.1
Introduction to Information Retrieval
Fundamentos da busca Web
Sponsored Links
CG Appliance Express
Discount Appliances (650) 756-3931
Same Day Certified Installation
www.cgappliance.com
San Francisco-Oakland-San Jose,
CA
User
Miele Vacuum Cleaners
Miele Vacuums- Complete Selection
Free Shipping!
www.vacuums.com
Miele Vacuum Cleaners
Miele-Free Air shipping!
All models. Helpful advice.
www.best-vacuum.com
Web
Results 1 - 10 of about 7,310,000 for miele. (0.12 seconds)
Miele, Inc -- Anything else is a compromise
Web spider
At the heart of your home, Appliances by Miele. ... USA. to miele.com. Residential Appliances.
Vacuum Cleaners. Dishwashers. Cooking Appliances. Steam Oven. Coffee System ...
www.miele.com/ - 20k - Cached - Similar pages
Miele
Welcome to Miele, the home of the very best appliances and kitchens in the world.
www.miele.co.uk/ - 3k - Cached - Similar pages
Miele - Deutscher Hersteller von Einbaugeräten, Hausgeräten ... - [ Translate this
page ]
Das Portal zum Thema Essen & Geniessen online unter www.zu-tisch.de. Miele weltweit
...ein Leben lang. ... Wählen Sie die Miele Vertretung Ihres Landes.
www.miele.de/ - 10k - Cached - Similar pages
Herzlich willkommen bei Miele Österreich - [ Translate this page ]
Herzlich willkommen bei Miele Österreich Wenn Sie nicht automatisch
weitergeleitet werden, klicken Sie bitte hier! HAUSHALTSGERÄTE ...
www.miele.at/ - 3k - Cached - Similar pages
Search
Indexer
The Web
Indexes
Ad indexes
Sec. 19.4.1
Introduction to Information Retrieval
Usuário precisa
 Need [Brod02, RL04]
 Informational– quer aprender sobre alguma coisa (~40% / 65%)
Low hemoglobin
 Navigational – quer ir para uma página (~25% / 15%)
United Airlines
 Transactional – quer fazer alguma coisa (web-mediated) (~35% / 20%)
 Acessar um serviço
 Downloads
 Shop
Seattle weather
Mars surface images
Canon S410
 Gray areas
 Encontrar um bom centro Car rental Brasil
 Busca exploratória “ver o que mais”
Introduction to Information Retrieval
Quão longe as pessoas olham os resultados ?
(Source: iprospect.com WhitePaper_2006_SearchEngineUserBehavior.pdf)
Introduction to Information Retrieval
Avaliação empírica dos usuários dos
resultados
 Qualidade de páginas varia amplamente
 Relevância não é suficiente
 Outras qualidades desejadas (não relacionadas a RI !!)
 Conteúdo: Confiável, diverso, não-duplicado, bem mantido
 Legibilidade Web : mostrar corretamente e rápido
 S/ aborrecimentos: pop-ups, etc
 Precision vs. recall
 Na web, recall raramente importa
 O que importa
 Precisão de 1?
 Compreensividade – deve ser capaz de lidar com consultas obscuras
 Recall importa quando o número de resultados é muito pequeno
 Percepção do usuário pode não ser científica, mas é
signficante sobre um grande agregado
Introduction to Information Retrieval
Avaliação empírica dos usuários dos
resultados





Relevância e validade dos resultados
UI – Simples, sem bagunça, tolerante a erros
Confiança – Resultados são objetivos
Cobertura de tópicos para consultas polissêmicas
Ferramentas fornecidas para Pre/Pós processo
 Mitigar erros do usuário (verificação ortográfica automática, auxílio na
busca,…)
 Explícito: Busca dentro dos resultados, mais disso, refinar ...
 Antecipativa: buscas relacionadas
 Tratar excentricidade
 Vocabulário específico da Web
 Impacto sobre stemming, verificação ortográfica, etc
 Endereço Web digitado na caixa de busca
 “O primeiro, o último, o melhor e o pior …”
Sec. 19.2
Introduction to Information Retrieval
A coleção de documentos Web
A Web
 S/ projeto/coordenação
 Criação de conteúdo distribuído, linking,
democratização da publicação
 Conteúdo inclui verdades, mentiras,
informações obsoletas, contradições …
 Não estruturado (texto, html, …), semiestruturado (XML), estruturado (banco de
dados)…
 Escala muito maior que a coleção de
texto anterior … mas registros de
corporações estão alcançando
 Crescimento – “volume dobra em poucos
meses”, ainda continua expandindo
 Conteúdo pode ser gerado
dinamicamente
Introduction to Information Retrieval
Spam
 SEO – Search Engine Optimization
(Otimização da máquina de busca)
Introduction to Information Retrieval
Sec. 19.2.2
O problema com busca paga ads …
 Custa dinheiro. Qual alternativa?
 SEO (Search Engine Optimization):
 “Tuning” sua página p/ aparercer nas primeiras posições
nos resultados de algoritmos de busca p/ palavras
chaves selecionadas
 Alternativa p/ não ter de pagar
 Assim, uma função de marketing
 Realizado por companias, webmasters e
consultores (“Search engine optimizers”) para seus
clientes
 Alguns perfeitamente legitimados, alguns sombrios
Introduction to Information Retrieval
Sec. 19.2.2
Search engine optimization (Spam)
 Motivos
 Comercial, político, religioso, lobbies
 Promoção consolidada pela propaganda
 Operadores
 Contratantes (Search Engine Optimizers) para lobbies, companias
 Web masters
 Provedor de serviços
 Forums
 Isto é, Web master world ( www.webmasterworld.com )
 Truques para máquinas de busca específicas
 Discussão sobre papers acadêmicos 
Introduction to Information Retrieval
Sec. 19.2.2
Forma mais simples
 Primeira geração de máquinas confiavam em tf/idf
 As páginas do topo do ranking p/ consulta maui resort foram
aquelas contendo mais maui’s e resort’s
 SEOs responderam com densa repetição dos termos
escolhidos
 Isto é, maui resort maui resort maui resort
 Frequentemente, as repetições seriam da mesma cor como o
plano de fundo da página
 Termos repetidos indexados pelos crawlers
 Mas não visível p/ humanos ou browsers
Densidade de palavras
puramente não pode ser
confiável como um sinal de RI
Introduction to Information Retrieval
Sec. 19.2.2
Variantes de keyword stuffing
 Meta-tags “enganosas”, repetição excessiva
 Texto escondido com cores, truques de folha de
estilo, etc.
Meta-Tags =
“… London hotels, hotel, holiday inn, hilton, discount,
booking, reservation, sex, mp3, britney spears, viagra, …”
Sec. 19.2.2
Introduction to Information Retrieval
Cloaking
 Conteúdo falso serve à maquinas de busca spider
 DNS cloaking: Troca de endereço IP.
Y
SPAM
Is this a Search
Engine spider?
Cloaking
N
Real
Doc
Introduction to Information Retrieval
Sec. 19.2.2
Mais técnicas spam
 Doorway pages (Páginas de portal)
 Páginas otimizadas p/ uma única palavra chave que
redirecionadas para página alvo de fato
 Link spamming
 Mutual admiration societies, links ocultos, prêmios –
mais um desse depois
 Domain flooding: numerosos domínios que apontam ou
redirecionam para uma página alvo
 Robôs
 Falsa stream de consulta – rank checking programs
 “Curve-fit” ranking programs of search engines
 Milhões de submissões via Add-Url
Introduction to Information Retrieval
A guerra contra spam
 Sinais de qualidade – Prefira  Reconhecimento de
páginas autoritárias
spammers por
aprendizado de máquinas
baseadas em:
 Votos dos autores (sinais de
ligação)
 Votos dos usuários (sinais de
uso)
 Policiando das submissões
da URL
 Teste anti-robô
 Limites sobre as meta
palavras chave
 Análise robusta de links
 Ignore ligações estatísticas
improváveis (ou texto)
 Use análise de link para detectar
 Treinando um conjunto
baseado no conhecimento de
spam
 Filtros amigavelmente
familiares
 Análise linguística, técnicas de
classificação, etc.
 Para imagens: flesh tone
detectors, análise do texto
fonte, etc.
 Intervenção editorial




Listas negras
Top queries audited
Queixa de endereço
Detecção de padrão suspeito
Introduction to Information Retrieval
Mais sobre spam
 Máquinas de busca Web tem políticas das práticas
SEO que eles toleram/bloqueiam
 http://help.yahoo.com/help/us/ysearch/index.html
 http://www.google.com/intl/en/webmasters/
 Adversário da RI: a interminável (técnico) batalha
entre SEO’s e máquinas de busca Web
 Pesquisa http://airweb.cse.lehigh.edu/
Introduction to Information Retrieval
Tamanho da Web
Introduction to Information Retrieval
Sec. 19.5
Qual é o tamanho da Web ?
 Questões
 A Web é realmente infinita
 Conteúdo dinâmico, isto é, calendário
 Soft 404: www.yahoo.com/<qualquer_coisa> é uma página válida
 Web estática contém duplicação sintática, principalmente
devido a mirroring (~30%)
 Alguns servidores são raramente conectados
 Quem preocupa?
 Mídia e consequentemente o usuário
 Projetos de máquinas
 Engine crawl policy. Impacto sobre recall.
Introduction to Information Retrieval
Sec. 19.5
O que podemos tentar medir?
O tamanho relativo das máquinas de busca
 A noção de página sendo indexada é ainda razoavelmente
bem definida
 Já existem problemas
 Extensão de documento: isto é, máquinas indexam páginas não
ainda crawled, pela indexação anchortext.
 Restrição de documento: Todas engines restringem qual é
indexado (primeiras n palavras, somente palavras relevantes, etc.)
A cobertura de uma máquina de busca relativa a
outro processo particular crawling.
Introduction to Information Retrieval
Sec. 19.5
Nova definição ?
(IQ é qualquer medida de teste IQ)
 A Web indexável estaticamente é qualquer
índice de máquina de busca.
 Diferentes máquinas tem diferentes preferências
 max url depth, max count/host, regras anti-spam, regras
de prioridade, etc.
 Diferentes indexes de máquinas diferentes coisas
sobre a mesma URL:
 frames, meta palavras chaves, restrições de documentos,
extensões de documentos, ...
Sec. 19.5
Introduction to Information Retrieval
Tamanho relativo do Overlap
Dado duas máquinas A e B
Exemplo URLs de A aleatoriamente
AB
Checar se contido em B e viceversa
A B = (1/2) * Tamanho A
A B = (1/6) * Tamanho B
(1/2)* Tamanho A = (1/6)*
Tamanho B
\ Tamanho A / Tamanho B =
(1/6)/(1/2) = 1/3
Cada teste envolve: (i) Amostra (ii) Verificação
Introduction to Information Retrieval
Sec. 19.5
URLs de amostra
 Estratégia ideal: Gerar uma URL aleatoriamente e checar
a restrição (containment) em cada índice.
 Problema: URLs aleatórias são difíceis de econtrar!
Suficiente gerar uma URL aleatória contida em uma
dada máquina.
 Abordagem 1: Gerar uma URL aleatória contida em uma
dada máquina
 Suficiente para a estimar o tamanho relativo
 Abordagem 2: Random walks / IP addresses
 Na teoria: poderia nos dar uma estimativa verdadeira do tamanho da web
Introduction to Information Retrieval
Métodos estatísticos
 Abordagem1
 Consultas aleatórias
 Buscas aleatórias
 Approach 2
 Endereços de IP aleatórios
 Passeio aleatório (Random walks)
Sec. 19.5
Introduction to Information Retrieval
Sec. 19.5
URLs aleatórias de consultas aleatórias
 Gerar uma consula aleatória: como ?
 Vocabulário: 400,000+ palavras de um web crawl
 Consultas conjuntivas: w1 e w2
Isto é, vocalists AND rsi
 Pegue 100 URLs de resultado da máquina A
 Escolha uma URL aleatória como candidata para checar a
presenção na máquina B
 Isso distribuição induz a um peso de probabilidade W(p)
para cada página
 Conjetura: W(SEA) / W(SEB) ~ |SEA| / |SEB|
Introduction to Information Retrieval
Sec. 19.5
Verificação baseada na consulta
 Strong Query para checar se uma máquina B tem um
documento D:
 Download D. Pegue a lista de palavras.
 Use 8 palavras de baixa frequencia como AND da consulta
para B
 Cheque se D está presente no conjunto de resultados.
 Problemas:





Duplicações próximas
Frames
Redirecionamentos
Time-outs das máquians
Consultas de 8 palavras são de um bom tamanho ?
Introduction to Information Retrieval
Sec. 19.5
Vantagens e desvantagens
 Statistically sound under the induced weight.
 Biases induced by random query




Query Bias: Favors content-rich pages in the language(s) of the lexicon
Ranking Bias: Solution: Use conjunctive queries & fetch all
Checking Bias: Duplicates, impoverished pages omitted
Document or query restriction bias: engine might not deal properly
with 8 words conjunctive query
 Malicious Bias: Sabotage by engine
 Operational Problems: Time-outs, failures, engine inconsistencies,
index modification.
Introduction to Information Retrieval
Sec. 19.5
Buscas aleatórias
 Escolha buscas aleatórias extraídas de um registro
local [Lawrence & Giles 97] ou construir “buscas
aleatórias” [Notess]
 Use somente consultas com um pequeno conjunto de
resultados.
 Conte URLs normalizadas no conjunto de resultados.
 Use estatísticas
Introduction to Information Retrieval
Sec. 19.5
Vantagens e desvantagens
 Vantagem
 Pode ser uma melhor percepção humana da cobertura
 Questões
 Exemplos são relacionados com o fonte do registro
 Duplicados
 Problemas estatísticos técnicos (deve ter resultados,
ratio average not statistically sound)
Introduction to Information Retrieval
Sec. 19.5
Buscas aleatórias
 575 e 1050 queries from the NEC RI employee logs
 6 Engines in 1998, 11 in 1999
 Implementação:
 Restrito a consultas com < 600 resultados no total
 URLs contadas da máquina de busca depois da verificação
do emparelhamento da consulta
 Razão do tamanho computada & overlap para consultas
individuais
 Tamanho estimado do índice & overlap pela média de
todas as consultas
Sec. 19.5
Introduction to Information Retrieval
Consultas do estudo de Lawrence e Giles
 adaptive access control
 neighborhood preservation
topographic
 hamiltonian structures
 right linear grammar
 pulse width modulation neural
 unbalanced prior probabilities
 ranked assignment method
 internet explorer favourites
importing
 karvel thornber
 zili liu
 softmax activation function
 bose multidimensional system
theory
 gamma mlp
 dvi2pdf
 john oliensis
 rieke spikes exploring neural
 video watermarking
 counterpropagation network
 fat shattering dimension
 abelson amorphous computing
Introduction to Information Retrieval
Endereços de IP aleatórios
 Gere endereços de IP aleatórios
 Encontre um servidor web do endereço dado
 Se existir um
 Pegue todas as páginas do servidor
 Dessas, escolha uma aleatoriamente
Sec. 19.5
Introduction to Information Retrieval
Sec. 19.5
Endereços de IP aleatórios
 Requisição HTTP p/ um endereço de IP aleatório
 Ignorada: vazio or autorização requerida ou excluída
 [Lawr99] Estima-se que 2.8M de endereços de IP
executando em servicores web crawlable (16 milhões no
total) dos 2500 servidores observados
 OCLC usando IP de amostra encontrou 8.7 M hosts em
2001
 Netcraft [Netc02] acessou 37.2 milhões hosts em Julho 2002
 [Lawr99] crawled exaustivamente 2500
 Estimou o tamanho da web como 800 milhões de páginas
 Estimou o uso de metadados descritores:
 Meta tags (palavra chave, descrição) em 34% das páginas
Introduction to Information Retrieval
Sec. 19.5
Vantagens e desvantagens
 Vantagens
 Estatísticas claras
 Independente das estratégias de crawling
 Desvantagens
 Não trata duplicação
 Muitos hosts podem compartilhar um IP, ou não aceitar
requisições
 Não tem garantia que todas as páginas estão linkadas para
uma página raiz
 Lei do poder para páginas #/hosts geraram bias em direção a
sites com poucas páginas.
 Mas bias podem ser quantificados precisamente
 Influenciado potencialmente por spamming (múltiplos IPs para
um mesmo servidor para evitar bloqueio de IP)
Introduction to Information Retrieval
Sec. 19.5
Passeio aleatório (Random walks)
 Veja a Web como um grafo dirigido
 Construa um passeio aleatório nesse grafo
 Inclua várias regras de “pulo” para voltar a sites já visitados
 Não fique presos em spider traps!
 Pode seguir todos os links!
 Convirja para uma distribuição estacionária
 Deve assumir o grafo como finito e independente do caminho.
 Condições não estão satisfeitas (cookie crumbs, flooding)
 Tempo para convergência não é realmente conhecido
 Exemplo de distribuição estacionária do passeio
 Use o método da “consulta forte” para checar a cobertura
pelos SE (Search Engines)
Introduction to Information Retrieval
Sec. 19.5
Vantagens e desvantagens
 Vantagens
 Método “estatisticamente claro” pelo menos na teoria!
 Podia trabalhar até mesmo para uma web infinita
(assumindo convergência) sobre certas métricas.
 Desvantagens
 Lista de “sementes” é um problema.
 Aproximação prática pode não ser válida.
 Distribuiçã não uniforme
 Subject to link spamming
Introduction to Information Retrieval
Sec. 19.5
Conclusão




Sem soluções perfeitas
Várias novas idéias ...
....mas o problema está ficando difícil
Estudos quantitativos são fascinantes e um bom
problema de pesquisa
Introduction to Information Retrieval
Detecção de duplicações
Sec. 19.6
Introduction to Information Retrieval
Sec. 19.6
Documentos duplicados
 A Web é cheia de conteúdo duplicado
 Detecção de duplicação restrito = exata
 Não é comum
 Mas muitos, muitos casos perto de duplicação
 Isto é, última data de modificação a única
diferença entre duas cópias de uma página
Introduction to Information Retrieval
Sec. 19.6
Duplicado/Detecção de duplicação próxima
 Duplicação: Emparelhamento idêntico, pode ser
detectado com impressão digital (fingerprints)
 Duplicação próxima: Emparelhamento próximo
 Visão geral
 Calcula a similaridade estática com uma edit-distance
measure
 Use similaridade limiar para detectar duplicações
próximas
 Isto é, similaridade > 80% => Documentos são
“aproximadamente duplicados”
Introduction to Information Retrieval
Sec. 19.6
Calculando similaridade
 Características:
 Segmentos de um documento (breakpoints naturais ou
artificiais)
 Shingles (Word N-Grams)
 a rose is a rose is a rose →
a_rose_is_a → rose_is_a_rose →
is_a_rose_is → a_rose_is_a
 Medida de similaridade entre dois documentos (= conjuntos de
shingles)
 Conjunto de interseção
 Especificamente (Tamanho_interseção / Tamanho_união)
Sec. 19.6
Introduction to Information Retrieval
Shingles + Conjunto de intersecção
 Calcular o conjunto exato de interseção de shingles
entre todos os pares de documentos é caro
 Aproximar utilizando um conjunto de esclha inteligente of
shingles de cada (um esboço)
 Estimativa(tamanho da intersecção / tamanho da
união) baseado em um pequeno esboço
Doc
A
Shingle set A
Doc
B
Shingle set B
Sketch A
Jaccard
Sketch B
Introduction to Information Retrieval
Sec. 19.6
Esboço de um documento
 Crie um “sketch vector” (tamanho ~200) para
cada documento
 Documentos que partilham ≥ t (digo 80%)
elementos correspondentes do vetor são
aproximadamente duplicados
 Para doc D, esboçoD[ i ] é como segue:
 Seja f map todos shingles em um universo de 0..2m (isto
é, f = impressão digial)
 Seja pi uma permutação aleatória em 0..2m
 Escolha MIN {pi(f(s))} todos shingles s em D
Sec. 19.6
Introduction to Information Retrieval
Calculando Sketch[i] para Doc1
Documento 1
264
Comece com 64-bit f(shingles)
264
Permute no número da linha com
264
264
pi
Escolha o valor mínimo
Sec. 19.6
Introduction to Information Retrieval
Teste se Doc1.Sketch[i] = Doc2.Sketch[i]
Documento 2
Documento 1
A
264
264
264
264
264
264
264
B
264
São iguais?
Teste para 200 permutações aleatórias: p1, p2,… p200
Sec. 19.6
Introduction to Information Retrieval
Entretanto…
Documento 1
Documento 2
264
264
264
264
A
264
264
B
264
264
A = B se o shingle com o valor MIN na união de Doc1 e
Doc2 é comum para ambos (isto é, mentem na
intersecção)
Why?
Reivindicação: Isso acontece com probabilidade
Tamanho da intersecção / Tamanho da união
Introduction to Information Retrieval
Similaridade de conjunto dos
conjuntos Ci , Cj
Jaccard(C i , C j ) 
Sec. 19.6
Ci  C j
Ci  C j
 Olhe conjuntos com uma coluna da matriz A; uma linha
para cada elemento no universo. aij = 1 indica presença
do item i no conjunto j
C1 C2
 Exemplo
0
1
1
0
1
0
1
0
1
0
1
1
Jaccard(C1,C2) = 2/5 = 0.4
Introduction to Information Retrieval
Sec. 19.6
Observação chave
 Para colunas Ci, Cj, quatro tipos de linhas
A
B
C
D
Ci
1
1
0
0
Cj
1
0
1
0
 Notação de sobrecarga: A = # das linhas do tipo A
 Reivindicação
A
Jaccard(C i , C j ) 
A BC
Introduction to Information Retrieval
Sec. 19.6
“Min” Hashing
 Randomly permute rows
 Hash h(Ci) = índice da primeira linha com 1 na
coluna Ci
 Propriedade surpreendente
P  h(C i )  h(C j )   Jaccard Ci , C j 
 Por que?
 Ambos são A/(A+B+C)
 Look down columns Ci, Cj until first non-Type-D row
 h(Ci) = h(Cj)  type A row
Introduction to Information Retrieval
Sec. 19.6
Min-Hash sketches
 Pick P random row permutations
 MinHash sketch
SketchD = list of P indexes of first rows with 1 in column C
 Similarity of signatures
 Let sim[sketch(Ci),sketch(Cj)] = fraction of permutations
where MinHash values agree
 Observe E[sim(sig(Ci),sig(Cj))] = Jaccard(Ci,Cj)
Sec. 19.6
Introduction to Information Retrieval
Example
R1
R2
R3
R4
R5
C1
1
0
1
1
0
C2
0
1
0
0
1
C3
1
1
0
1
0
Signatures
S1
Perm 1 = (12345) 1
Perm 2 = (54321) 4
Perm 3 = (34512) 3
S2
2
5
5
S3
1
4
4
Similarities
1-2
1-3 2-3
Col-Col 0.00 0.50 0.25
Sig-Sig 0.00 0.67 0.00
Introduction to Information Retrieval
Sec. 19.6
Implementação de truque
 Permuting universe even once is prohibitive
 Row Hashing
 Pick P hash functions hk: {1,…,n}{1,…,O(n)}
 Ordering under hk gives random permutation of rows
 One-pass Implementation
 For each Ci and hk, keep “slot” for min-hash value
 Initialize all slot(Ci,hk) to infinity
 Scan rows in arbitrary order looking for 1’s
 Suppose row Rj has 1 in column Ci
 For each hk,
 if hk(j) < slot(Ci,hk), then slot(Ci,hk)  hk(j)
Sec. 19.6
Introduction to Information Retrieval
Exemplo
R1
R2
R3
R4
R5
C1
1
0
1
1
0
C2
0
1
1
0
1
h(x) = x mod 5
g(x) = 2x+1 mod 5
C1 slots
h(1) = 1
g(1) = 3
C2 slots
1
3
-
h(2) = 2
g(2) = 0
1
3
2
0
h(3) = 3
g(3) = 2
1
2
2
0
h(4) = 4
g(4) = 4
h(5) = 0
g(5) = 1
1
2
1
2
2
0
0
0
Introduction to Information Retrieval
Sec. 19.6
Comparando assinaturas
 Assinatura Matriz S
 Linhas = Funções Hash
 Colunas = Colunas
 Entradas = Assinaturas
 Pode calcular – Pair-wise similarity of any
pair of signature columns
Introduction to Information Retrieval
Sec. 19.6
Todos os pares de assinatura
 Agora temos um método extremamente eficiente
para estimar o coeficiente de Jaccard para um único
par de documentos
 Mas ainda temos de estimar coeficientes N2 onde N
é o número de páginaw web
 Still slow
 Uma solução: locality sensitive hashing (LSH)
 Outra solução: sorting (Henzinger 2006)
Introduction to Information Retrieval
More resources
 IIR Chapter 19