algorithm - subconjuntos - teoria de conjuntos pdf

Encontrar conjuntos que tienen subconjuntos específicos (6)

Soy un estudiante graduado de física y estoy trabajando en la escritura de un código para ordenar varios cientos de gigabytes de datos y devolver partes de esos datos cuando los solicite. Este es el truco, no conozco ningún método bueno para ordenar y buscar datos de este tipo.

Mis datos consisten esencialmente en una gran cantidad de conjuntos de números. Estos conjuntos pueden contener entre 1 yn números dentro de ellos (aunque en el 99.9% de los conjuntos, n es menor que 15) y hay aproximadamente 1.5 ~ 2.000 millones de estos conjuntos (desafortunadamente este tamaño impide una búsqueda de fuerza bruta).

Necesito poder especificar un conjunto con k elementos y tener cada conjunto con k + 1 elementos o más que contenga el subconjunto especificado devuelto a mí.

Ejemplo simple:
Supongamos que tengo los siguientes conjuntos para mis datos:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

Si tuviera que dar la solicitud (1,3) tendría los conjuntos: (1,2,3), (1,2,3,4,5) y (1,3,8,9).
La solicitud (11) devolvería el conjunto: (5,8,11).
La solicitud (1,2,3) devolvería los conjuntos: (1,2,3) y (1,2,3,4,5)
La solicitud (50) no devolvería ningún conjunto:

Por ahora, el patrón debe ser claro. La principal diferencia entre este ejemplo y mis datos es que los conjuntos con mis datos son más grandes, los números utilizados para cada elemento de los conjuntos se ejecutan desde 0 hasta 16383 (14 bits), y hay muchos muchos más conjuntos.

Si es importante, estoy escribiendo este programa en C ++, aunque también conozco java, c, algún ensamblado, algún fortán y algún perl.

¿Alguien tiene alguna pista sobre cómo llevarlo a cabo?

editar:
Para responder un par de preguntas y agregar algunos puntos:

1.) Los datos no cambian. Todo fue tomado en un largo conjunto de ejecuciones (cada una dividida en dos archivos de concierto).

2.) En cuanto al espacio de almacenamiento. Los datos brutos ocupan aproximadamente 250 gigabytes. Estimo que después de procesar y eliminar una gran cantidad de metadatos extraños que no me interesan podría reducirlos a 36 u 48 gigabytes dependiendo de la cantidad de metadatos que decida mantener (sin índices). Además, si en mi procesamiento inicial de los datos encuentro suficientes conjuntos que son los mismos, es posible que pueda consultar los datos aún más agregando contadores para repetir eventos en lugar de simplemente repetir los eventos una y otra vez.

3.) Cada número dentro de un conjunto procesado realmente contiene al menos dos números 14 bits para los datos en sí (energía detectada) y 7 bits para los metadatos (número de detector). Entonces necesitaré al menos tres bytes por número.

4.) Mi "aunque en el 99.9% de los conjuntos, n es menos de 15", el comentario fue engañoso. En una mirada preliminar a través de algunos de los datos, encuentro que tengo conjuntos que contienen hasta 22 números, pero la mediana es de 5 números por conjunto y el promedio es de 6 números por conjunto.

5.) Aunque me gusta la idea de crear un índice de punteros en archivos, estoy un poco receloso porque para las solicitudes que involucran a más de un número me queda la tarea semi lenta (al menos creo que es lenta) de encontrar el conjunto de todos los indicadores comunes a las listas, es decir, encontrar el mayor subconjunto común para un número determinado de conjuntos.

6.) En términos de recursos disponibles para mí, puedo reunir aproximadamente 300 gigas de espacio después de tener los datos brutos en el sistema (El resto de mi cuota en ese sistema). El sistema es un servidor de doble procesador con 2 núcleos de corriente alterna de cuatro núcleos y 16 gigabytes de ram.

7.) Sí 0 puede ocurrir, es un artefacto del sistema de adquisición de datos cuando ocurre, pero puede ocurrir.

Cree archivos de índice 16383, uno para cada posible valor de búsqueda. Para cada valor en su conjunto de entrada, escriba la posición del archivo del inicio del conjunto en el archivo de índice correspondiente. Es importante que cada uno de los archivos de índice contenga el mismo número para el mismo conjunto. Ahora cada archivo de índice consistirá en índices ascendentes en el archivo maestro.

