Amplificación de un hash local sensible

Estoy tratando de construir un hash sensible a la localidad coseno para poder encontrar pares de artículos similares candidatos sin tener que comparar cada par posible. Básicamente funciona, pero la mayoría de los pares en mis datos parecen tener una similitud de coseno en el rango de -0.2 a +0.2, así que estoy tratando de cortarlo con precisión y elegir cosas con una similitud de coseno 0.1 y superior.

He estado leyendo el capítulo 3. Conjuntos de datos masivos de minería. Habla de aumentar la precisión de la selección de pares de candidatos amplificando una familia sensible a la localidad. Creo que casi entiendo la explicación matemática, pero me cuesta ver cómo implemento esto prácticamente.

Lo que tengo hasta ahora es el siguiente

1. Tengo 1000 películas cada una con calificaciones de una selección de 1 millón de usuarios. Cada película está representada por un vector escaso de puntajes de usuario (número de fila = ID de usuario, valor = puntaje de usuario)
2. Construyo N vectores aleatorios. La longitud del vector coincide con la longitud de los vectores de la película (es decir, el número de usuarios). Los valores del vector son +1 o -1. En realidad, codifico estos vectores como binarios para ahorrar espacio, con +1 asignado a 1 y -1 asignado a 0
3. Construyo vectores de croquis para cada película tomando el producto escalar de la película y cada uno de los N vectores aleatorios (o mejor dicho, si creo una matriz R colocando los N vectores aleatorios horizontalmente y superponiéndolos uno encima del otro, entonces el croquis para la película m es R * m), luego tomo el signo de cada elemento en el vector resultante, así que termino con un vector de boceto para cada película de + 1s y -1s, que nuevamente codifico como binario. Cada vector tiene una longitud de N bits.
4. Luego busco bocetos similares haciendo lo siguiente
   1. Dividí el vector de croquis en b bandas de r bits
   2. Cada banda de r bits es un número. Combino ese número con el número de banda y agrego la película a un cubo de hash debajo de ese número. Cada película se puede agregar a más de un cubo.
   3. Luego miro en cada cubo. Cualquier película que esté en el mismo grupo son pares de candidatos.

Comparando esto con 3.6.3 de mmds, mi paso AND es cuando miro bandas de r bits: un par de películas pasan el paso AND si los bits r tienen el mismo valor. Mi paso OR ocurre en los grupos: las películas son pares de candidatos si ambos están en alguno de los grupos.

El libro sugiere que puedo "amplificar" mis resultados agregando más pasos AND y OR, pero no sé cómo hacerlo prácticamente, ya que la explicación del proceso de construcción para capas adicionales es en términos de verificar la igualdad por pares en lugar de proponiendo números de cubo.

¿Alguien puede ayudarme a entender cómo hacer esto?

Creo que he resuelto algo. Básicamente estoy buscando un enfoque que funcione en un entorno de tipo mapa / reducción y creo que este enfoque lo hace.

Entonces,

• supongamos que tengo b bandas de r filas y quiero agregar otra etapa AND, digamos otras c AND.
• así que en lugar de bits b * r necesito hashes de bits b * r * c
• y ejecuto mi procedimiento anterior c veces, cada vez en bits b * r
• Si se descubre que xey son un par candidato mediante cualquiera de estos procedimientos, emite un par de valores clave ((x, y), 1), con la tupla de ID (x, y) como clave y el valor 1
• Al final de los procedimientos c, agrupo estos pares por clave y suma
• Cualquier par (x, y) con una suma igual a c fue un par candidato en cada una de las r rondas, y también lo es un par candidato de todo el procedimiento.

Así que ahora tengo una solución viable, y todo lo que necesito hacer es determinar si usar 3 pasos como este realmente me ayudará a obtener un mejor resultado con menos bits de hash generales o un mejor rendimiento general ...

$$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 : S → S ' S ' h " ( x , j ) j j y $h''(x,y)$$\hat{h}:S\to S'$$S'$, pero al hacerlo también es probable que presente falsos positivos y / o negativos. Una idea para un hash es el mínimo de para todos (o el mínimo en todos los y todos asociados directa e indirectamente ). Ambos claramente introducirían prejuicios. Podría intentar uno de estos, aunque no estoy seguro de que los hashes de un AND / OR aleatorio sean significativos la próxima vez. Pero teniendo en cuenta una distribución uniforme de aleatorio y un gran número de repeticiones, ¿tal vez?$h''(x,j)$$j$$j$$y$$v$