Schnelle räumliche Datenstruktur für Nearest-Neighbor-Suche zwischen Hypersphären ungleichmäßiger Größe

Angesichts eines k-dimensionalen kontinuierlichen (euklidischen) Raums mit ziemlich unvorhersehbar sich bewegenden/wachsenden/schrumpfenden Hypersphären muss ich immer wieder die Hyperkugel finden, deren Oberfläche am nächsten ist gegebene Koordinate. Wenn einige Hypersphären die gleiche Entfernung zu meiner Koordinate haben, dann gewinnt die größte Hypersphäre. (Die Gesamtzahl der Hypersphären ist garantiert das gleiche im Laufe der Zeit zu bleiben.)Schnelle räumliche Datenstruktur für Nearest-Neighbor-Suche zwischen Hypersphären ungleichmäßiger Größe

Mein erster Gedanke war ein KDTree zu verwenden, aber es wird die Hypersphären nicht einheitliche Volumina nicht berücksichtigen. Also schaute ich weiter und fand BVH (Bounding Volume Hierarchies) und BIH (Bounding Interval Hierarchies), die den Trick zu tun scheinen. Zumindest im 2-/3-dimensionalen Raum. Während ich jedoch ziemlich viele Informationen und Visualisierungen zu BVHs fand, konnte ich kaum etwas über BIHs finden.

My Grundvoraussetzung ist eine k-dimensionale räumliche Datenstruktur, die Volumen in Rechnung trägt und ist entweder super schnellen (off-line) oder dynamisch mit kaum Unwucht aufzubauen.

Angesichts meiner Anforderungen oben, mit welcher Datenstruktur würden Sie gehen? Irgendwelche anderen, die ich nicht einmal erwähnt habe?

Edit 1: Vergessen zu erwähnen: hypershperes dürfen (eigentlich sehr zu erwarten) überlappen!

Edit 2: Sieht so aus, als ob anstelle von "Abstand" (und "negativer Abstand" im Besonderen) meine beschriebene Metrik dem power of a point viel besser entspricht.

Quelle

2012-06-04 Regexident

Da die Berechnung der Entfernung von einem Punkt zu einer Hypersphäre einfach trivial ist (selbst wenn O (k), aber so ist alles im k-Raum), wie viele Hyperspheres haben Sie im Allgemeinen? Natürlich sollte sich die Datenstruktur im Vergleich zu einer einfachen linearen Liste von Hyperspheres auszahlen. Nette Frage, obwohl. –

Die Anzahl der Hyperspheres könnte 8 sein (in diesem Fall würde ich wahrscheinlich nur mit Brute-Force gehen, oder in Tausenden oder sogar Hunderttausenden, abhängig von der Größe des Datensatzes, die ich an dieser Stelle nicht vorhersehen kann. Ich mache derzeit Brute-Force und es ist schmerzhaft langsam – Regexident

Ändert sich die Anzahl der Hypersphären, während Ihr Programm ausgeführt wird? Und zur Klarstellung, wenn Sie 'eine gegebene Koordinate' schreiben, erwarte ich, dass Sie eine Funktion wollen, die z Gibt jede gegebene Koordinate die nächste Hypersphäre zurück, dh die gegebene Koordinate ist nicht für die Dauer des Programms festgelegt? –

Ich würde erwarten, dass ein QuadTree/Octree/generalisiert auf 2^K-Baum für Ihre Dimensionalität von K würde den Trick tun; diese rekursiv Partition Raum, und vermutlich können Sie aufhören, wenn ein K-Teilwürfel (oder K-rechteckigen Ziegel, wenn die Splits nicht gerade sind) enthält keine Hypersphäre, oder enthält eine oder mehrere Hypersphären, so dass Partitionierung keine trennt, oder enthält alternativ das Zentrum von nur einer einzigen Hypersphäre (wahrscheinlich einfacher).

Das Einfügen und Löschen von Entitäten in solchen Bäumen ist schnell, so dass eine Hypergröße, die die Größe ändert, nur ein Lösch/Einfüge-Paar von Operationen verursacht. (Ich vermute, dass Sie dies optimieren können, wenn sich Ihre Kugelgröße durch eine lokale zusätzliche rekursive Partition ändert, wenn die Kugel kleiner wird, oder wenn ein lokaler K-Block-Merge entsteht, wenn er wächst).

Ich habe nicht mit ihnen gearbeitet, aber Sie könnten auch binary space partitions betrachten. Mit diesen können Sie binäre Bäume anstelle von k-Bäumen verwenden, um Ihren Raum zu partitionieren. Ich verstehe, dass KDTrees ein Sonderfall sind.

Aber auf jeden Fall dachte ich, die Einfüge-/Löschalgorithmen für 2^K Bäume und/oder BSP/KDTrees waren gut verstanden und schnell. Hyperflächengrößenänderungen verursachen daher Lösch-/Einfügeoperationen, aber diese sind schnell. Also verstehe ich deinen Einwand gegen KD-Bäume nicht.

Ich denke, die Leistung all dieser sind asymptotisch gleich.

Quelle

2012-06-07 12:38:10

Wie funktionieren Raumtrennung und/oder 2^k-Bäume mit der Tatsache, dass Hypersphären sich überlappen sollen (und dies häufig)? Tut mir leid, wenn das nicht klar war. Bearbeitete meine Frage, um das besser zu reflektieren. – Regexident

Warum ist ihre Überschneidung wichtig? Alles, was Sie tun möchten, ist, den Raum so zu partitionieren, dass sich ein kleiner Satz von Sphären in einem bestimmten Chunk befindet, so dass Sie entscheiden können, welches für die Koordinate in diesem Chunk am besten ist. Und wenn die Überlappung Sie stört, dann partitionieren Sie, bis ein K-Block nur den Mittelpunkt einer Kugel enthält. Suchen Sie dann die Partition, die Ihren Interessenpunkt enthält, und listen Sie alle Unterblöcke auf, die Kugeln/Kugelzentrenpunkte enthalten. –

wäre das Turbo-geladen oder nur 200 Gallonen? –

Ich würde die R * Tree-Erweiterung für SQLite verwenden. Eine Tabelle würde normalerweise 1 oder 2 dimensionale Daten haben. SQL-Abfragen können mehrere Tabellen kombinieren, um in höheren Dimensionen zu suchen.

Die Formulierung mit negativen Abstand ist ein wenig seltsam.Die Entfernung ist in der Geometrie positiv, so dass es möglicherweise keine hilfreiche Theorie gibt.

Eine andere Formulierung, die nur positive Entfernungen verwendet, kann hilfreich sein. Lies über hyperbolische Räume. Dies könnte dazu beitragen, Ideen für andere Wege zur Beschreibung der Entfernung zu liefern.

Quelle

2012-06-11 20:33:02

Schnelle räumliche Datenstruktur für Nearest-Neighbor-Suche zwischen Hypersphären ungleichmäßiger Größe

Antwort

Verwandte Themen