Estoy trabajando en un algoritmo que necesita calcular el tamaño de un conjunto generado por las intersecciones de al menos 2 conjuntos. Más concretamente:
$$ z = \left |A_0 \cap \ldots \cap A_n \right | $$
Los conjuntos que se cruzan son generados por consultas SQL, y en un esfuerzo por mantener las cosas rápidas, obtengo un recuento de cada consulta por adelantado, luego tomo el conjunto con el menor recuento ( $A_0$ ) y utilizar esos IDs como límites en el resto de las grandes consultas, por lo que la intersección se convierte efectivamente:
$$ z = \left |\left ( A_0 \cap A_1 \right ) \cap \ldots \cap \left ( A_0 \cap A_n \right ) \right | $$
Incluso esta estrategia me deja con algunas consultas bastante grandes para ejecutar, ya que $\left | A_0 \right |$ a veces puede ser grande. Mi idea para tratar esto es tomar una muestra aleatoria de $A_0$ y la intersección con el resto de los conjuntos antes de extrapolar a una estimación adecuada de $z$ . Mi pregunta es: ¿cuál es la mejor manera de realizar el muestreo y luego extrapolar para llegar a un valor de $z$ que, si no es totalmente preciso, tiene un rango de error predecible?
Esto es lo que he probado hasta ahora (en pseudocódigo, más o menos):
sample_threshold := 10000
factor := 1
if (len(A0) > sample_treshold) {
factor = sample_threshold / len(A0)
}
// Take a random sample of size 10000 from A0
// Intersect all the other sets with the A0 sample, then with each other
working_set := A0
for i, a := range A {
a = intersect(A0, a)
working_set = intersect(working_set, a)
}
z := len(working_set) * (1 / factor)
Este código funciona, pero parece sobrestimar sistemáticamente z
con un tamaño de muestra menor que produce una estimación mayor. Además, no estoy seguro de cómo se escalaría esto con más de dos conjuntos para intersecar.
Espero que esta pregunta tenga sentido, dime si puedo aclarar algo más. Además, si esta pregunta está fuera de tema o pertenece a otro lugar, por favor hágamelo saber y estaré encantado de moverla.
Por Comentario de Bill He realizado algunas pruebas rápidas para mostrar el tamaño de la muestra frente al error. Cada cubo de tamaño de muestra se ejecutó 20 veces, y como se puede ver hay una tendencia bastante clara:
0 votos
Creo que un simple muestreo aleatorio sin reemplazo debería funcionar. Me desconcierta que se obtengan sobreestimaciones. Esto parece que se corresponde exactamente con la estimación de la media de la población utilizando la media de la muestra de una muestra aleatoria. Usted está tratando de estimar la probabilidad de la población de que un elemento de $A_0$ está en la intersección de los otros $A$ s. He jugado con un ejemplo sencillo y funciona bien. ¿Qué tan seguro estás de que estás sobreestimando consistentemente? ¿Ha sucedido como 15 veces de 20 o como 150 veces de 200? ¿La muestra es realmente aleatoria?
1 votos
@Bill He añadido un gráfico del tamaño de la muestra frente al error que ilustra lo que estoy viendo. Es más bien 20 veces de 20. En cuanto a la muestra aleatoria, es tan aleatoria como
ORDER BY RAND()
que no es perfecto pero debería ser adecuado para esta tarea.0 votos
@JimmySawczuk ¿No sería mejor simplemente intersecar el "conjunto de trabajo" con "a" directamente, en lugar de "intersect(A0, a)"? Porque "A0" será presumiblemente mayor que el "conjunto de trabajo" actual en el algoritmo después de la primera ejecución... ¿Lo he entendido bien?
0 votos
¿Puede confirmar que se refiere realmente a conjuntos y no a multisets (es decir, que no hay duplicados en los conjuntos)? Porque, si los hay, es fácil sobrestimar el tamaño de la "intersección" con tu método. (Considere el caso de que $A_0$ es una de las 100 copias del mismo elemento y has muestreado la mitad de ellas).
0 votos
¿Puedo preguntar también si el tamaño de la intersección, en relación con el tamaño de los conjuntos originales, es extremadamente pequeño? Si es así, creo que eso explicaría tu problema. He realizado algunas simulaciones (con conjuntos más pequeños) y también estoy obteniendo una sobreestimación bastante consistente, aunque pequeña.
0 votos
@Innuo ese terminó siendo el problema, más o menos. Si quieres escribirlo como respuesta estaré encantado de darte la recompensa. Puede que también escriba algo más detallado sólo para la posteridad.
0 votos
@NotNotLogical con respecto a tu primer comentario, mi pseudocódigo está un poco fuera de lugar porque esa primera intersección ocurre en SQL a través de un
WHERE ... IN (...)
cláusula. Lo he mostrado ahí para completar, pero en realidad es más complejo que eso. En cuanto a tu segundo comentario, hice algunos experimentos, pero el tamaño de la intersección oscilaba entre el 5% y el 80% del original, así que no creo que pueda calificarse de "extremadamente pequeño".