Amplifier un hachage sensible à la localité

J'essaie de créer un hachage sensible aux localités cosinus afin de pouvoir trouver des paires d'articles similaires candidates sans avoir à comparer toutes les paires possibles. Je l'ai essentiellement, mais la plupart des paires de mes données semblent avoir une similitude cosinus dans la plage -0,2 à +0,2, donc j'essaie de le découper assez finement et de choisir des choses avec une similitude cosinus de 0,1 et plus.

J'ai lu le chapitre 3 de Mining Massive Datasets. Il s'agit d'augmenter la précision de la sélection de paires candidates en amplifiant une famille sensible à la localité. Je pense que je comprends à peu près l'explication mathématique, mais j'ai du mal à voir comment je l'implémente pratiquement.

Ce que j'ai jusqu'à présent est le suivant

1. J'ai dit 1000 films chacun avec des notes d'une sélection d'utilisateurs de 1M. Chaque film est représenté par un vecteur épars de scores utilisateur (numéro de ligne = ID utilisateur, valeur = score utilisateur)
2. Je construis N vecteurs aléatoires. La longueur du vecteur correspond à la longueur des vecteurs de film (c'est-à-dire le nombre d'utilisateurs). Les valeurs vectorielles sont +1 ou -1. En fait, j'encode ces vecteurs en binaire pour économiser de l'espace, avec +1 mappé à 1 et -1 mappé à 0
3. Je crée des vecteurs d'esquisse pour chaque film en prenant le produit scalaire du film et chacun des N vecteurs aléatoires (ou plutôt, si je crée une matrice R en posant les N vecteurs aléatoires horizontalement et en les superposant, puis l'esquisse pour le film m est R * m), puis en prenant le signe de chaque élément dans le vecteur résultant, je termine avec un vecteur d'esquisse pour chaque film de + 1s et -1s, que j'encode à nouveau comme binaire. Chaque vecteur a une longueur de N bits.
4. Ensuite, je cherche des croquis similaires en procédant comme suit
   1. J'ai divisé le vecteur d'esquisse en bandes b de bits r
   2. Chaque bande de r bits est un nombre. Je combine ce numéro avec le numéro de bande et ajoute le film à un seau de hachage sous ce numéro. Chaque film peut être ajouté à plusieurs compartiments.
   3. Je regarde ensuite dans chaque seau. Tous les films qui sont dans le même ensemble sont des paires candidates.

En comparant cela à 3.6.3 de mmds, mon étape ET est quand je regarde les bandes de r bits - une paire de films passe l'étape ET si les r bits ont la même valeur. Mon étape OU se produit dans les compartiments: les films sont des paires candidates s'ils sont tous les deux dans l'un des compartiments.

Le livre suggère que je puisse "amplifier" mes résultats en ajoutant plus d'étapes ET et OU, mais je ne sais pas comment le faire pratiquement car l'explication du processus de construction pour d'autres couches consiste à vérifier l'égalité par paire plutôt que venir avec des numéros de seau.

Quelqu'un peut-il m'aider à comprendre comment procéder?

Je pense que j'ai travaillé sur quelque chose. Fondamentalement, je recherche une approche qui fonctionne dans un environnement de type carte / réduction et je pense que cette approche le fait.

Donc,

• supposons que j'ai b bandes de r lignes et que je veuille ajouter une autre étape ET, disons encore c ET.
• donc au lieu de b * r bits j'ai besoin de hachages de b * r * c bits
• et je lance ma procédure précédente c fois, à chaque fois sur b * r bits
• Si x et y s'avèrent être une paire candidate par l'une de ces procédures, il émet une paire de valeurs de clé ((x, y), 1), avec le tuple d'ID (x, y) comme clé et la valeur 1
• À la fin des procédures c, je regroupe ces paires par clé et somme
• Toute paire (x, y) avec une somme égale à c était une paire candidate dans chacun des c tours, tout comme une paire candidate de toute la procédure.

Alors maintenant, j'ai une solution viable, et tout ce que je dois faire est de savoir si l'utilisation de 3 étapes comme celle-ci m'aidera réellement à obtenir un meilleur résultat avec moins de bits de hachage globaux ou de meilleures performances globales ...

J'aurais juste commenté mais je ne peux pas. Je cherchais un traitement pratique de l'amplification en LSH et ce que vous avez présenté a beaucoup de sens. D'après ce que je comprends, la fonction de hachage principale estpour un vecteur aléatoire , après le ET cela devient , et enfin après le OU, ouMaintenant, vous pouvez ET / OU en utilisant

$$h(x,v)=\left\{ \begin{array}{ll}0 & \mbox{if }\textrm{sgn}(x\cdot v) < 0\\ 1 & \mbox{else}\end{array} \right.$$ $v$$h'(x,i) = (h(x,v_{i+1}),...,h(x,v_{i+r}))$$h''(x,j) =f(h'(x,rj),j)$ $$h''(x,y) =\left\{ \begin{array}{ll}1 & \mbox{if }h''(x,j) = h''(y,j) \mbox{ for any }j \in [0,b)\\ 0 & \mbox{else}\end{array} \right.$$ $h''(x,y)$comme vous le décrivez. Vous choisiriez alors simplement des candidats sur la base d'énoncés logiques ET / OU; vous ne hachez plus vraiment. À ce stade, pour continuer le hachage, vous auriez besoin d'un mappage des bacs de sorte que chaque vecteur n'apparaisse qu'une fois dans , mais cela introduira probablement des faux positifs et / ou négatifs. Une idée pour une table de hachage est le minimum de pour tout (ou le minimum dans l' ensemble et toutes associées directement ou indirectement ). Les deux introduiraient clairement un biais. Je pourrais essayer l'un d'entre eux, mais je ne suis pas sûr que les hachages d'un ET / OU aléatoire seront significatifs la prochaine fois.$\hat{h}:S\to S'$$S'$$h''(x,j)$$j$$j$$y$$v$ et un grand nombre de réplications, peut-être?