geeks geek for first breadth bfs c++ algorithm indexing data-structures large-data

c++ - geek - Lo mejor de las estructuras de datos de indexación para series de tiempo extremadamente grandes



breadth first search graph (3)

Me gustaría preguntarles a los compañeros SOE sus opiniones sobre las mejores estructuras de datos de razas que se utilizarán para indexar series de tiempo (también conocidas como datos de columnas, también llamadas lineales planas).

Existen dos tipos básicos de series temporales basadas en la característica de muestreo / discretización:

  1. Discretización regular (cada muestra se toma con una frecuencia común)

  2. Discretización irregular (las muestras se toman en puntos de tiempo arbitary)

Consultas que serán requeridas:

  1. Todos los valores en el rango de tiempo [t0, t1]

  2. Todos los valores en el rango de tiempo [t0, t1] que son mayores / menores que v0

  3. Todos los valores en el rango de tiempo [t0, t1] que se encuentran en el rango de valores [v0, v1]

Los conjuntos de datos consisten en series temporales resumidas (que en cierto modo superan la discretización irregular) y series temporales multivariantes. Los conjuntos de datos en cuestión tienen un tamaño de aproximadamente 15-20TB, por lo que el procesamiento se realiza de forma distribuida, ya que algunas de las consultas descritas anteriormente darán lugar a conjuntos de datos más grandes que la cantidad física de memoria disponible en cualquier sistema.

El procesamiento distribuido en este contexto también significa despachar el cómputo específico de datos requerido junto con la consulta de series de tiempo, para que el cálculo pueda ocurrir lo más cerca posible de los datos, para reducir las comunicaciones entre nodos (algo similar al mapa / reducir el paradigma) - en la proximidad del cálculo y la información es muy crítica.

Otro problema que el índice debería ser capaz de afrontar es que la abrumadora mayoría de los datos son estáticos / históricos (99.999 ...%); sin embargo, a diario se agregan nuevos datos, piense en "en el campo de los sensores" o "datos del mercado". La idea / requisito es poder actualizar cualquier cálculo en ejecución (promedios, garch, etc.) con una latencia tan baja como sea posible, algunos de estos cálculos en ejecución requieren datos históricos, algunos de los cuales serán más de lo que razonablemente se pueden almacenar en caché.

Ya he considerado HDF5, funciona bien / de manera eficiente para conjuntos de datos más pequeños, pero comienza a arrastrarse a medida que los conjuntos de datos se vuelven más grandes, también no hay capacidades nativas de procesamiento en paralelo desde el front-end.

Buscando sugerencias, enlaces, lecturas adicionales, etc. (soluciones C o C ++, bibliotecas)

Ideas generales:

El problema 1 es bastante común: cree un índice que se ajuste a su RAM y tenga enlaces a los datos en el almacenamiento secundario (estructura de datos: familia B-Tree ). El problema 2/3 es bastante complicado ya que sus datos son muy grandes. Puede dividir sus datos en intervalos de tiempo y calcular el mínimo / máximo para ese rango de tiempo. Utilizando esa información, puede filtrar los rangos de tiempo (por ejemplo, el valor máximo para un rango es 50 y busca v0> 60, entonces el intervalo está fuera). El resto debe buscarse revisando los datos. La efectividad depende en gran medida de la velocidad con la que cambian los datos.

También puede hacer múltiples índices combinando los intervalos de tiempo de niveles más bajos para filtrar más rápido.

Probablemente quieras usar algún tipo de árbol grande y equilibrado. Como mencionó Tobias, B-trees sería la opción estándar para resolver el primer problema. Si también te preocupa obtener inserciones y actualizaciones rápidas, hay muchos trabajos nuevos que se están realizando en lugares como MIT y CMU en estos nuevos "B-trees" caché inconscientes. Para una discusión sobre la implementación de estas cosas, busque Tokutek DB , ellos tienen una cantidad de buenas presentaciones como las siguientes:

http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf

Las preguntas 2 y 3 son, en general, mucho más difíciles, ya que implican una mayor búsqueda del rango dimensional. La estructura de datos estándar para hacer esto sería el árbol de rango (que da O (log ^ {d-1} (n)) tiempo de consulta, a costa de O (n log ^ d (n)) almacenamiento). Por lo general, no desearía usar un árbol kd para algo como esto. Si bien es cierto que los árboles kd tienen costos de almacenamiento óptimos, O (n), es un hecho que no puede evaluar las consultas de rango más rápido que O (n ^ {(d-1) / d}) si solo use O (n) almacenamiento. Para d = 2, esta sería la complejidad del tiempo O (sqrt (n)); y, francamente, eso no lo va a cortar si tiene 10 ^ 10 puntos de datos (¿quién quiere esperar a que O (10 ^ 5) lecturas de disco se completen en una consulta de rango simple?)

Afortunadamente, suena como su situación, realmente no necesita preocuparse demasiado por el caso general. Debido a que todos sus datos provienen de una serie temporal, solo tiene como máximo un valor por cada coordenada de tiempo. Hipotéticamente, lo que podría hacer es usar una consulta de rango para extraer un intervalo de puntos, luego, como un proceso posterior, aplicar las restricciones de v de manera puntual. Esto sería lo primero que intentaría (después de obtener una buena implementación de la base de datos), y si funciona, ¡ya está listo! Realmente solo tiene sentido intentar optimizar las dos últimas consultas si sigues corriendo en situaciones donde el número de puntos en [t0, t1] x [-infty, + infty] es de órdenes de magnitud mayor que el número de puntos en [t0 , t1] x [v0, v1].