Para buscar, comience a leer los archivos de índice correspondientes a cada valor de búsqueda. Si lee un índice que es más bajo que el índice que lee de otro archivo, deséchelo y lea otro. Cuando obtiene el mismo índice de todos los archivos, eso es una coincidencia: obtenga el conjunto del archivo maestro y lea un nuevo índice de cada uno de los archivos de índice. Una vez que llegue al final de cualquiera de los archivos de índice, habrá terminado.

Si sus valores están distribuidos uniformemente, cada archivo de índice contendrá 1/16383 de los conjuntos de entrada. Si su conjunto de búsqueda promedio consta de 6 valores, hará un pase lineal sobre 6/16383 de su entrada original. Sigue siendo una solución O (n), pero tu n es un poco más pequeña ahora.

PS: ¿Es cero un valor de resultado imposible o realmente tienes 1638 4 posibilidades?

Mi suposición es la siguiente.

Supongamos que cada conjunto tiene un nombre o ID o dirección (un número de 4 bytes funcionará si solo hay 2 mil millones de ellos).

Ahora recorra todos los conjuntos una vez y cree los siguientes archivos de salida:

Un archivo que contiene las ID de todos los conjuntos que contienen ''1''
Un archivo que contiene los ID de todos los conjuntos que contienen ''2''
Un archivo que contiene las ID de todos los conjuntos que contienen ''3''
... etc ...

Si hay 16 entradas por conjunto, en promedio cada uno de estos archivos 2 ^ 16 contendrá los ID de 2 ^ 20 conjuntos; con cada ID de 4 bytes, esto requeriría 2 ^ 38 bytes (256 GB) de almacenamiento.

Harás lo anterior una vez, antes de procesar las solicitudes.

Cuando reciba solicitudes, use estos archivos de la siguiente manera:

Mira un par de números en la solicitud
Abre un par de los archivos de índice correspondientes
Obtenga la lista de todos los conjuntos que existen en ambos archivos (solo hay un millón de ID en cada archivo, por lo que esto no debería ser difícil)
Vea cuáles de estos pocos conjuntos satisfacen el resto de la solicitud

Supongo que si haces lo anterior, crear los índices será (muy) lento y las solicitudes de manejo serán (muy) rápidas.

Simplemente jugando al defensor del diablo para un enfoque que incluye la fuerza bruta + búsqueda de índice:

Crea un índice con min, max y no de elementos de conjuntos.
A continuación, aplique la fuerza bruta excluyendo los conjuntos donde max <max (conjunto que se busca) y min> min (conjunto que se busca)
En la fuerza bruta también se excluyen los conjuntos. El recuento de elementos completos es menor que el del conjunto que se busca.

El 95% de tus búsquedas realmente sería un forzado bruto forzando un subconjunto muy pequeño. Solo un pensamiento.

Suponiendo una distribución aleatoria de 0-16383, con 15 elementos consistentes por conjunto y dos mil millones de conjuntos, cada elemento aparecería en aproximadamente 1,8 millones de conjuntos. ¿Ha considerado (y tiene la capacidad para) construir una tabla de búsqueda 16384x ~ 1.8M (30B entradas, 4 bytes cada una)? Dada dicha tabla, puede consultar qué conjuntos contienen (1) y (17) y (5555) y luego encontrar las intersecciones de esas tres listas de elementos ~ 1.8M.

Tu problema es el mismo que enfrentan los motores de búsqueda. "Tengo un bajillon de documentos. Necesito los que contienen este conjunto de palabras". Simplemente tiene (muy convenientemente) enteros en lugar de palabras y documentos pequeños. La solución es un índice invertido . Introducción a la recuperación de información por parte de Manning et al. (En ese enlace), disponible en línea, es muy legible y detallará cómo hacerlo.

Tendrá que pagar un precio en el espacio en disco, pero puede ser paralelizado y debe ser más que lo suficientemente rápido para cumplir con los requisitos de tiempo, una vez que se haya construido el índice.

Recientemente descubrí métodos que usan curvas de relleno espacial para asignar los datos multidimensionales a una única dimensión. Uno puede indexar los datos según su índice 1D. Las consultas de rango se pueden realizar fácilmente al encontrar los segmentos de la curva que intersectan el cuadro que representa la curva y luego recuperar esos segmentos.

Creo que este método es muy superior a hacer los índices locos como se sugirió porque, después de verlo, el índice sería tan grande como los datos que deseaba almacenar, apenas algo bueno. Una explicación algo más detallada de esto se puede encontrar en:

http://www.ddj.com/184410998
y
http://www.dcs.bbk.ac.uk/~jkl/publications.html