Быстрое сопоставление подпоследовательностей в базах данных временных рядов

Представлен эффективный метод индексирования для поиска одномерных подпоследовательностей в наборе последовательностей, при котором подпоследовательности соответствуют заданному шаблону запроса с точностью, определяемой установленным допуском. Основная идея заключается в отображении каждой последовательности данных в небольшое множество многомерных прямоугольников в пространстве признаков. Затем эти прямоугольники можно эффективно индексировать с помощью традиционных методов пространственного доступа, таких как R*-дерево [9]. В частности, для последовательности данных используется скользящее окно, из которого извлекаются признаки; результатом является траектория в пространстве признаков. Предложен эффективный алгоритм разбиения таких траекторий на подтраектории, которые затем представляются их минимальными ограничивающими прямоугольниками (MBR). Кроме того, рассмотрены запросы различной длины и показано, как эффективно обрабатывать каждый такой случай. Метод реализован, и проведены эксперименты на синтетических и реальных данных (изменения котировок акций). Метод сравнивался с последовательным сканированием, являющимся единственным очевидным конкурентом. Результаты оказались превосходными: предложенный метод ускорил поиск в 3–100 раз.