algorithm - questions - data structures types

¿Existe una estructura de datos probabilísticos para almacenar las relaciones?

Question

Tengo una base de datos con suscripciones de usuarios a temas. Actualmente hay alrededor de 20 000 temas, 20 millones de usuarios y 200 millones de suscripciones almacenadas en la base de datos SQL. Debido a su tamaño, la base de datos está dividida por temas, por lo que no puedo obtener la información en una consulta de base de datos. Hay un par de temas con 10 millones de suscripciones, pareja con 100 000 y otros tienen cientos o menos.

Cuando se produce un evento, por lo general coincide con un par de temas, por lo que para informar a los usuarios, debo realizar una consulta como "darme todos los usuarios suscritos a los temas x, y, z y realizar la unión de conjuntos" para que un usuario reciba la noticia una vez, incluso si suscribió los temas x y z.

Las restricciones son:

• No debe haber duplicados en el conjunto de unión. (los usuarios no pueden obtener el contenido dos veces)
• Puede haber una cantidad limitada de usuarios que faltan en el conjunto de unión. (si a veces el usuario no obtiene el contenido, no es tan malo, pero no puede ser siempre el mismo usuario para el mismo tema)
• Es posible suscribirse a un nuevo tema sin reconstruir todo.

Pensé en usar un conjunto de filtros de bloom para cada tema, pero las restricciones son al revés: "el usuario no está suscrito con certeza o probablemente esté suscrito". Necesito algo como "usuario suscrito con certeza o probablemente no".

Las tablas hash Lossy podrían ser una buena idea, pero no estoy seguro, si pueden ser tan eficientes en memoria como los filtros bloom y me temo, que sería siempre el mismo usuario, que le falta el contenido de su tema.

¿Conoces alguna otra estructura de datos que me sirva para resolver este problema?

Answer 1

¿Qué ocurre si cada registro de usuario tiene un BIT FIELD que representa todos los temas?

TABLE Usuarios (ID INT, Nombre de usuario VARCHAR (16), Temas BINARIO (8000))

Un 8k binario le permitiría tener 64000 temas. Probablemente usaría varias columnas de BINARY (1024) cada una para poder agregar más temas fácilmente.

Ahora cuando viene un evento etiquetado para los temas 1, 10, 20, 30, 40. Tengo que buscar en cada usuario, pero esto se puede paralelizar y siempre será N complejidad, donde N es la cantidad total de usuarios.

SELECT ID 
FROM Users (READPAST)
WHERE 
    SUBSTRING(Topics, 1 / 8, 1) & (1 * POWER(2, (1 % 8))) > 0
    OR
    SUBSTRING(Topics, 10 / 8, 1) & (1 * POWER(2, (10 % 8))) > 0
    OR
    SUBSTRING(Topics, 20 / 8, 1) & (1 * POWER(2, (20 % 8))) > 0
    OR
    SUBSTRING(Topics, 30 / 8, 1) & (1 * POWER(2, (30 % 8))) > 0
    OR
    SUBSTRING(Topics, 40 / 8, 1) & (1 * POWER(2, (40 % 8))) > 0
OPTION (MAXDOP = 64)

• No duplicados escaneamos Usuarios una vez para no tener que preocuparnos por los sindicatos
• Algunos usuarios que carecen de la sugerencia de READPAST omitirán las filas que estén actualmente bloqueadas (actualizándose), por lo que es posible que algunos usuarios no estén en el resultado.
• SUbscribe No puede [un] suscribirse a un tema simplemente alternar el bit de temas en la columna Temas.

Answer 2

Como dije en los comentarios, una solución exacta basada en la memoria es ciertamente factible.

Pero si realmente desea una estructura de datos aproximada, entonces lo que está buscando es un conjunto de tamaño limitado (de usuarios para cada tema) con desalojo aleatorio.

También debe calcular los sindicatos rápidamente sobre la marcha cuando lleguen las consultas. No hay cálculo previo útil aquí. Si los conjuntos de temas tienden a repetirse, puede ver el almacenamiento en caché de las uniones utilizadas con frecuencia.

Se aplican todos los métodos habituales de representar un conjunto. Las tablas hash (tanto cerradas como abiertas), árboles y listas de omisiones (todas contienen claves de identificación de usuario, no se requieren valores) son las más probables.

Si usa una tabla hash cerrada con una buena función hash, el desalojo pseudoaleatorio ocurre automáticamente. En caso de colisión, simplemente reemplace el valor anterior. El problema con los valores hash cerrados siempre es escoger un buen tamaño de tabla para el conjunto que necesita representar. Recuerde que para recuperar los elementos establecidos, tendrá que atravesar toda la tabla abierta, incluidas las entradas nulas, por lo que comenzar con una tabla grande no es una buena idea; en lugar de empezar con uno pequeño y reorganizar, creciendo por un factor cada vez, por lo que la reorganización se amortiza a una sobrecarga de tiempo constante por elemento almacenado.

