Лучшие в своем классе структуры данных индексации для чрезвычайно больших временных рядов

Question

Я бы хотел попросить других SO для их мнений относительно лучших структур данных, которые будут использоваться для индексации временных рядов (по столбцам, плоско-линейные данные).

Два основныхСуществуют типы временных рядов, основанные на характеристике выборки / дискретизации:

1. Регулярная дискретизация (каждый образец берется с общей частотой)

2. Неправильная дискретизация (образцы берутся в произвольные моменты времени)

Запросы, которые потребуются:

1. Все значения в диапазоне времени [t0, t1]

2. Все значения в диапазоне времени [t0, t1], которые больше / меньше v0

3. Все значения во временидиапазон [t0, t1], который находится в диапазоне значений [v0, v1]

Наборы данных состоят из суммированных временных рядов (что-то вроде нерегулярной дискретизации), имногомерный временной ряд.Размер рассматриваемых наборов данных составляет около 15-20 ТБ, следовательно, обработка выполняется распределенным образом - поскольку некоторые из описанных выше запросов приведут к наборам данных, превышающим физический объем памяти, доступный в любой одной системе.

Распределенная обработка в этом контексте также означает диспетчеризацию требуемых конкретных вычислений данных вместе с запросом временного ряда, чтобы вычисление могло происходить как можно ближе к данным, чтобы уменьшить связь между узлами(несколько похоже на парадигму отображения / сокращения) - в непосредственной близости от вычислений и данных очень важно.

Другая проблема, с которой должен справиться индекс, заключается в том, что подавляющее большинство данных является статичными / историческими.(99,999 ...%), однако ежедневно добавляются новые данные, представьте себе "сеньоров на местах" или "рыночные данные".Идея / требование состоит в том, чтобы иметь возможность обновлять любые текущие вычисления (средние значения, диаграммы и т. Д.) С минимально возможной задержкой, некоторые из этих текущих вычислений требуют исторических данных, некоторые из которых будут больше, чем те, которые могут быть разумно кэшированы.

Я уже рассмотрел HDF5, он работает хорошо / эффективно для небольших наборов данных, но начинает перетаскиваться по мере увеличения наборов данных, также нет встроенных возможностей параллельной обработки от внешнего интерфейса.

Поиск предложений, ссылок, дальнейшего чтения и т. Д. (Решения на C или C ++, библиотеки)

Answer 1

Возможно, вы захотите использовать какое-то большое сбалансированное дерево.Как упоминал Тобиас, B-деревья были бы стандартным выбором для решения первой проблемы.Если вы также хотите получать быстрые вставки и обновления, в таких новых «B-деревьях кеша» в таких местах, как MIT и CMU, делается много новой работы.Для некоторого обсуждения реализации этих вещей, посмотрите Tokutek DB , у них есть много хороших презентаций, таких как:

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

Вопросы2 и 3, как правило, намного сложнее, поскольку они включают поиск в более широком диапазоне измерений.Стандартной структурой данных для этого будет дерево диапазона (которое дает O (log ^ {d-1} (n))) время запроса за счет O (n log ^ d (n)) место хранения).Как правило, вы бы не хотели бы использовать дерево kd для чего-то подобного.Хотя верно, что деревья kd имеют оптимальные, O (n), затраты на хранение, фактом является то, что вы не можете оценить запросы диапазона быстрее, чем O (n ^ {(d-1) / d}), если вы толькоиспользуйте O (n) хранилище.Для d = 2 это будет O (sqrt (n)) сложность времени;и, честно говоря, это не приведет к сокращению, если у вас есть 10 ^ 10 точек данных (кто хочет дождаться завершения чтения диска O (10 ^ 5) по простому запросу диапазона?)

К счастью, этоПохоже на вашу ситуацию, вам действительно не нужно слишком беспокоиться об общем случае.Поскольку все ваши данные поступают из временного ряда, у вас всегда есть только одно значение для каждой временной координаты.Гипотетически, то, что вы могли бы сделать, это просто использовать запрос диапазона, чтобы вытянуть некоторый интервал точек, а затем, после завершения процесса, применить поточечные ограничения v.Это будет первое, что я попробую (после хорошей реализации базы данных), и если это сработает, то все готово!На самом деле имеет смысл попытаться оптимизировать последние два запроса, если вы продолжаете сталкиваться с ситуациями, когда число точек в [t0, t1] x [-infty, + infty] на порядки больше, чем количество точек в [t0, t1] x [v0, v1].

Answer 2

Это будет очень трудоемким и сложным, чтобы реализовать это самостоятельно. Я рекомендую вам использовать Кассандру. Cassandra может предоставить вам горизонтальную масштабируемость, избыточность и позволит вам в будущем запускать сложные функции сокращения карт. Чтобы узнать, как хранить временные ряды в Кассандре, взгляните на: http://www.datastax.com/dev/blog/advanced-time-series-with-cassandra и http://www.youtube.com/watch?v=OzBJrQZjge0.

Answer 3

Общие идеи:

Проблема 1 довольно распространена: создайте индекс, который помещается в вашу оперативную память и содержит ссылки на данные на вторичном хранилище (структура данных: семейство B-Tree ),Задача 2/3 довольно сложна, так как ваши данные очень большие.Вы можете разделить ваши данные на временные диапазоны и рассчитать минимальное / максимальное значения для этого временного диапазона.Используя эту информацию, вы можете отфильтровать временные диапазоны (например, максимальное значение для диапазона составляет 50, и вы ищете v0> 60, тогда интервал истекает).Остальные нужно искать, просматривая данные.Эффективность в значительной степени зависит от того, насколько быстро изменяются данные.

Вы также можете создавать несколько индексов, комбинируя временные диапазоны более низких уровней для ускорения фильтрации.