Pourquoi textreuse packge dans R rend les seaux LSH bien plus grands que les minhashes d'origine?

Question

Autant que je sache, l'une des principales fonctions de la méthode LSH est la réduction des données même au-delà des hachages sous-jacents (souvent des minhashes). J'utilise le textreusepackage dans R, et je suis surpris par la taille des données qu'il génère. textreuseest un package ROpenSci évalué par des pairs , donc je suppose qu'il fait son travail correctement, mais ma question persiste.

Disons que j'utilise respectivement 256 permutations et 64 bandes pour mes fonctions minhash et LSH - des valeurs réalistes souvent utilisées pour détecter avec une certitude relative (~ 98%) des similitudes aussi basses que 50%.

Si je hache un fichier texte aléatoire en utilisant TextReuseTextDocument(256 perms) et que je l'attribue à trtd, j'aurai:

object.size(trtd$minhashes)
> 1072 bytes

Créons maintenant les buckets LSH pour cet objet (64 bandes) et assignons-le l, j'aurai:

object.size(l$buckets)
> 6704 bytes

Ainsi, les hachages conservés dans les seaux LSH sont six fois plus grands que les minhashs d'origine. Je comprends que cela se produit car textreuse utilise un condensé md5 pour créer les hachages de compartiment.

Mais n'est-ce pas trop gaspilleur / excessif, et ne puis-je pas l'améliorer? Est-il normal que notre technique de réduction des données finisse par gonfler à ce point? Et n'est-il pas plus efficace de faire correspondre les documents basés sur les hachages d'origine (similaires à perms = 256 et bandes = 256), puis d'utiliser un seuil pour éliminer les faux positifs?

Notez que j'ai passé en revue les textes typiques tels que l' extraction d'ensembles de données massifs , mais cette question demeure sur cette implémentation particulière. Notez également que la question n'est pas seulement par curiosité, mais plutôt par nécessité. Lorsque vous avez des millions ou des milliards de hachages, ces différences deviennent significatives.

Answer 1

Auteur du package ici. Oui, il serait inutile d'utiliser plus de hachages / bandes que vous n'en avez besoin. (Gardez à l'esprit que nous parlons ici de kilo-octets, ce qui pourrait être beaucoup plus petit que les documents originaux.)

La question est, de quoi avez-vous besoin? Si vous avez besoin de ne trouver que des correspondances presque identiques (c'est-à-dire avec un score Jaccard proche de 1,0), vous n'avez pas besoin d'une recherche particulièrement sensible. Si, cependant, vous avez besoin de détecter de manière fiable des correspondances potentielles qui ne partagent qu'un chevauchement partiel (c'est-à-dire avec un score Jaccard plus proche de 0), alors vous avez besoin de plus de hachages / bandes.

Puisque vous avez lu MMD, vous pouvez y rechercher l'équation. Mais il y a deux fonctions dans le package, documentées ici , qui peuvent vous aider à calculer le nombre de hachages / bandes dont vous avez besoin. lsh_threshold()calculera le score seuil Jaccard qui sera détecté; while lsh_probability()vous dira quelle est la probabilité qu'une paire de documents avec un score Jaccard donné soit détectée. Jouez avec ces deux fonctions jusqu'à obtenir le nombre de hachages / bandes optimal pour votre problème de recherche.