El algoritmo de varias etapas en el análisis de datos

En este artículo, vamos a discutir en detalle el algoritmo de múltiples etapas en el análisis de datos. También cubriremos el funcionamiento de los algoritmos de varias etapas. 

El algoritmo multietapa: el algoritmo multietapa es la versión mejorada del algoritmo PCY que utiliza ciertas tablas hash consecutivas para disminuir aún más el recuento de pares de candidatos. La contradicción en ambos algoritmos es que la multietapa requiere más de dos pasadas para descubrir los pares frecuentes. 

Trabajando en el algoritmo multietapa:

• Primer paso: el primer paso de multietapa es idéntico al primer paso de PCY. Después de ese pase, los cubos frecuentes se identifican y encapsulan mediante un mapa de bits, de nuevo igual que en PCY. Por el contrario, la segunda pasada de multietapa no cuenta las parejas candidatas. Más bien, usa la memoria principal accesible para otra tabla hash, usando otra función hash. Después de todo, el mapa de bits obtenido de la primera tabla hash ocupa 1/32 de la memoria principal accesible, mientras que la segunda tabla hash tiene más o menos tantos cubos como la primera.
• Segundo pase:En el punto de la segunda pasada de multietapa, pasamos de nuevo por la plegadora de cestas. No hay necesidad de contar los elementos de nuevo. El algoritmo multietapa utiliza tablas hash suplementarias para disminuir el número de pares de candidatos. Sin embargo, debemos mantener la información sobre qué elementos son frecuentes, ya que la necesitamos tanto en el segundo como en el tercer pase. Durante el segundo paso, hacemos hash de pares incuestionables de elementos en cubos de la segunda tabla hash. En este segundo pase, verá que un par tiene hash solo si se cuenta en el segundo pase de PCY experimente las dos calidades, y hará hash {i, j} si y solo si i y j ocurren juntos a menudo, y luego, ese par se convierte en hash en un cubo frecuente durante el primer pase. Como resultado, la suma de los conteos en la segunda tabla hash debería ser notablemente menor que la suma del primer paso.
• Paso final: después del segundo paso, la segunda tabla hash también se encapsula como un mapa de bits y ese mapa de bits se almacena en la memoria principal. Los dos mapas de bits juntos ocupan un poco menos de 1/16 de la memoria principal accesible, por lo que todavía hay mucho espacio para contar los pares candidatos en el tercer paso. Un par {i, j} está en C2 si y solo si –
  1. Tanto i como j aparecen en la lista de elementos frecuentes.
  2. El par {i, j} se somete a hash y se transfiere a un depósito frecuente de la primera tabla hash creada.
  3. El par {i, j} se somete a hash y se transfiere a un cubo frecuente de la segunda tabla hash creada.
• La tercera restricción es la divergencia entre multietapa y PCY: podría ser muy claro que es posible encerrar cualquier número de pases entre el primero y el último en el algoritmo multietapa. Hay un factor restrictivo de que cada pase debe reservar los mapas de bits de cada uno de los pases anteriores. A su debido tiempo, no queda suficiente espacio en la memoria principal para hacer los conteos. No afecta la cantidad de pases que aplicamos, los pares sinceramente frecuentes generarán cada vez un cubo frecuente, por lo que no hay forma de evitar contarlos.