Con los otros esquemas, puedes literalmente hacer un desalojo pseudoaleatorio cuando la mesa se hace demasiado grande. La forma más fácil de desalojar equitativamente es almacenar el identificador de usuario en una tabla y tener los índices de tienda de conjuntos de tamaño limitado. Expulsa generando un índice aleatorio en la tabla y eliminando esa identificación antes de agregar una nueva.

También es posible desalojar equitativamente de una representación de conjunto de BST utilizando un árbol de estadística de orden : almacenar el número de descendientes en cada nodo. Entonces siempre puedes encontrar el n-ésimo elemento en el orden clave ordenado, donde n es pseudoaleatorio, y desalojarlo.

Sé que estabas buscando la eficiencia espacial bit a bit de un filtro Bloom, pero garantizar que no hay falsos positivos parece descartarlo.

Answer 3

Puede que esta no sea la solución que estaba buscando, pero podría utilizar el filtro de términos de ElasticSearch y tener un documento como este para cada usuario:

{
  "id": 12345,
  "topics": ["Apache", "GitHub", "Programming"]
}

Los filtros de términos responden directamente a la consulta "a la que los usuarios se suscriben al menos a uno de estos temas" y ES es muy inteligente sobre cómo almacenar en caché y volver a utilizar los filtros.

No sería una estructura de datos probabilísticos, pero resolvería muy eficientemente este problema. Tendrá que usar la API de escaneo para serializar la recuperación de respuestas JSON potencialmente grandes. Si es necesario, puede escalar esta solución a miles de millones de usuarios distribuidos en múltiples computadoras y tener tiempos de respuesta como 10 - 100 milisegundos. También podría encontrar correlaciones entre los temas (agregación de términos significativos) y usar ES como motor para un análisis posterior.

Editar : Implementé la búsqueda y el uso de la API de escaneo / sroll en Python y obtuve algunos resultados interesantes. Hice las consultas de "usuarios que se suscriben a tres de estos temas" con los usuarios de 20 my el conjunto de datos de suscripciones de 200 my, en general, la búsqueda finaliza en 4 a 8 milisegundos. Las consultas devuelven 350,000 - 750,000 usuarios.

Los problemas surgen cuando los identificadores de usuario salen de ES, incluso con la API de exploración / desplazamiento. En Core i5, parece obtener solo 8200 usuarios / segundo, por lo que es menos de 0.5 millones / minuto (con "_source": false ). La consulta en sí tiene este aspecto:

{
  "filtered": {
    "filter": {
      "terms": {
        "topics": [ 123, 234, 345 ],
        "execution": "plain",
        "_cache": false
      }
    }
  }
}

En producción, usaría "execution": "bool" para que los resultados de las consultas parciales puedan ser almacenados en caché y reutilizados en otras consultas. No sé cuál es el cuello de botella para obtener resultados, el uso de la CPU del servidor es del 50% y ejecuto la secuencia de comandos python del cliente en la misma máquina, utilizando elasticsearch.helpers.scan .

Answer 4

[Esta solución es similar a la de Louis Ricci, excepto que se invirtió en la tabla Temas, lo que podría hacer que las actualizaciones de suscripción sean menos prácticas, ¡adviértase! ]

(El enfoque de la estructura de datos probabilísticos es genial, pero innecesario para su tamaño de datos actual. Al principio estaba buscando conjuntos de bits comprimidos para una solución no probabilística, ya que son excelentes para realizar operaciones de conjunto en memoria, pero creo que eso es demasiado Bien, aquí hay una buena implementación para este tipo de caso de uso, si le interesa).

Pero al observar la escasez de sus datos, los bitsets desperdician espacio en arreglos enteros. E incluso con arreglos enteros, la operación union sigue siendo bastante económica dado que solo tiene un promedio de 10,000 suscripciones por tema.

Así que tal vez, solo tal vez, una estructura de datos simple-muerta dado su caso de uso es simplemente:

Topic 1 => [array of subscriber IDs]
Topic 2 => [array of subscriber IDs]
...
Topic 20,000 => [array of subscriber IDs]

Almacenar (promedio) 10,000 ID de suscriptor (suponiendo enteros de 32 bits) solo requiere aproximadamente 40kb de espacio por tema.

[En un tipo de matriz o BLOB, dependiendo de su base de datos]

Con 20,000 temas, esto agrega solo 800mb de datos a su tabla de temas ... y muy poco de esto (~ 200kb prom) necesita ser cargado a la memoria cuando ocurre un evento de notificación!

Luego, cuando ocurre un evento promedio (que afecta a 5 temas), todo lo que debe suceder es:

1. Consulta / Extraiga los datos de los temas relevantes (registros promedio 5) en la memoria ( promedio ~ 200kb de E / S)

2. Volcarlos en una estructura de datos establecida (eliminar la lista de suscriptores)

3. Alerta a los suscriptores en el conjunto.