Perché textreuse packge in R rende i bucket LSH molto più grandi dei minhash originali?

Aug 16 2020

Per quanto ho capito una delle funzioni principali del metodo LSH è la riduzione dei dati anche oltre gli hash sottostanti (spesso minhash). Ho usato il textreusepacchetto in R e sono sorpreso dalla dimensione dei dati che genera. textreuseè un pacchetto ROpenSci sottoposto a revisione paritaria , quindi presumo che funzioni correttamente, ma la mia domanda persiste.

Supponiamo che io usi 256 permutazioni e 64 bande rispettivamente per le mie funzioni minhash e LSH - valori realistici che vengono spesso utilizzati per rilevare con certezza relativa (~ 98%) somiglianze fino al 50%.

Se eseguo l'hash di un file di testo casuale usando TextReuseTextDocument(256 perm) e lo assegno a trtd, avrò:

object.size(trtd$minhashes)
> 1072 bytes

Ora creiamo i bucket LSH per questo oggetto (64 bande) e assegniamolo a l, avrò:

object.size(l$buckets)
> 6704 bytes

Quindi, gli hash conservati nei bucket LSH sono sei volte più grandi dei minhash originali. Capisco che ciò accada perché textreuse utilizza un digest md5 per creare gli hash del bucket.

Ma non è troppo dispendioso / eccessivo e non posso migliorarlo? È normale che la nostra tecnica di riduzione dei dati finisca per gonfiarsi fino a questo punto? E non è più efficace abbinare i documenti basati sugli hash originali (simili a perm = 256 e bande = 256) e quindi utilizzare una soglia per eliminare i falsi positivi?

Nota che ho rivisto i testi tipici come Mining of Massive Datasets , ma questa domanda rimane su questa particolare implementazione. Si noti inoltre che la domanda non è solo per curiosità, ma piuttosto per necessità. Quando hai milioni o miliardi di hash, queste differenze diventano significative.

Risposte

1 LincolnMullen Aug 17 2020 at 03:24

Autore del pacchetto qui. Sì, sarebbe uno spreco usare più hash / band di quanto ti serva. (Anche se tieni presente che qui stiamo parlando di kilobyte, che potrebbero essere molto più piccoli dei documenti originali.)

La domanda è: di cosa hai bisogno? Se devi trovare solo corrispondenze quasi identiche (cioè con un punteggio Jaccard vicino a 1.0), non hai bisogno di una ricerca particolarmente sensibile. Se, tuttavia, è necessario rilevare in modo affidabile potenziali corrispondenze che condividono solo una sovrapposizione parziale (cioè, con un punteggio Jaccard più vicino a 0), allora sono necessari più hash / bande.

Dato che hai letto MMD, puoi cercare l'equazione lì. Ma ci sono due funzioni nel pacchetto, documentate qui , che possono aiutarti a calcolare quanti hash / bande ti servono. lsh_threshold()calcolerà la soglia di punteggio Jaccard che verrà rilevata; mentre lsh_probability()ti dirà quanto è probabile che venga rilevata una coppia di documenti con un dato punteggio Jaccard. Gioca con queste due funzioni finché non ottieni il numero di hash / bande ottimale per il tuo problema di ricerca.