Algoritmo para búsqueda rápida de etiquetas

El problema es el siguiente.

• Hay un conjunto de entidades simples E, cada una con un conjunto de etiquetas T adjuntas. Cada entidad puede tener un número arbitrario de etiquetas. El número total de entidades es cercano a los 100 millones, y el número total de etiquetas es de aproximadamente 5000.

Entonces los datos iniciales son algo como esto:

E1 - T1, T2, T3, ... Tn
E2 - T1, T5, T100, ... Tk
..
Ez - T10, T12, ... Tl

Estos datos iniciales rara vez se actualizan.

• De alguna manera, mi aplicación genera una expresión lógica en etiquetas como esta:

  T1 y T2 y T3 | (T5 y! T6)

• Lo que necesito es calcular un número de entidades que coincidan con la expresión dada (nota: no las entidades, sino solo el número). Este podría no ser totalmente exacto, por supuesto.

Lo que tengo ahora es una simple búsqueda en la tabla en memoria, lo que me da un tiempo de ejecución de 5-10 segundos en un solo hilo.

Tengo curiosidad, ¿hay alguna manera eficiente de manejar estas cosas? ¿Qué enfoque recomendarías? ¿Hay algunos algoritmos comunes o estructuras de datos para esto?

Actualizar

Un poco de aclaración según lo solicitado.

1. Tlos objetos son en realidad cadenas constantes relativamente cortas. Pero en realidad no importa: siempre podemos asignar algunas ID y operar con enteros.
2. Definitivamente podemos ordenarlos.

Lo haría en sql teniendo una tabla de enlaces EntityCategoryentre la eidentidad de cidreferencia y la categoría de referencia utilizando autouniones:

    select count(ec1.eid)
    from EntityCategory ec1 
    left join EntityCategory ec2 on ec1.eid=ec2.eid 
    left join EntityCategory ec3 on ec1.eid=ec3.eid 
    ...
    where 
      ec1.cid={categoryId1} and 
      ec2.cid={categoryId2} and
      ec3.cid={categoryId3} ...

Después de haber escrito esta respuesta, probablemente debería marcar la pregunta como "demasiado amplia": podemos hablar durante años sobre varias estrategias, al final, se tendrá que ejecutar un punto de referencia con sus datos.

Cada etiqueta puede ser representada eficientemente por un número entero. Cada entidad tiene un conjunto de etiquetas. Elegir la implementación correcta del conjunto es importante: son posibles tanto los árboles B como las matrices ordenadas. Con este conjunto, solo haremos pruebas de membresía. Como ambas estructuras hacen esto en O (log t) (con t etiquetas por entidad), preferiría las matrices debido a su representación más densa.

Ahora podemos filtrar a través de todas las entidades en una operación O (n · log t · p) , donde p es la longitud promedio de la ruta en el árbol de decisión del predicado. Este árbol de decisiones se puede ordenar para que se pueda llegar rápidamente a una decisión. Sin datos estadísticos, solo es posible factorizar la subexpresión común.

El orden en que se buscan las entidades no es realmente importante. Por otro lado, puede ser ventajoso para solucionar el problema de tal manera que las entidades en los índices 0a itodos tienen una cierta etiqueta, mientras que el resto no lo hace. Esto reduce la n cuando busca esta etiqueta específica (en el árbol de decisión, esta debería ser la primera prueba). Esto se puede ampliar a múltiples niveles, pero esto complica las cosas y toma memoria O (2 ^k ) con kniveles. Con múltiples niveles, las etiquetas con la ganancia más alta deben decidirse primero, donde la ganancia es el número de entidades que no tienen que buscarse por la probabilidad de descartarlas. La ganancia se vuelve máxima para 50:50 oportunidades o cuando el 50% de las entidades tienen esta etiqueta específica. Esto le permitiría optimizar incluso si no se conocen los patrones de acceso.

También puede crear conjuntos que indexen las entidades por cada etiqueta utilizada: un conjunto con todas las entidades para T1, el siguiente para T2. Una optimización obvia (espacio y tiempo) es detenerse cuando un conjunto contiene más de la mitad de todos los elementos, y guardar aquellos elementos que no tienen esta etiqueta; de esta manera, crear índices para todas las etiquetas tomará menos ½ · n · tespacio (con t etiquetas en total). Tenga en cuenta que guardar conjuntos complementarios puede dificultar otras optimizaciones. De nuevo, haría (ordenado) matrices para los conjuntos.

Si también representa sus entidades a través de un rango entero, puede comprimir el espacio utilizado para los conjuntos de índices almacenando solo el miembro inicial y final de un rango continuo. En cuanto a la implementación, esto probablemente se haría con un bit alto para indicar si una entrada es un rango limitado o una entrada regular.

Si ahora tenemos conjuntos de índices (y, por lo tanto, estadísticas sobre las etiquetas), podemos optimizar nuestros predicados para que las propiedades poco probables se prueben primero (estrategia de falla rápida). Esto significa que si T1es común y T2es raro, entonces el predicado T1 & T2debe evaluarse iterando a través de todas las T2entradas del conjunto de índices y probando cada elemento T1.

Si usamos matrices ordenadas para implementar los conjuntos de índices, muchos pasos de evaluación se pueden implementar como operaciones de fusión. T1 & T2significa que tomamos las listas T1y T2, asignamos una matriz de destino del tamaño de las entradas más grandes y realizamos el siguiente algoritmo hasta que ambas entradas estén vacías: Si T1[0] < T2[0], entonces T1++(descarte la cabeza). Si T1[0] > T2[0]entonces T2++. Si ambas cabezas son iguales, entonces copiar ese número a la matriz de destino, e incrementar los tres punteros ( T1, T2, diana). Si el predicado es T1 | T2, entonces no se descartan elementos, pero se copia el más pequeño. Un predicado del formulario T1 & ¬T2también se puede implementar usando una estrategia de fusión, pero ¬T1o T1 | ¬T2no se puede.

Esto debe tenerse en cuenta al ordenar el árbol de decisión de predicados: los complementos deben ocurrir en el RHS de un &, o al final, cuando se está determinando el recuento final y no es necesario tener en cuenta los elementos reales.

Sin usar conjuntos de índices, cada subproceso puede filtrar a través de su parte de las entidades y devolver el recuento de elementos que coinciden con el predicado, que se pueden resumir. Cuando se usan conjuntos de índices, a cada hilo se le asignará un nodo en el árbol de decisión. Toma dos flujos de entrada que corresponden a los conjuntos ordenados y devuelve un flujo combinado. Observe que cada nodo en el árbol de decisión tiene un conjunto correspondiente que representa todas las entidades que cumplen con esa subexpresión, y que debido al orden de los conjuntos, no es necesario conocer todo el conjunto de una vez para fusionarlos. .

Las diferentes estrategias, como fusionar conjuntos indexados o filtrar a través de una lista de entidades, se pueden combinar hasta cierto punto. El filtrado tiene un rendimiento muy predecible. Si una consulta es muy específica para que el uso de conjuntos de índices reduzca drásticamente el espacio de búsqueda, entonces las operaciones de combinación podrían ser mejores. Es importante tener en cuenta que la combinación de muchos conjuntos de entrada grandes puede resultar en un rendimiento mucho peor que la búsqueda de fuerza bruta. Un algoritmo muy optimizado elegirá una estrategia adecuada basada en el tamaño de entrada, la estructura de consulta y los indicadores estadísticos.

Por otro lado, el almacenamiento en caché de resultados parciales puede ser beneficioso si se espera que se ejecuten consultas similares en el futuro, aunque no aceleren la ejecución inicial.