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

Question

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 tienen 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 Además, nótese que va a correr 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 pares de pares 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 calcular la intersección de cada par de conjuntos.

Answer 1

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. A continuación, me gustaría utilizar 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 G grupos que contienen cada uno U usuarios en promedio, y teniendo en cuenta que estos usuarios pertenecen a grupos g en promedio, entonces esto va a funcionar en O(G*U*g). Lo cual, dado su problema, es probablemente mucho más rápido que la comparación de grupos ingenua por parejas que se ejecuta en O(G*G*U).

Answer 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. Seguirlo:

• Tire a la basura todos los conjuntos de tamaño < 15 antes de empezar
• Calcula tu búsqueda desde identificador de usuario -> lista de juegos a los que pertenece
• Crear una 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 el número de conjuntos a los que pertenece el usuario.
• Cuando esto esté terminado, escanear el mapa de entradas donde el valor es mayor que 15.

Se utilizará más memoria que el enfoque simple de calcular 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.

Podría 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 el número de grupos al que pertenece cada usuario, en lugar del 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.

Answer 3

Una forma es ver su problema como metric spaceradio de búsqueda problema en el que la función de distancia es el número de entradas que no coincidan 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.

Candidates for your problem 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 busque 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 de métricas 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).

Answer 4

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

Con el fin de contar el grado de intersección, usted todavía tiene que visitar los otros grupos que tiene el usuario, que es aún cúbico 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, tiene G G S/2 para comparar cada par de grupos y N T T si tiene 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, muy 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, entonces los 25TB se reduce a 1 GB de datos, por lo que no es imposible para una matriz dispersa en una computadora de tamaño normal.

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

• Si se clasifican los grupos, que no requieren almacenamiento de trabajo, la salida sólo el grado de diferencia entre los grupos de entrada directamente.
• La mayoría de los accesos a memoria serán lineales en áreas de memoria contigua, y los resultados dependen solo de los dos conjuntos que se comparan, en lugar de depender de la suma en 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 es necesario 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 se puede descontar 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, utilizando el mapa usuario-> grupo para podar el conjunto de las comparaciones de grupo a grupo que se realizarán. Esto tiene la ventaja de no requerir el incremento de una estructura de datos compartida:

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

Usando el tipo de fusión, esto es muy parecido a cada uno para paralelizar 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).