stringtranslate.com

Algoritmo de Marzullo

El algoritmo de Marzullo , inventado por Keith Marzullo para su tesis doctoral en 1984, es un algoritmo de acuerdo utilizado para seleccionar fuentes para estimar el tiempo preciso a partir de una serie de fuentes de tiempo ruidosas . Una versión refinada de este algoritmo, rebautizada como " algoritmo de intersección ", forma parte del moderno Protocolo de Tiempo de Red . El algoritmo de Marzullo también se utiliza para calcular la intersección relajada de n cajas (o, de manera más general, n subconjuntos de R n ), como lo requieren varios métodos de estimación de conjuntos robustos .

Objetivo

El algoritmo de Marzullo es eficiente en términos de tiempo para producir un valor óptimo a partir de un conjunto de estimaciones con intervalos de confianza donde el valor real puede estar fuera del intervalo de confianza para algunas fuentes. En este caso, se considera que la mejor estimación es el intervalo más pequeño que sea consistente con el mayor número de fuentes.

Si tenemos las estimaciones 10 ± 2, 12 ± 1 y 11 ± 1, entonces estos intervalos son [8,12], [11,13] y [10,12] que se intersecan para formar [11,12] o 11,5 ± 0,5, lo que es consistente con los tres valores.

Algoritmo de Marzullo, ejemplo#1
Algoritmo de Marzullo, ejemplo#1

Si, en cambio, los rangos son [8,12], [11,13] y [14,15], entonces no hay ningún intervalo consistente con todos estos valores, pero [11,12] es consistente con el mayor número de fuentes, es decir, dos de ellas.

Algoritmo de Marzullo, ejemplo#2
Algoritmo de Marzullo, ejemplo#2

Finalmente, si los rangos son [8,9], [8,12] y [10,12] entonces ambos intervalos [8,9] y [10,12] son ​​consistentes con el mayor número de fuentes.

Algoritmo de Marzullo, ejemplo#3
Algoritmo de Marzullo, ejemplo#3

Este procedimiento determina un intervalo. Si el resultado deseado es el mejor valor de ese intervalo, entonces un enfoque ingenuo sería tomar el centro del intervalo como valor, que es lo que se especificó en el algoritmo Marzullo original. Un enfoque más sofisticado reconocería que esto podría estar descartando información útil de los intervalos de confianza de las fuentes y que un modelo probabilístico de las fuentes podría devolver un valor distinto del centro.

Tenga en cuenta que el valor calculado probablemente se describa mejor como "optimista" en lugar de "óptimo". Por ejemplo, considere tres intervalos [10,12], [11, 13] y [11,99,13]. El algoritmo descrito a continuación calcula [11,99, 12] o 11,995 ± 0,005, que es un valor muy preciso. Si sospechamos que una de las estimaciones puede ser incorrecta, entonces al menos dos de las estimaciones deben ser correctas. Bajo esta condición, la mejor estimación es [11,13] ya que este es el intervalo más grande que siempre interseca al menos dos estimaciones. El algoritmo descrito a continuación se parametriza fácilmente con el número máximo de estimaciones incorrectas.

Método

El algoritmo de Marzullo comienza preparando una tabla de las fuentes, ordenándola y luego buscando (de manera eficiente) las intersecciones de los intervalos. Para cada fuente hay un rango [c−r,c+r] definido por c ± r. Para cada rango, la tabla tendrá dos tuplas de la forma ⟨offset,type⟩ . Una tupla representará el comienzo del rango, marcado con tipo −1 como ⟨c−r,−1⟩ y la otra representará el final con tipo +1 como ⟨c+r,+1⟩ .

La descripción del algoritmo utiliza las siguientes variables: best (mayor número de intervalos superpuestos encontrados), cnt (número actual de intervalos superpuestos), beststart y bestend (el comienzo y el final del mejor intervalo encontrado hasta el momento), i (un índice) y la tabla de tuplas.

  1. Construye la tabla de tuplas.
  2. Ordenar la tabla por el desplazamiento. (Si existen dos tuplas con el mismo desplazamiento pero tipos opuestos, lo que indica que un intervalo termina justo cuando comienza otro, entonces es necesario un método para decidir cuál viene primero. Tal ocurrencia puede considerarse una superposición sin duración, que puede detectarse mediante el algoritmo colocando el tipo −1 antes del tipo +1. Si tales superposiciones patológicas se consideran objetables, se pueden evitar colocando el tipo +1 antes de −1 en este caso).
  3. [inicializar] mejor=0 cnt=0
  4. [bucle] recorre cada tupla de la tabla en orden ascendente
  1. [número actual de intervalos superpuestos] cnt=cnt−type[i]
  2. si cnt>mejor entonces mejor=cnt mejorinicio=desplazamiento[i] mejorfin=desplazamiento[i+1]
comentario: la siguiente tupla, en [i+1], será o bien el final de un intervalo (tipo=+1) en cuyo caso finaliza este mejor intervalo, o bien será el comienzo de un intervalo (tipo=−1) y en el siguiente paso reemplazará a mejor.
ambigüedad: no se especifica qué hacer si best=cnt. Esta es una condición de empate para la mayor superposición. Se puede tomar la decisión de tomar el menor de bestend−beststart y offset[i+1]−offset[i] o simplemente tomar una arbitraria de las dos entradas igualmente buenas. Esta decisión es relevante solo cuando type[i+1]=+1.
  1. [fin del bucle] devuelve [beststart,bestend] como intervalo óptimo. La cantidad de fuentes falsas (aquellas que no se superponen con el intervalo óptimo devuelto) es la cantidad de fuentes menos el valor de best.

Eficiencia

El algoritmo de Marzullo es eficiente tanto en el espacio como en el tiempo. El uso asintótico del espacio es O(n) , donde n es el número de fuentes. Al considerar el requisito de tiempo asintótico, se puede considerar que el algoritmo consiste en construir la tabla, ordenarla y buscarla. La ordenación se puede realizar en un tiempo O(n log n) , y esto domina las fases de construcción y búsqueda que se pueden realizar en un tiempo lineal . Por lo tanto, la eficiencia temporal del algoritmo de Marzullo es O(n log n) .

Una vez que se ha creado y ordenado la tabla, es posible actualizar el intervalo de una fuente (cuando se recibe nueva información) en tiempo lineal. Por lo tanto, la actualización de los datos de una fuente y la búsqueda del mejor intervalo se pueden realizar en tiempo O(n).

Referencias

Enlaces externos