Lo mejor de las estructuras de datos de indexación para series de tiempo extremadamente grandes

Question

Me gustaría preguntarle a mis compañeros opiniones acerca de las mejores estructuras de datos para ser utilizadas para indexar series de tiempo (también conocido como datos de columna, aka plano lineal).

Dos tipos básicos de series de tiempo existir basadas en la característica de muestreo/discretización:

1. discretización regulares (cada muestra se toma con una frecuencia común)

2. discretización irregular (se toman las muestras en los puntos de tiempo arbitrarios)

consultas que serán necesarios:

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

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

3. Todos los valores en el momento rango [t0, t1] que están en el rango de valores [v0, v1]

los conjuntos de datos constan de series de tiempo se resume (que tipo de consigue sobre la discretización irregular), y de series de tiempo multivariante. 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 enviar el cómputo específico de datos requerido junto con la consulta de series de tiempo, para que el cálculo pueda ocurrir tan cerca de los datos como sea posible, a fin de reducir las comunicaciones de nodo a nodo (un tanto similar al paradigma map/reduce) - en la proximidad corta de computación y datos es muy crítico.

Otro problema que el índice debería ser capaz de hacer frente, 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 Sensores de campo "o" datos de 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/eficientemente para conjuntos de datos más pequeños, pero comienza a arrastrarse a medida que los conjuntos de datos se hacen más grandes, también no hay capacidades nativas de procesamiento en paralelo desde el front-end.

en busca de sugerencias, enlaces, además de leer, etc (soluciones de C o C++, bibliotecas)

Answer 1

las ideas generales:

Problema 1 es bastante común: Crear un índice que encaja en la memoria RAM y tiene enlaces a los datos en el almacenamiento secundario (estructura de datos: B-Tree family). 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. Al usar esa información, puede filtrar los rangos de tiempo (por ejemplo, el valor máximo para un rango es 50 y busca v0> 60, luego el intervalo se agota). 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 los niveles más bajos para filtrar más rápido.

Answer 2

Es probable que desee utilizar 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. Por alguna discusión de la aplicación de estas cosas, buscar Tokutek DB, que tienen un buen número de 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ícil, ya que implican búsqueda de mayor rango dimensional. La estructura de datos estándar para hacer esto sería range tree (que da O (log^{d-1} (n)) tiempo de consulta, a costa de O (n log^d (n)) almacenamiento). Por lo general, no desea utilizar un árbol k-d 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 que O (10^5) lecturas de disco se completen en una consulta de rango simple?)

Afortunadamente, suena como En 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].

Answer 3

Va a ser muy lento y complicado de implementar esto por su cuenta. Te recomiendo que uses Cassandra. Cassandra puede brindarle escalabilidad horizontal, redundancia y le permite ejecutar funciones complicadas de reducción de mapas en el futuro. Para saber cómo almacenar series de tiempo en cassandra, consulte: http://www.datastax.com/dev/blog/advanced-time-series-with-cassandra y http://www.youtube.com/watch?v=OzBJrQZjge0.