Análise do LSH

Análise do processo

Assumimos que:

• existem posições (buckets) suficientes para que as colunas não sejam suscetíveis de mapeamento para a mesma posição a menos que sejam idênticas num banda específica

Em consequência, assumimos que “mesma posição” significa “idêntico nessa banda”

Esta simplificação é necessária apenas para simplificar a análise, não para a correção do algoritmo

Exemplo de aplicação

100 000 documentos (=> 100 000 colunas de M)

Assinaturas de 100 inteiros (linhas)

Com b = 20 bandas de r = 5 inteiros/banda

Objetivo: encontrar pares de documentos que apresentem s ≥ 0.8

Caso 1: sim(C1 , C2 ) =0.8

Vejamos primeiro o que acontecerá a dois documentos com similaridade elevada (0.8)

Probabilidade de C1 , C2 idênticas numa banda específica:

• J^r = (0.8)^5 = 0.329

Probabilidade C1 , C2 não serem semelhantes em todas as 20 bandas:

• (1 − 0.328)^20 = 0.00035

• Cerca de 1/3000 dos pares de colunas semelhantes a 80% são falsos negativos

Encontraríamos 99.97% de pares de documentos verdadeiramente semelhantes

Caso 1: sim(C1 , C2 ) =0.3

Considerando agora documentos com baixa similaridade sim(C1 ,C2 ) = 0.3

Probabilidade de C1 , C2 idênticas numa banda específica:

• J^r = (0.3)^5 = 0.00243

Probabilidade C1 , C2 não serem semelhantes em todas as 20 bandas:

• 1−(1−0.00243)20 = 0.0474

Aproximadamente 4.74% pares de documentos com similaridade de 0.3% acabam como pares candidatos, aparecendo como falsos positivos

Otimização do processo

A aplicação do LSH obriga a um compromisso entre os falsos positivos e falsos negativos

Este compromisso pode ser efetuado através de:

1. número de funções de dispersão, que resultam no número de linhas da matriz de assinaturas

2. número de bandas

3. número de linhas por banda