La forma más rápida de realizar una operación de prueba de subconjuntos en una gran colección de conjuntos con el mismo dominio

Question

Supongamos que tenemos billones de conjuntos almacenados en alguna parte. El dominio para cada uno de estos conjuntos es el mismo. También es finito y discreto. Por lo tanto, cada conjunto puede almacenarse como un campo de bits (p. Ej .: 0000100111 ...) de una longitud relativamente corta (p. Ej .: 1024). Es decir, el bit X en el campo de bits indica si el elemento X (de 1024 elementos posibles) está incluido en el conjunto dado o no.

Ahora, quiero diseñar una estructura de almacenamiento y un algoritmo para responder eficientemente a la consulta: lo que los conjuntos en el almacén de datos han establecido Y como un subconjunto. El conjunto Y no está presente en el almacén de datos y se especifica en tiempo de ejecución.

Ahora, la forma más simple de resolver esto sería AND Y el campo de bits para el conjunto Y con campos de bits de cada conjunto en el almacén de datos uno por uno, seleccionando aquellos cuyo resultado Y coincida con el campo de bits de Y.

¿Cómo puedo acelerar esto? ¿Existe una estructura de árbol (índice) o algún algoritmo inteligente que me permita realizar esta consulta sin tener que ANDAR cada campo de bit del conjunto almacenado?

¿Existen bases de datos que ya admitan tales operaciones en grandes colecciones de conjuntos?

Answer 1

Tiendo a decir que la respuesta es no, debido al campo de bit muy baja cardinalidad.

Answer 2

Esto sería un tramo en un RDBMS convencional basado en su volumen, ¿ha mirado en Neo4j que se basa en un modelo de almacenamiento de gráficos?

Answer 3

Si puede preprocesar los conjuntos, la relación del subconjunto es representable como un DAG (porque está describiendo un poset). Si se calcula la reducción transitiva, entonces creo que puede evitar probar todos los conjuntos simplemente realizando un DFS comenzando desde los conjuntos más grandes y deteniéndose cuando Y ya no sea un subconjunto del conjunto actual que se está visitando.

Answer 4

Dependiendo de la cardinalidad del conjunto del que se extraen todos los conjuntos, una opción podría ser construir un mapeo de índice invertido desde los elementos hasta los conjuntos que los contienen. Dado un conjunto Y, podría encontrar todos los conjuntos que tienen Y como un subconjunto al encontrar todos los conjuntos que contienen cada elemento individualmente y calcular su intersección. Si almacena las listas en orden ordenado (por ejemplo, enumerando todos los conjuntos en su base de datos con los valores 0, 1, etc.), entonces debería poder calcular esta intersección de manera bastante eficiente, suponiendo que ningún elemento está contenido en muchos juegos

Answer 5

Un vistazo rápido me hace pensar en BDD, que es algo similar a la idea de la solución DAG. Alternativamente un ZDD.

Answer 6

Si un RDBMS era su única opción, recomiendo buscando en este interesante artículo en el modelado de un DAG en SQL:

http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx?msg=3051183

Si usted no puede permitirse Oracle o MSSQL, echar un vistazo a PostgresQL 9, que admite consultas recursivas. También es compatible con Cross Joins durante bastante tiempo.