algorithm - tres - Algoritmo más rápido para encontrar conjuntos con intersección alta

union de conjuntos (4)

Tengo una gran cantidad de ID de usuario (enteros), potencialmente millones. Todos estos usuarios pertenecen a varios grupos (conjuntos de enteros), de modo que existen del orden de 10 millones de grupos.

Para simplificar mi ejemplo y llegar a la esencia del mismo, supongamos que todos los grupos contienen 20 ID de usuario.

Quiero encontrar todos los pares de conjuntos enteros que tengan una intersección de 15 o mayor.

¿Debo comparar cada par de conjuntos? (Si mantengo una estructura de datos que mapea los ID de usuario para establecer membresía, esto no sería necesario.) ¿Cuál es la forma más rápida de hacer esto? Es decir, ¿cuál debería ser mi estructura de datos subyacente para representar los conjuntos enteros? Conjuntos ordenados, sin clasificar --- ¿puede el hashing de alguna manera ayudar? ¿Y qué algoritmo debería usar para calcular la intersección establecida? Prefiero las respuestas que relacionan C / C ++ (especialmente STL), pero también son bienvenidas las ideas algorítmicas generales.

Actualización También, tenga en cuenta que voy a ejecutar esto en paralelo en un entorno de memoria compartida, por lo que se prefieren las ideas que se extienden limpiamente a una solución paralela.

Además, tenga en cuenta que la gran mayoría de los pares de conjuntos tendrán un tamaño de intersección de 0 --- lo que significa que podría ser ventajoso utilizar una estructura de datos que correlacionara ID de usuario con conjuntos para evitar el cálculo de la intersección de cada par de conjuntos.

¿Debo comparar cada par de conjuntos? (Si mantengo una estructura de datos que mapea los ID de usuario para establecer la membresía, esto no sería necesario).

Para contar el grado de intersección, aún necesita visitar los otros grupos que tiene el usuario, que aún son cúbicos. Podría contar con una tabla hash u otra matriz dispersa para contar, pero de todos modos requeriría un incremento para cada usuario por cada par de grupos en que se encuentre cada usuario. Si tiene N usuarios en grupos G con un promedio de S usuarios por grupo y número de grupos T de cada usuario, tienes G G S / 2 para comparar cada par de grupos y N T T si tienes un índice de usuario para agrupar. T = G S / N, entonces N T T = G G S S / N; para S = 20 y N en millones debería haber una ventaja. Desafortunadamente, también necesita al menos almacenamiento G * G para el recuento de intersecciones (25 TB o más para un contador no disperso de 4 bits), y debe asegurarse de que la estructura se pueda incrementar en paralelo.

Para un millón de usuarios en 10 millones de grupos de 20, aproximadamente la probabilidad de que un usuario esté en un grupo determinado es 2e-6, y la probabilidad de que dos grupos compartan usuarios será 40e-6, por lo que los 25TB se reducen a 1GB datos, por lo que no es imposible para una matriz dispersa en una computadora de tamaño ordinario.

Sin embargo, comparar un conjunto de 20 elementos para 15 elementos en común tiene optimizaciones más obvias

Si los grupos están ordenados, no necesita almacenamiento de trabajo, solo imprima el grado de diferencia entre los grupos de entrada directamente.
La mayoría de los accesos a la memoria serán lineales en las áreas de memoria contigua, y los resultados dependen únicamente de los dos conjuntos que se comparan, en lugar de depender de la suma de todo el conjunto de datos. Acceder a la memoria principal aleatoriamente es significativamente más lento que acceder linealmente. Alterar la memoria principal aleatoriamente con bloqueos de bus es mucho más lenta que acceder a la memoria caché sin necesidad de bloquear el bus (aunque si tiene un par de GB por núcleo, puede usar el enfoque usuario-> grupo sin tener que hacer ninguna sincronización).
Solo necesita contar 5 elementos que son distintos entre los conjuntos; si los datos son aleatorios, la mayoría de los conjuntos serán disjuntos, por lo que la cantidad promedio de elementos visitados es menor.
Puede descontar rápidamente ciertos grupos tratando la diferencia como una distancia (si A es 11 diferente de B, y C es 5 diferente de B, entonces C está entre 6 y 16 diferente de A, por lo que puede descontarse sin comparar A y C directamente). Como la mayoría de los sets son completamente disjuntos, esto no te hará ganar mucho.

