Arquitectura MySQL para n * (n - 1)/2 algoritmo

Question

Actualmente estoy desarrollando un sitio web donde los usuarios pueden buscar a otros usuarios según los atributos (edad, altura, ciudad, educación, etc.). Ahora quiero implementar algún tipo de calificación entre los perfiles de usuario. La calificación se calcula a través de su propio algoritmo basado en la similitud entre los 2 perfiles dados. El usuario A tiene una calificación de "clasificación de coincidencia" de 85 con el usuario B y 79 con el usuario C, por ejemplo. B y C tienen una calificación de 94 y así sucesivamente ....

El usuario debe poder buscar ciertos atributos y filtrar los resultados por calificación.

Dado que la clasificación difiere de un perfil a otro y también depende del usuario que realiza la búsqueda, no puedo simplemente agregar un campo a la tabla de mis usuarios y usar ORDER BY. Hasta el momento se me ocurrió con 2 soluciones:

• Mi primera solución era tener un trabajo por lotes todas las noches, que calcula la calificación para cada combinación posible de usuarios y lo almacena en una tabla separada (usuario1, usuario2 valoraciones) . Entonces puedo unirme a esta tabla con la tabla de usuarios y ordenar el resultado por clasificación. Después de hacer algunas matemáticas, pensé que esta solución no se escalaría tan bien.

  Según la fórmula n * (n - 1)/2 hay 45 combinaciones posibles para 10 usuarios. Para 1.000 usuarios, de repente tengo que insertar 499.500 combinaciones de calificación en mi tabla de clasificación.

• La segunda solución fue dejar MySQL y simplemente calcular la calificación sobre la marcha dentro de mi aplicación. Esto tampoco se escala bien. Digamos que la búsqueda solo debe devolver 100 resultados a la IU (con la calificación más alta en la parte superior). Si tengo 10.000 usuarios y deseo hacer una búsqueda para cada usuario que vive en Nueva York ordenado por clasificación, tengo que cargar TODOS los usuarios que viven en Nueva York en mi aplicación (digamos 3.000), aplicar el algoritmo y luego regresar solo los 100 mejores para el usuario. De esta forma cargué 2.900 objetos de usuario inútiles de la base de datos y desperdicié CPU en el algoritmo sin hacer nada con él.

Alguna idea de cómo puedo diseñar esto en mi db MySQL o aplicación web para que un usuario puede tener una calificación individual con cada otro usuario de manera que el sistema de escalas más allá de un par de miles de usuarios?

Answer 1

Si tiene que hacer coincidir cada usuario con cada otro usuario, el algoritmo es O (N^2), haga lo que haga.

Si puede explotar algún tipo de "métrica" ​​unidimensional, puede intentar asociar a cada usuario con un único valor sintético. Pero eso es incómodo y podría ser imposible.

Pero lo que puede hacer es observar qué usuarios requieren cambiar en sus perfiles (siempre que cualquiera de los parámetros en los que se basa la coincidencia, cambie). En ese punto, puede recalcular por lotes la tabla para esos usuarios solamente, trabajando así en O (N): si tiene 10000 usuarios y solo 10 requieren un nuevo cálculo, debe examinar 100,000 registros en lugar de 100,000,000.

Otras estrategias serían ejecutar solo el algoritmo principal para los registros que tienen una mayor probabilidad de comparación: en su ejemplo, "la misma ciudad". O al actualizar registros (pero esto requeriría almacenar (user_1, user_2, ranking, last_calculated), solo recalcular esos registros con alta clasificación, muy antiguos o nunca calculados. Las coincidencias de menor clasificación probablemente no cambien tanto que floten a la cima en un corto tiempo.

ACTUALIZACIÓN

El problema también está operando con O (N^2) de espacio de almacenamiento .

Cómo reducir este espacio? Creo que puedo ver dos enfoques. Uno es no ponga algo de información en la tabla de coincidencias en total. La función de "coincidencia" tiene más sentido cuanto más rígida y empinada; tener diez mil "buenas coincidencias" significaría que que coincida con significa muy poco. Por lo tanto, aún necesitaríamos muchos cálculos cuando el Usuario1 cambia algunos datos clave, en caso de que traiga algunas de las coincidencias "no-no" del Usuario1 de regreso a la zona "tal vez". Pero mantendríamos una camarilla más pequeña de coincidencias activas para cada usuario.

El almacenamiento aún crecerá de forma cuadrática, pero con menos pendiente.

Otra estrategia sería recalcular el partido, y luego tendría que desarrollar algún método para seleccionar rápidamente el que los usuarios son propensos a tener un buen partido (lo que limita el número de filas recuperadas por el JOIN), y algún método para calcular rápidamente una coincidencia; lo que podría implicar reescribir de alguna manera la coincidencia entre User1 y User2 a una función muy simple de un subconjunto de DataUser1, DataUser2 (quizás utilizando columnas auxiliares).

El desafío sería aprovechar las capacidades de MySQL y descargar algunos cálculos del motor MySQL.

Para este propósito, es posible que pueda "asignar" algunos datos, en el tiempo de entrada (por lo tanto en O (k)), a la información espacial, o a cadenas y emplear la distancia Levenshtein.

El almacenamiento para un solo usuario aumentaría, pero crecería linealmente, no en forma cuadrática, y los índices SPATIAL de MySQL son muy eficientes.

Answer 2

Estoy de acuerdo con todo @Iserni dice.

Si tiene una aplicación web y los usuarios necesitan "iniciar sesión", entonces puede tener la oportunidad de crear los rankings de ese usuario en ese momento y esconderlos en una tabla temporal (o filas en una tabla existente).

Esto funcionará en un período de tiempo razonable (unos pocos segundos) si todos los datos necesarios para el cálculo se ajustan a la memoria. El motor de la base de datos debería realizar un escaneo completo de la tabla y crear todas las clasificaciones.

Esto debería funcionar razonablemente bien para un usuario que inicia sesión. Pasablemente para dos. . . pero no va a escalar muy bien si tiene, por ejemplo, una docena de usuarios que inician sesión en un segundo.

Fundamentalmente, su calificación no se escala bien. Debe hacer una comparación de todos los usuarios con todos los usuarios para obtener los resultados. Si esto es por lotes (por la noche) o en tiempo real (cuando alguien tiene una consulta) no cambia la naturaleza del problema. Va a utilizar muchos recursos de computación, y múltiples usuarios haciendo solicitudes al mismo tiempo serán un cuello de botella.

Answer 3

Si la búsqueda solo devuelve las 100 mejores coincidencias, ¿por qué no almacenarlas? Parece que nunca querrá buscar el final de los resultados, así que no los calcule.

De esta manera, su espacio de almacenamiento es solamente o (n), en lugar de o (n^2), y las actualizaciones también deberían serlo.Si alguien realmente quiere ver las coincidencias más allá de los primeros 100 (y desea dejarlas), entonces tiene la opción de ejecutar la consulta en tiempo real en ese momento.