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

Вы, вероятно, захотите использовать какое-то большое, сбалансированное дерево. Как упоминал Тобиас, B-деревья были бы стандартным выбором для решения первой проблемы. Если вы также заботитесь о быстрых вставках и обновлениях, в таких местах, как MIT и CMU, выполняется много новой работы с этими новыми «кэширующими забывчивыми B-деревьями». Чтобы обсудить реализацию этих вещей, найдите 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].

Общие идеи:

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

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

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