Обнаружение периодических шаблонов в большом наборе данных

Question

У меня есть большая последовательность кортежей на диске в виде (t1, k1) (t2, k2) ... (тн, кн)

ti - это монотонно увеличивающаяся временная метка, а ki - это ключ (если необходимо, примите строку фиксированной длины). Ни ти, ни ки не гарантированно являются уникальными. Тем не менее, количество уникальных тис и поцелуев огромно (миллионы). Сам по себе n очень большой (100 миллионов +), а размер k (около 500 байт) делает невозможным хранение всего в памяти.

Я хотел бы выяснить периодические появления ключей в этой последовательности.

Например, если у меня есть последовательность (1, а) (2, б) (3, с) (4, б) (5, а) (6, б) (7, д) (8, б) (9, а) (10, б)

Алгоритм должен излучать (a, 4) и (b, 2). То есть происходит с периодом 4, а b происходит с периодом 2.

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

Answer 1

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

Answer 2

Это более или менее причина, по которой были преобразованы Фурье ( Быстрые преобразования Фурье и т. Д.).

Вы по существу преобразуете последовательность из временной области (или некоторого подобного измерения) в частотную область . Это очень старая проблема, предшествующая применению компьютеров, и по этому вопросу существует огромный объем теории. Также см. дискретное преобразование Фурье .

РЕДАКТИРОВАТЬ: Вам придется каким-то образом преобразовать ваши значения k1, k2, ..., но при условии, что это возможно, этот подход должен быть тоже.

Answer 3

У вас действительно есть две отдельные проблемы:

1. у вас есть m различных сигналов в ваших данных, определенных m уникальными ключами. Вы должны отделить каждый сигнал и хранить отдельно.

2. учитывая один из этих уникальных сигналов, вы должны определить, является ли он периодическим, это применение автокорреляции или дискретного преобразования Фурье, в зависимости от того, что вы предпочитаете. Например, DFT дает вам коэффициенты интерполяции периодических функций ваших данных. Если только один коэффициент в ДПФ не равен нулю, существует четкий период.

Если вы примените ДПФ или автокорреляцию к данным без разделения сигналов, вы получите сложную проблему, при которой вы не узнаете, состоит ли один из найденных «периодических» сигналов из одного уникального сигнала или нескольких.

Answer 4

Давайте обозначим кортеж (метка времени, строка) как ( ключ , значение ). Некоторые ограничения: 1. Существует дискретный набор значений , то есть соответствие между периодическими появлениями этих значений является точным: aaabb ... aaabb, а не aaabb ... aaabc. 2. Множество всех экземпляров значения может быть помещено в память.

Алгоритм: 1. Получить полный список всех уникальных значений 2. Для каждого уникального значения получите все кортежи, создав упорядоченный список временных меток. 3. Примените алгоритм для поиска шаблонов в этих данных. В идеале - неоднородное дискретное преобразование Фурье или автокорреляция.

Answer 5

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

Лично я думаю, что это, вероятно, лучшее, что вы получите, если не сможете определить структуру проблемы.