También existe la opción de un enfoque híbrido, usando el mapa de usuario-> grupo para podar el conjunto de comparaciones de grupo a grupo que se realizarán. Esto tiene la ventaja de no requerir el incremento de una estructura de datos compartida:

para cada par de grupos en que se encuentra un usuario, agregue ese par a la lista para investigar.
ordene la lista de pares de grupos con al menos un usuario en común.
la cantidad de veces que aparece cada par en la lista es la cantidad de usuarios que tienen en común.

Usando la clasificación por fusión, esto es muy parecido a la paralelización en unidades de transmisión pura. Usted ordenaría alrededor de 20 * 200 * 10 millones / 2 = 20 mil millones de pares de identificación de grupo (cada grupo de 20 usuarios multiplicado por el número de grupos en el que cada usuario está en / 2).

Si la gran mayoría de las intersecciones son 0, eso significa que el número de intersecciones no vacías es relativamente pequeño. Prueba esto:

Bote todos los conjuntos de tamaño <15 antes de comenzar
Calcule su búsqueda desde ID de usuario -> lista de conjuntos a los que pertenece
Crear un map<pair<userset, userset>, int>
Para cada usuario, incremente (después de crear si es necesario), n*(n-1)/2 entradas de ese mapa, donde n es la cantidad de conjuntos a los que pertenece el usuario.
Cuando haya terminado, escanee el mapa para ver las entradas donde el valor es mayor que 15.

Utilizará más memoria que el enfoque simple de computar cada intersección. De hecho, se encontrará con lo que es factible: si cada conjunto se cruza con otros 10, tal vez en intersecciones muy pequeñas, entonces el mapa necesita 50 millones de entradas, lo que comienza a ser una gran cantidad de RAM. También es lamentablemente caché-antipático.

Puede ser más rápido que hacer todas las intersecciones establecidas, porque los términos O (n ^ 2) se relacionan con el número de intersecciones no vacías y la cantidad de grupos a la que pertenece cada usuario, en lugar de con el número de conjuntos.

La paralelización no es trivial, debido a la contención en el mapa gigante. Sin embargo, puede fragmentarlo en un mapa para cada hilo, y periódicamente darle a un hilo un mapa nuevo, vacío, y agregar los resultados hasta ahora en los resultados totales. Los diferentes subprocesos se ejecutan de forma completamente independiente la mayor parte del tiempo, cada uno con una lista de usuarios para procesar.

Una forma es ver su problema como un problema de búsqueda de radio de espacio métrico donde la función de distancia es el número de entradas que no coinciden y el radio es r = max(number of elements in sets) - number of equal . El filtrado de los elementos encontrados es necesario para ver que hay suficientes valores en el Conjunto. Entonces, a menos que alguien se le ocurra una función métrica que pueda usarse directamente, esta solución tiene muchas limitaciones.

Una de las estructuras de datos para la búsqueda de métricas es BK-Tree que se puede usar para búsquedas de similitud de cadenas.

Los candidatos para su problema son VP-tree y M-Trees.

El peor caso para el árbol métrico es O (n ^ 2) cuando busca una distancia> m (número máximo de elementos en los conjuntos) a medida que construye el árbol en O (log n * n) y busca en O (n ^ 2).

Aparte de eso, la complejidad real del tiempo de ejecución depende de la capacidad de podar los subárboles del árbol métrico mientras se ejecuta la búsqueda. En un árbol métrico, se puede omitir un subárbol si la distancia del elemento de pivote al elemento de búsqueda es mayor que el radio del elemento de pivote (que es al menos la distancia máxima de un ancestores al elemento de pivote). Si sus conjuntos de entradas son bastante disjuntos, el tiempo de ejecución general estará dominado por el tiempo de acumulación del árbol de medidas O (log n * n).

Haría exactamente lo que usted propone: asignar usuarios a su grupo. Es decir, mantendría una lista de ID de grupo para cada usuario. Entonces usaría el siguiente algoritmo:

foreach group: map = new Map<Group, int> // maps groups to count foreach user in group: foreach userGroup in user.groups: map[userGroup]++ if( map[userGroup] == 15 && userGroup.id > group.id ) largeIntersection( group, userGroup )

Dado que tiene grupos G que contienen cada uno U usuarios en promedio, y dado que estos usuarios pertenecen a grupos g en promedio, esto se ejecutará en O( G*U*g ) . Lo cual, dado su problema, es probablemente mucho más rápido que la comparación por pares ingenua de grupos que se ejecuta en O(G*G*U) .