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

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

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

Регулярная дискретизация (каждый образец берется с общей частотой)
Нерегулярная дискретизация (Образцы берутся в суровых временных точках)

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

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

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

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

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

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

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

Ответ 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))). Обычно вы не хотели бы использовать дерево k-d для чего-то вроде этого. Хотя верно, что деревья 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].

Ответ 2

Общие идеи:

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

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

Ответ 3

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