Da ein k-dimensionaler kontinuierlicher (euklidischer) Raum mit ziemlich unvorhersehbar sich bewegenden / wachsenden / schrumpfenden Hypersphären gefüllt ist, muss ich wiederholt die Hyperkugel finden, deren Oberfläche einer gegebenen Koordinate am nächsten ist. Wenn einige Hypersphären die gleiche Entfernung zu meiner Koordinate haben, dann gewinnt die größte Hypersphäre. (Die Gesamtzahl der Hyperspheres bleibt im Laufe der Zeit garantiert gleich.)
Mein erster Gedanke war, einen KDTree zu verwenden, aber er wird die ungleichmäßigen Volumina der Hyperspheres nicht berücksichtigen. Also schaute ich weiter und fand BVH (Begrenzungsvolumenhierarchien) und BIH (Grenzhierarchien), die den Trick zu tun scheinen. Zumindest im 2- / 3-dimensionalen Raum. Aber während ich ziemlich viele Informationen und Visualisierungen über BVHs fand, konnte ich kaum etwas über BIHs finden.
Meine Grundvoraussetzung ist eine k-dimensionale räumliche Datenstruktur, die das Volumen berücksichtigt und entweder super schnell ist (off Linie) oder dynamisch mit kaum ein Ungleichgewicht .
Angesichts meiner obigen Anforderungen, mit welcher Datenstruktur würden Sie gehen? Irgendwelche anderen habe ich nicht einmal erwähnt?
Edit 1: Vergessen zu erwähnen: Hyperspeere dürfen sich (eigentlich stark erwartet) überlappen!
Edit 2: Sieht so aus, als ob anstelle von "distance" (und insbesondere "negative distance") meine beschriebene Metrik mit der Potenz von a übereinstimmt Punkt viel besser.
Ich würde erwarten, dass ein QuadTree / Octree / generalisiert auf 2 ^ K-Baum für Ihre Dimensionalität von K den Trick machen würde; 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 Größe, die die Hypersphäre ä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 Binärraumpartitionen in Erwägung ziehen. 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, dass die Einfüge- / Löschalgorithmen für 2 ^ K Bäume und / oder BSP / KDTrees gut verstanden und schnell waren. 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 Dinge ist asymptotisch gleich.
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 negativem Abstand ist etwas komisch. Der Abstand ist positiv in der Geometrie, so dass es nicht viel hilfreiche Theorie zu verwenden gibt.
Eine andere Formulierung, die nur positive Entfernungen verwendet, kann hilfreich sein. Lies über hyperbolische Räume. Dies könnte helfen, Ideen für andere Wege zur Beschreibung der Entfernung zu liefern.
Tags und Links c data-structures spatial multidimensional-array