Busca Rápida Baseada em Similaridade
para Redes Par-a-Par
Fast Similarity Search in Peer-to-Peer Networks
NOMS 2008
Autores: Thomas Bocek
Ela Hunt
David Hausheer
Burkhard Stiller
Apresentador: Sérgio Samuel Furlaneto
18 de Novembro de 2009
Agenda
•
•
•
•
•
•
Introdução
Motivação
Objetivo
P2PFast
Conclusão do autor
Conclusão do apresentador
2
Motivação
• Necessidade de sistemas de busca baseados
na similaridade de texto: tipografia
• Eficiência no tratamento de palavras pequenas
3
Objetivo
• Descoberta de serviços e arquivos baseado em
sua descrição
• Estrutura descentralizada
• Seja aplicável a qualquer DHT
• Independente do algoritmo de roteamento
4
P2PFastSS
• É aplicável à descoberta de serviços e arquivos
• Usa distância de edição
– Número mínimo de operações para transformar
uma string em outra: Apagar, Inserir e Substituir
5
P2PFastSS - Funcionamento
• Dividido em duas fases:
– Indexação:
• Identifica todas as palavras de um documento
• Gera vizinhança a partir de remoção de caracteres
• Indexação de arquivos a partir da vizinhança gerada
– Busca:
• Gera vizinhança a partir da remoção de um caractere
• Cada vizinho é consultado para uma chave. Cada
documento contém um ID e palavra-chave
• O documento é recuperado
6
P2PFastSS - Indexação
• Os documentos são armazenados usando DHT,
cuja chave é o hash do título do documento
Posição
1234
TESA
1
ESA
2
TSA
3
TEA
4
TES
• Todos as referências vizinhas ao novo
documento são armazenadas
7
TESTE
TESTE
TESTE
TESTE
TESTE
TESTE
Título (Chave)
Documento (Texto)
Albedo(Doc ID:0x123)
O Albedo é um objeto...
Achilles(Doc ID:0x132) Na mitologia grega, Aquilles...
Papel(Doc ID:0x238)
O papel é uma comodite...
Teste(Doc ID:0x321)
O objetivo do teste...
Palavra-Chave (Key)
Localização do recurso
objeto(hash 0x432)
objeto, Doc ID: 0x123
ppel(hash 0x927)
papel: Doc ID: 0x238
pipel: Doc ID: 0x641
gua(hash 0x149)
agua: Doc ID: 0x583
tes(hash 0x123)
teste: Doc ID: 0x321
8
P2PFastSS – Avaliação
•
•
•
•
Java
360 hosts PlanetLab, cada um com 100 nós
Distância de edição k=1
Palavras com comprimento entre 3 e 16
caracteres
9
P2PFastSS - Avaliação
• Métricas
– Número de mensagens
– Latência
– Espaço para armazenamento
10
11
P2PFastSS - Avaliação
12
P2PFastSS - Avaliação
13
Conclusão - Autor
• Pode ser usado em qualquer rede P2P
• Independente da DHT usada
• Mecanismos de descoberta de serviços
baseados em texto
14
Conclusão - Apresentador
• Web Semântica
• Independente da DHT usada
• Mecanismos de descoberta de serviços
baseados em texto
15
Perguntas
16