Entdecken periodische Muster in einem großen Datensatz

Question

Ich habe eine große Sequenz von Tupeln auf der Platte in Form (t1, k1) (T2, K2) ... (tn, kn)

ti ist ein monoton ansteigender Zeitstempel und ki ist ein Schlüssel (bei Bedarf eine Zeichenfolge fester Länge annehmen). Weder ti oder ki sind garantiert einzigartig. Die Anzahl der einzigartigen tis und kis ist jedoch riesig (Millionen). n selbst ist sehr groß (100 Millionen +) und die Größe von k (ca. 500 Byte) macht es unmöglich, alles im Speicher zu speichern.

Ich möchte periodische Vorkommen von Schlüsseln in dieser Reihenfolge herausfinden.

Zum Beispiel, wenn I die Sequenz (1, a) (2, b) (3, c) (4, b) (5, a) (6, b) (7, d) (8, b) (9, a) (10, b)

Der Algorithmus sollte emittieren (a, 4) und (b, 2). Das ist ein tritt mit einer Periode von 2 auf.

Wenn ich einen Hash aller Schlüssel aufstelle und den Durchschnitt der Differenz zwischen aufeinander folgenden Zeitstempeln jedes Schlüssels und einer Standardabweichung desselben speichern Ich könnte vielleicht einen Durchlauf machen und nur diejenigen melden, die eine akzeptable Standardabweichung haben (im Idealfall 0). Es erfordert jedoch einen Bucket pro eindeutigen Schlüssel, während in der Praxis sehr wenige wirklich periodische Muster vorliegen. Irgendwelche besseren Möglichkeiten?

Answer 1

Dies ist mehr oder weniger der Grund, warum Fourier transforms (Fast Fourier Transforms, etc.) erfunden wurden.

Sie transformieren im Wesentlichen eine Sequenz aus der Zeitdomäne (oder einer ähnlichen Dimension) in eine frequency domain. Dies ist ein sehr altes Problem, das der Anwendung von Computern vorausgeht, und es gibt eine immense Menge an Theorien zu diesem Thema. Siehe auch discrete fourier transform.

EDIT: Sie müssten Ihre Werte k1, k2, ... irgendwie transformieren, aber vorausgesetzt, dass das machbar ist, sollte dieser Ansatz auch sein.

Answer 2

Sie könnten diskrete autocorrelation verwenden, um die Perioden zu finden, und dann nach den Schlüsseln suchen. Die Vorteile der Autokorrelation sind, dass es ein wenig einfacher ist zu verstehen, was in der diskreten Domäne vor sich geht, und Sie müssen sich keine Gedanken über die Zuordnung von Schlüsseln zu irgendwas machen. Verwenden Sie einfach eine charakteristische Funktion von zwei Schlüsseln, die 1 ist, wenn sie gleich sind und 0, wenn sie ungleich sind.

Answer 3

Wenn ich einen Hash aller Schlüssel und speichert der Mittelwert der Differenz zwischen aufeinanderfolgenden Zeitstempeln jeden Schlüssel und einer Standardabweichung desselben aufzubauen, I könnte in der Lage sein, einen Durchgang zu machen, und berichte nur diejenigen, die eine akzeptable Standardabweichung haben (im Idealfall 0). Allerdings erfordert es einen Eimer pro eindeutigen Schlüssel, während in der Praxis I sehr wenige wirklich regelmäßige Muster haben kann. Irgendwelche besseren Möglichkeiten?

Persönlich denke ich, dass dies wahrscheinlich das Beste ist, das Sie erhalten werden, wenn Sie mehr Struktur zu dem Problem identifizieren können.

Answer 4

Lassen Sie uns Etikett a (Zeitstempel, string) Tupel als ( Schlüssel, Wert). Einige Einschränkungen: 1. Es gibt einen diskreten Satz Werte, d.h. die Übereinstimmung zwischen periodischen Erscheinungen dieser Werte ist genau: aaabb ... aaabb, nicht aaabb ... aaabc. 2. Die Menge aller Instanzen eines Wertes kann in den Speicher eingegeben werden.

Algorithmus: 1. Eine vollständige Liste aller eindeutigen Werte erhalten 2. Für jeden eindeutigen Wert, erhalten Sie alle Tupel und produzieren eine geordnete Liste von Zeitstempeln. 3. Wenden Sie einen Algorithmus an, um nach Mustern in diesen Daten zu suchen. Idealerweise eine nicht gleichförmige diskrete Fourier-Transformation oder Autokorrelation.

Answer 5

Sie haben wirklich zwei verschiedene Probleme:

1. Sie haben m unterschiedliche Signale in den Daten, die durch die m eindeutigen Schlüssel. Sie müssen jedes Signal trennen und separat speichern.

2. Bei einem dieser eindeutigen Signale müssen Sie feststellen, ob es sich um eine periodische Anwendung handelt. Dies ist eine Anwendung der Autokorrelation oder der diskreten Fourier-Transformation, je nachdem, welche Sie bevorzugen. Zum Beispiel gibt Ihnen die DFT die Koeffizienten einer Interpolation periodischer Funktionen Ihrer Daten. Wenn nur ein Koeffizient in der DFT nicht Null ist, gibt es eine klare Periode.

Wenn Sie die DFT oder Autokorrelation auf die Daten ohne Signale trennen gelten Sie ein zusammengesetztes Problem bekommen, wo Sie nicht wissen, ob einer der „periodischen“ Signale gefunden aus einem einzigartigen Signal gemacht wird oder mehr .