Como empezar, me quería referir a un artículo de revista, se llama Un Algoritmo Rápido para Aproximado de Cuantiles en Alta Velocidad de los Flujos de Datos. Este es un papel que tengo que hace referencia a mí mismo antes y utilizado en la práctica, cuando la construcción de software de análisis de flujo de datos. Además, este método también fue discutido y aplicado aquí en Intel sitio.
A continuación es una instantánea de la más simple fragmento de código que se utiliza para calcular las instantáneas de cuantiles para la transmisión de datos desde el procesador Intel sitio que muestra cómo el algoritmo fue implementado.
#include "mkl_vsl.h"
#include <stdio.h>
#define DIM 3 /* dimension of the task */
#define N 1000 /* number of observations */
#define M 100 /* number of quantiles to compute */
#define EPS 0.01 /* accuracy of quantile computation */
int main()
{
int i, status;
VSLSSTaskPtr task;
float x[DIM][N]; /* matrix of observations */
float q_order[M], quants[M];
float params;
MKL_INT q_order_n;
MKL_INT p, n, nparams, xstorage;
int indices[DIM]={1,0,0}; /* the first vector component is processed */
/* Parameters of the task and initialization */
p = DIM;
n = N;
q_order_n = M;
xstorage = VSL_SS_MATRIX_STORAGE_ROWS;
params = EPS;
nparams = VSL_SS_SQUANTS_ZW_PARAMS_N;
/* Calculate percentiles */
for ( i = 0; i < M; i++ ) q_order[i] = (float)i / (float)M;
/* Create a task */
status = vslsSSNewTask( &task, &p, &n, &xstorage, x, 0, indices );
/* Initialize the task parameters */
status = vslsSSEditStreamQuantiles( task, &q_order_n, q_order,
quants, &nparams, ¶ms );
/* Compute the percentiles with accuracy eps */
status = vslsSSCompute( task, VSL_SS_STREAM_QUANTS,
VSL_SS_METHOD_SQUANTS_ZW );
/* Deallocate the task resources */
status = vslSSDeleteTask( &task );
return 0;
}
Como Zhang dice en su artículo, "Streaming cuantil de cálculo tiene varias limitaciones. Los flujos de datos son transitorios y se puede llegar a una alta velocidad. Además, el tamaño del flujo no puede ser conocido apriori. Transmisión de los cálculos por lo que requieren de una sola pasada de los algoritmos con espacios reducidos y que son capaces de manejar arbitrario del tamaño de los arroyos. Con el fin de garantizar la precisión de los resultados, el algoritmo debe garantizar aleatorio o determinista de error obligado para el cálculo de los cuantiles."
Me gustaría empezar por leer el periódico y luego ir desde allí. Aquí hay un enlace al PDF de la ponencia. Varios métodos se discuten antes de su algoritmo rápido es introducido.