Los histogramas se utilizan con mayor frecuencia como representaciones visuales de datos. Sin embargo, los sistemas de bases de datos utilizan histogramas para resumir datos internamente y proporcionar estimaciones de tamaño para consultas . Estos histogramas no se presentan a los usuarios ni se muestran visualmente, por lo que hay una gama más amplia de opciones disponibles para su construcción. Los histogramas simples o exóticos se definen mediante cuatro parámetros: valor de ordenación, valor de origen, clase de partición y regla de partición. El histograma más básico es el histograma de ancho igual, donde cada segmento representa el mismo rango de valores. Ese histograma se definiría como que tiene un valor de ordenación de Valor, un valor de origen de Frecuencia, está en la clase de partición serial y tiene una regla de partición que indica que todos los segmentos tienen el mismo rango.
Los histogramas V-óptimos son un ejemplo de un histograma más "exótico". La V-optimalidad es una regla de partición que establece que los límites de los compartimentos deben ubicarse de manera que se minimice la varianza ponderada acumulada de los compartimentos. La implementación de esta regla es un problema complejo y la construcción de estos histogramas también es un proceso complejo.
Un histograma v-óptimo se basa en el concepto de minimizar una cantidad que en este contexto se denomina varianza ponderada . [1] Esto se define como
donde el histograma consta de J contenedores o cubos, n j es el número de elementos contenidos en el j ésimo contenedor y donde V j es la varianza entre los valores asociados con los elementos en el j ésimo contenedor.
El siguiente ejemplo construirá un histograma V-óptimo que tiene un Valor de Ordenación de Valor, un Valor de Origen de Frecuencia y una Clase de Partición de Serie. En la práctica, casi todos los histogramas utilizados en productos comerciales o de investigación son de la clase Serie, lo que significa que los valores de ordenación secuencial se colocan en el mismo contenedor o en contenedores secuenciales. Por ejemplo, los valores 1, 2, 3 y 4 estarán en los contenedores 1 y 2, o en los contenedores 1, 2 y 3, pero nunca en los contenedores 1 y 3. Esto se tomará como una suposición en cualquier discusión posterior.
Tomemos un conjunto simple de datos, por ejemplo, una lista de números enteros:
1, 3, 4, 7, 2, 8, 3, 6, 3, 6, 8, 2, 1, 6, 3, 5, 3, 4, 7, 2, 6, 7, 2
Calcular los pares de valores y frecuencias (1, 2), (2, 4), (3, 5), (4, 2), (5, 1), (6, 4), (7, 3), (8, 2)
Nuestro histograma V-óptimo tendrá dos segmentos. Dado que un segmento debe terminar en el punto de datos correspondiente al valor 8, debemos decidir dónde colocar el límite del otro segmento. La regla de V-óptimo establece que la varianza ponderada acumulada de los segmentos debe minimizarse. Analizaremos dos opciones y calcularemos la varianza acumulada de esas opciones.
Opción 1: El depósito 1 contiene los valores del 1 al 4. El depósito 2 contiene los valores del 5 al 8.
Cubo 1:
Frecuencia media 3,25
Varianza ponderada 2,28
Cubo 2:
Frecuencia media 2,5
Varianza ponderada 2,19
Suma de la varianza ponderada 4,47
Opción 2: El depósito 1 contiene los valores del 1 al 2. El depósito 2 contiene los valores del 3 al 8.
Cubo 1:
Frecuencia media 3
Varianza ponderada 1,41
Cubo 2:
Frecuencia media 2,83
Varianza ponderada 3,29
Suma de la varianza ponderada 4,70
La primera opción es mejor, por lo que el histograma que se almacenaría sería:
Grupo 1: Rango (1–4), Frecuencia promedio 3,25
Grupo 2: Rango (5–8), Frecuencia promedio 2,5
Los histogramas V-óptimos son más eficaces a la hora de estimar el contenido de los contenedores. Un histograma es una estimación de los datos base y cualquier histograma tendrá errores. La regla de partición utilizada en los histogramas V-óptimos intenta tener la menor varianza posible entre los contenedores, lo que permite un error menor. La investigación realizada por Poosala e Ioannidis 1 ha demostrado que la estimación más precisa de los datos se realiza con un histograma V-óptimos que utiliza el valor como parámetro de ordenación y la frecuencia como parámetro de origen.
Si bien el histograma V-optimal es más preciso, tiene desventajas. Es una estructura difícil de actualizar. Cualquier cambio en el parámetro de origen podría potencialmente resultar en tener que reconstruir el histograma por completo, en lugar de actualizar el histograma existente. Un histograma de ancho equitativo no tiene este problema. Los histogramas de profundidad equitativa experimentarán este problema hasta cierto punto, pero debido a que la construcción de profundidad equitativa es más simple, hay un menor costo para mantenerlo. La dificultad para actualizar los histogramas VOptimal es una consecuencia de la dificultad involucrada en la construcción de estos histogramas.
El cálculo del histograma V-óptimo es computacionalmente costoso en comparación con otros tipos de histogramas. [2]
El ejemplo anterior es simple. Solo hay 7 opciones de límites de cubeta. Se podría calcular la varianza acumulada para las 7 opciones fácilmente y elegir la mejor ubicación absoluta. Sin embargo, a medida que el rango de valores se hace más grande y el número de cubetas se hace más grande, el conjunto de histogramas posibles crece exponencialmente y se convierte en un problema desalentadoramente complejo encontrar el conjunto de límites que proporcionen la varianza mínima absoluta utilizando el enfoque ingenuo. Usando programación dinámica , es posible calcular el histograma V-óptimo en donde N es el número de puntos de datos y B es el número de cubetas. [3]
Dado que la búsqueda del histograma óptimo es cuadrática, es común, en cambio, aproximar el histograma V-óptimo. Al crear soluciones aleatorias, usarlas como punto de partida y mejorarlas, se puede encontrar una solución que sea una aproximación justa de la "mejor" solución. Un método de construcción utilizado para solucionar este problema es el algoritmo de mejora iterativa. Otro es el recocido simulado. Los dos pueden combinarse en la optimización de dos fases o 2PO. Estos algoritmos se presentan en "Algoritmos aleatorios..." (citado a continuación) como un método para optimizar las consultas, pero la idea general puede aplicarse a la construcción de histogramas V-óptimos.
La mejora iterativa (II) es un algoritmo bastante ingenuo y voraz. A partir de un estado aleatorio, se consideran pasos iterativos en muchas direcciones. Se toma el paso que ofrece la mejor mejora del costo (en este caso, la varianza total). El proceso se repite hasta que se llega al mínimo local, donde no es posible ninguna mejora adicional. Aplicado a la construcción de histogramas V-óptimos, el estado aleatorio inicial sería un conjunto de valores que representan las ubicaciones de los límites de los cubos. Los pasos de mejora iterativos implicarían mover cada límite hasta que estuviera en su mínimo local, luego pasar al siguiente límite y ajustarlo en consecuencia.
Una explicación básica del recocido simulado es que es muy parecido al II, solo que en lugar de dar el paso codicioso cada vez, a veces aceptará un paso que resulte en un aumento del costo. En teoría, SA tendrá menos probabilidades de detenerse en un mínimo muy local y más probabilidades de encontrar uno más global. Una imagen útil es un gráfico en forma de M, que representa el costo total en el eje Y. Si el estado inicial está en la parte en forma de V de la "M", II se asentará en el valle alto, el mínimo local. Debido a que SA aceptará movimientos cuesta arriba, es más probable que suba por la pendiente de la "V" y termine al pie de la "M", el mínimo global.
La optimización en dos fases, o 2PO, combina los métodos II y SA. Se ejecuta II hasta que se alcanza un mínimo local y luego se ejecuta SA en esa solución en un intento de encontrar mejoras menos obvias.
La idea detrás de los histogramas V-óptimos es minimizar la varianza dentro de cada grupo. Al considerar esto, surge la idea de que la varianza de cualquier conjunto con un miembro es 0. Esta es la idea detrás de los histogramas V-óptimos "sesgados hacia el final". El valor con la frecuencia más alta siempre se coloca en su propio grupo. Esto garantiza que la estimación para ese valor (que es probable que sea la estimación solicitada con más frecuencia, ya que es el valor más frecuente) siempre será precisa y también elimina el valor con más probabilidades de causar una alta varianza del conjunto de datos.
Otra idea que podría surgir es que la varianza se reduciría si se ordenara por frecuencia, en lugar de por valor. Esto tendería naturalmente a colocar valores similares uno al lado del otro. Un histograma de este tipo se puede construir utilizando un Valor de Ordenación de Frecuencia y un Valor de Origen de Frecuencia. En este punto, sin embargo, los contenedores deben llevar información adicional que indique qué valores de datos están presentes en el contenedor. Se ha demostrado que estos histogramas son menos precisos, debido a la capa adicional de estimación requerida.
