Ich möchte eine Datenstruktur zum Sortieren von Raum-Zeit-Daten (x, y, z, Zeit) verwenden.
Gegenwärtig sucht ein Verarbeitungsalgorithmus eine Menge von 4D-Punkten (x, y, z, Zeit) mit einem sphärischen (3d) räumlichen Radius und einem linearen (1d) Zeitradius und markiert für jeden Punkt, welche anderen Punkte innerhalb liegen diese Radien. Der Grund ist, dass ich nach der Verarbeitung jeden beliebigen 4D Punkt für alle seine Nachbarn in O (1) Zeit fragen kann.
Bei einigen üblichen Konfigurationen von Raum- und Zeitradien dauert der erste Lauf des Algorithmus jedoch ungefähr 12 Stunden. Ob Sie es glauben oder nicht, das ist im Vergleich zu dem, was in unserer Branche existiert, tatsächlich schnell. Nichtsdestotrotz möchte ich helfen, die ersten Runs zu beschleunigen und ich möchte wissen: Ist ein kd-tree geeignet für 4D Raum-Zeit-Daten?
Beachten Sie, dass ich nicht nach Implementierungen der Suche nach dem nächsten Nachbarn oder der Suche nach k-nächsten Nachbarn suche.
Weitere Informationen:
Ein Beispieldatensatz hat 450.000 4D-Punkte.
Einige Datensätze sind zeitdicht, so dass die Reihenfolge nach Zeit sicherlich die Verarbeitung spart, aber immer noch zu vielen Abstandsprüfungen führt.
Zeit wird durch Daten im Excel-Stil dargestellt, mit typischen Bereichen zwischen 30.000 und 39.000 (ungefähr). Die Raumbereiche sind manchmal höhere Werte, manchmal niedrigere Werte, aber der Bereich zwischen jeder Raumkoordinate ist ähnlich der Zeit (z. B. maxX-minX ~ maxT-minT).
Noch mehr Informationen:
Ich dachte, ich würde etwas mehr irrelevante Daten hinzufügen, falls jemand mit einem ähnlichen Datensatz zu tun hat.
Im Grunde arbeite ich mit Daten, die Raum-Zeit-Ereignisse darstellen, die von mehreren Sensoren aufgezeichnet und bestätigt werden. Es liegt ein Fehler vor, daher sind nur Ereignisse enthalten, die einen Fehlerschwellenwert erfüllen.
Die Zeitspanne dieser Datensätze reicht von 5 bis 20 Jahren Daten.
Für die wirklich alten Daten (& gt; 8 Jahre alt) waren die Ereignisse aus zwei Gründen oft sehr räumlich dicht: 1) es gab damals relativ wenige Sensoren und 2) die Sensoren waren nahe beieinander angeordnet, so dass sie in der Nähe waren Ereignisse können korrekt mit geringem Fehler bestätigt werden. Weitere Ereignisse konnten aufgezeichnet werden, aber sie hatten einen zu hohen FehlerFür die neueren Daten (& lt; 8 Jahre alt) sind die Ereignisse oft sehr zeitaufwendig, aus entgegengesetzten Gründen: 1) es sind normalerweise viele Sensoren verfügbar, und 2) die Sensoren sind in regelmäßigen Intervallen über einem größeren angeordnet Entfernung.
Folglich können die Datensätze normalerweise nicht als zeitdicht oder nur räumlich dicht bezeichnet werden (außer bei Datensätzen, die nur neue Daten enthalten).
Fazit
Ich sollte eindeutig mehr Fragen auf dieser Seite stellen.
Ich werde in der nächsten Zeit mehrere Lösungen testen, die den 4d kd-Baum, einen 3d kd-Baum gefolgt von einer Zeitdistanzprüfung (vorgeschlagen von Drew Hall) und den aktuellen Algorithmus enthalten werden. Außerdem wurde mir eine andere Datenstruktur namens TSP (time space partitioning) vorgeschlagen, die einen Octree für den Raum und einen bsp für jeden Knoten für die Zeit verwendet, also kann ich das auch testen.
Wenn ich mich erinnere, werde ich sicher einige Profiling-Benchmarks auf verschiedenen Zeit- / Raumradien-Konfigurationen veröffentlichen.
Danke allen
Um ein wenig über meine Kommentare zu einer Antwort oben zu erweitern:
Gemäß der Literatur benötigen kd-Bäume Daten mit euklidischen Koordinaten. Sie sind wahrscheinlich nicht unbedingt notwendig, aber sie sind sicherlich ausreichend: um zu garantieren, dass alle Koordinaten euklidisch sind, stellt man sicher, dass die normalen Regeln des Raums gelten, und es ermöglicht, Punkte einfach nach ihrer Position zu teilen und die Baumstruktur aufzubauen.
>Die Zeit ist ein bisschen seltsam. Unter den Regeln der speziellen Relativitätstheorie verwenden Sie eine Minkowski-Metrik, nicht eine euklidische Standardmetrik, wenn Sie mit Zeitkoordinaten arbeiten. Dies verursacht alle Arten von Problemen (von denen die schwersten unter ihnen die Bedeutung der "Gleichzeitigkeit" zerstören) und macht Menschen allgemein Angst vor Zeitkoordinaten. Diese Angst ist jedoch nicht begründet, denn wenn Sie nicht wissen, dass Sie an der Physik arbeiten, wird Ihre Zeit mit ziemlicher Sicherheit tatsächlich in der Praxis euklidisch sein.
>
Was bedeutet es für eine Koordinate, euklidisch zu sein? Es sollte unabhängig von allen anderen Koordinaten sein. Zeit zu sagen ist eine euklidische Koordinate bedeutet, dass Sie die Frage beantworten können "Sind diese beiden Punkte zeitlich nahe beieinander?" indem Sie only zu ihren Zeitkoordinaten sehen und zusätzliche Informationen ignorieren. Es ist leicht zu sehen, warum nicht diese Eigenschaft hat, die ein Schema, das Punkte durch die Werte ihrer Koordinaten teilt, bricht. Wenn zwei Punkte radikal andere Zeitkoordinaten haben können, aber immer noch als "zeitlich nahe" betrachtet werden, dann wird ein Baum, der sie nach Zeitkoordinaten sortiert, nicht sehr gut funktionieren.
Ein Beispiel für eine euklidische Zeitkoordinate wäre jede Zeit, die in einer einzigen, konsistenten Zeitzone angegeben wird (wie UTC-Zeiten). Wenn Sie zwei Uhren haben, eine in New York und eine in Tokio, wissen Sie, dass wenn Sie zwei Messungen mit der Bezeichnung "12:00 UTC" haben, dann wurden sie zur gleichen Zeit genommen. Aber wenn die Messungen in Ortszeit gemacht werden, also man sagt "12:00 New York Zeit" und eine ist "12:00 Tokyo Zeit", müssen Sie zusätzliche Informationen über die Orte und Zeitzonen der Städte verwenden, um herauszufinden wie viel Zeit zwischen den beiden Messungen verstrichen ist.
Solange also Ihre Zeitkoordinate konsistent gemessen und vernünftig ist, wird sie euklidisch sein, und das bedeutet, dass sie in einem kd-Baum oder einer ähnlichen Datenstruktur gut funktioniert.
Wenn Sie einen Index für Ihre Punkte gespeichert haben, die in der Zeitdimension sortiert sind, können Sie nicht zuerst eine erste Bereinigung in der 1-d-Zeitdimension durchführen und so die Anzahl der Entfernungsberechnungen reduzieren? (Oder ist das eine Überzeichnung?)
Sie haben nicht wirklich genug Informationen gegeben, um dies zu beantworten.
Aber im Allgemeinen sind kd-Bäume im Allgemeinen für 4 (oder 5 oder 6 oder ...) dimensionale Daten geeignet - wenn die räumliche Verteilung (oder in Ihrem Fall Raum / Zeit-Verteilung) sich für kd eignet Baumzerlegung. Mit anderen Worten, es kommt darauf an (bekannt?).
kd-Bäume sind nur eine Methode der räumlichen Zerlegung, die sich für bestimmte lokalisierte Suchen eignen. Wenn Sie zu höheren Dimensionen gehen, wird der Fluch des Dimensionalitätsproblems natürlich wieder größer, aber 4d ist nicht schlecht (Sie wollen wahrscheinlich mindestens einige hundert Punkte).
Um zu wissen, ob dies für Sie funktioniert, müssen Sie einige andere Kriterien analysieren. Ist ungefähre NN Suche gut genug (das kann sehr helfen). Ist Baumausgleich wahrscheinlich teuer? usw.
Wenn Ihre Daten relativ zeitdicht sind (und relativ wenig Platz haben), könnte es am besten sein, einen 3d kd-Baum für die räumlichen Dimensionen zu verwenden, dann lehnen Sie einfach die Punkte ab, die außerhalb des interessierenden Zeitfensters liegen. Das würde Ihr Problem mit gemischten Raum / Zeit-Metrik umgehen, auf Kosten einer etwas komplexeren Punktstruktur.
Tags und Links algorithm math search data-structures multidimensional-array