Encontrar conjuntos que tienen subconjuntos específicos

Question

Soy un estudiante graduado de física y estoy trabajando en escribir un código para clasificar varios cientos de gigabytes de datos y devolver segmentos de esos datos cuando lo solicite. Aquí está el truco, no conozco ningún buen método 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 y n números dentro de ellos (aunque en el 99.9% de los conjuntos, n es menor que 15) y hay aproximadamente 1.5 ~ 2 mil 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.

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 conjuntos:

Por ahora el patrón debería estar claro. La principal diferencia entre este ejemplo y mis datos es que los conjuntos dentro de mis datos son más grandes, los números utilizados para cada elemento de los conjuntos van de 0 a 16383 (14 bits), y hay muchos, muchos, muchos más conjuntos.

Si es importante, estoy escribiendo este programa en C ++, aunque también sé java, c, algún ensamblado, algunos fortran y algunos perl.

¿Alguien tiene alguna pista sobre cómo lograr esto?

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

1.) Los datos no cambian. Todo se tomó en una larga serie de ejecuciones (cada una dividida en 2 archivos de concierto).

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

3.) Cada número dentro de un conjunto procesado 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). Por lo tanto, necesitaré al MENOS tres bytes por número.

4.) Mi " aunque en el 99.9% de los conjuntos, n es menor que 15 " El comentario fue engañoso. En un vistazo preliminar a través de algunos de los fragmentos de 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.) Si bien me gusta la idea de construir un índice de punteros en archivos, soy un poco receloso porque para solicitudes que involucran 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 punteros 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 en bruto en el sistema (El resto de mi cuota en ese sistema). El sistema es un servidor de doble procesador con 2 opterones amd 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.

Answer 1

Recientemente descubrí métodos que usan curvas de relleno de espacio para asignar los datos multidimensionales a una sola dimensión. Entonces se puede indexar los datos en función de su índice 1D. Las consultas de rango se pueden realizar fácilmente al encontrar los segmentos de la curva que se cruzan con el cuadro que representa la curva y luego recuperar esos segmentos.

Creo que este método es muy superior a la creación de los índices locos como se sugiere porque después de mirarlo, el índice sería tan grande como los datos que deseaba almacenar, lo que no es 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/ Publicaciones.html

Answer 2

Su problema es el mismo que enfrentan los motores de búsqueda. " Tengo millones de documentos. Necesito las que contienen este conjunto de palabras. & Quot; Solo 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 Manning et al es (en ese enlace) disponible en línea gratis, es muy legible y entrará en muchos detalles sobre cómo hacerlo.

Tendrá que pagar un precio en el espacio en disco, pero puede ser paralelo y debe ser más que suficiente para cumplir con sus requisitos de tiempo, una vez que se construye el índice.

Answer 3

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.8M conjuntos. ¿Ha considerado (y tiene la capacidad para) construir una tabla de búsqueda 16384x ~ 1.8M (30B entradas, 4 bytes cada una)? Dada una tabla de este tipo, puede consultar qué conjuntos contienen (1) y (17) y (5555) y luego encontrar las intersecciones de esas tres listas de elementos ~ 1.8M.

Answer 4

Mi suposición es la siguiente.

Suponga que cada conjunto tiene un nombre o ID o dirección (un número de 4 bytes servirá 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 los 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 los ID de todos los conjuntos que contienen '3'
• ... etc ...

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

Hará 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
• Abra 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 no debería ser difícil)
• Vea cuál de estos pocos conjuntos satisface el resto de la solicitud

Supongo que si hace lo anterior, la creación de los índices será (muy) lenta y el manejo de las solicitudes será (muy) rápido.

Answer 5

Cree 16383 archivos de índice, uno para cada valor de búsqueda posible. 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 inferior al índice que leyó 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 se distribuyen uniformemente, cada archivo de índice contendrá 1/16383 de los conjuntos de entrada. Si su conjunto de búsqueda promedio consta de 6 valores, realizará un pase lineal sobre 6/16383 de su entrada original. Sigue siendo una solución O (n), pero su n es un poco más pequeña ahora.

P.S. ¿Es cero un valor de resultado imposible, o realmente tiene 1638 posibilidades 4 ?

Answer 6

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

1. Cree un índice con los elementos min, max y no de los conjuntos.
2. Luego aplique fuerza bruta excluyendo conjuntos donde max < max (se busca el conjunto) y min > min (conjunto que se busca)
3. En la fuerza bruta también se excluyen conjuntos, el recuento completo de elementos es menor que el del conjunto que se busca.

El 95% de sus búsquedas serían realmente brutas forzando un subconjunto muy pequeño. Solo un pensamiento.