Por que o pacote textreuse em R torna os baldes de LSH muito maiores do que os meushes originais?

Question

Pelo que eu entendo, uma das principais funções do método LSH é a redução de dados, mesmo além dos hashes subjacentes (geralmente minhashes). Tenho usado o textreusepacote em R e estou surpreso com o tamanho dos dados que ele gera. textreuseé um pacote ROpenSci revisado por pares , então presumo que faça seu trabalho corretamente, mas minha dúvida persiste.

Digamos que eu use 256 permutações e 64 bandas para minhas funções minhash e LSH respectivamente - valores realistas que são freqüentemente usados ​​para detectar com certeza relativa (~ 98%) similaridades tão baixas quanto 50%.

Se eu hash um arquivo de texto aleatório usando TextReuseTextDocument(256 perms) e atribuí-lo a trtd, terei:

object.size(trtd$minhashes)
> 1072 bytes

Agora vamos criar os intervalos LSH para este objeto (64 bandas) e atribuí-lo a l, terei:

object.size(l$buckets)
> 6704 bytes

Portanto, os hashes retidos nos baldes do LSH são seis vezes maiores do que os meushes originais. Eu entendo que isso acontece porque textreuse usa um resumo md5 para criar os hashes de balde.

Mas isso não é muito desperdício / exagero e não posso melhorar isso? É normal que nossa técnica de redução de dados acabe inchando a esse ponto? E não é mais eficaz combinar os documentos com base nos hashes originais (semelhante a perms = 256 e bandas = 256) e então usar um limite para eliminar os falsos positivos?

Observe que eu revisei os textos típicos, como Mining of Massive Datasets , mas esta questão permanece sobre esta implementação particular. Observe também que a pergunta não é apenas por curiosidade, mas também por necessidade. Quando você tem milhões ou bilhões de hashes, essas diferenças se tornam significativas.

Answer 1

Autor do pacote aqui. Sim, seria um desperdício usar mais hashes / bandas do que o necessário. (Lembre-se de que estamos falando de kilobytes aqui, que podem ser muito menores do que os documentos originais.)

A questão é: do que você precisa? Se você precisa encontrar apenas correspondências que sejam quase idênticas (ou seja, com uma pontuação de Jaccard próxima a 1,0), então você não precisa de uma pesquisa particularmente sensível. Se, no entanto, você precisar detectar possíveis correspondências confiáveis ​​que compartilham apenas uma sobreposição parcial (ou seja, com uma pontuação de Jaccard mais próxima de 0), você precisará de mais hashes / bandas.

Já que você leu MMD, você pode procurar a equação lá. Mas há duas funções no pacote, documentadas aqui , que podem ajudá-lo a calcular quantos hashes / bandas você precisa. lsh_threshold()irá calcular o limite de pontuação de Jaccard que será detectado; while lsh_probability()dirá a você a probabilidade de um par de documentos com uma determinada pontuação de Jaccard ser detectado. Brinque com essas duas funções até obter o número de hashes / bandas ideal para o seu problema de pesquisa.