Ich habe keine definitive Antwort für Sie, aber ich habe einen Vorschlag für einen Ansatz, der eine Lösung liefern könnte.
Ich denke, es lohnt sich zu untersuchen locality-sensitive hashing. Ich denke, die Punkte gleichmäßig zu verteilen und dann diese Art von LSH auf jeden Satz anzuwenden, sollte leicht parallelisierbar sein. Wenn Sie Ihren Hashing-Algorithmus so entwerfen, dass die Bucket-Größe in R
definiert wird, ist es wahrscheinlich, dass für eine bestimmte Gruppe von Punkten, die in Buckets unterteilt sind, die Punkte, die Ihren Kriterien entsprechen, wahrscheinlich in den vollständigsten Buckets vorhanden sind. Wenn Sie dies lokal ausgeführt haben, können Sie vielleicht eine Art von Map-Reduction-Strategie anwenden, um räumliche Buckets aus verschiedenen parallelen Läufen des LSH-Algorithmus schrittweise zu kombinieren und dabei die Tatsache zu nutzen, dass Sie beginnen können um Teile Ihres Problembereichs auszuschließen, indem ganze Buckets diskontiert werden. Offensichtlich müssen Sie bei Edge Cases, die sich über verschiedene Buckets erstrecken, vorsichtig sein, aber ich vermute, dass Sie bei jeder Merging-Phase unterschiedliche Bucket-Größen/Offsets anwenden können, um diesen Effekt zu entfernen (z. B. das Zusammenführen räumlich äquivalenter Buckets) als benachbarte Eimer). Ich glaube, dass diese Methode verwendet werden könnte, um die Speicheranforderungen klein zu halten (d. H. Sie sollten nicht viel mehr als die Punkte selbst zu einem bestimmten Zeitpunkt speichern müssen, und Sie arbeiten immer auf kleinen (ish) Teilmengen).
Wenn Sie nach einer Art Heuristik suchen, dann denke ich, dass dieses Ergebnis sofort etwas hervorbringen wird, das einer "guten" Lösung ähnelt - d. H. Es wird Ihnen eine kleine Anzahl wahrscheinlicher Punkte geben, die Sie überprüfen können. Wenn Sie nach einer genauen Antwort suchen, müssen Sie einige andere Methoden anwenden, um den Suchraum zu trimmen, wenn Sie beginnen, parallele Buckets zusammenzuführen.
Ein anderer Gedanke, den ich hatte, war, dass dies auf das Finden der metric k-center beziehen könnte. Es ist definitiv nicht das exakt gleiche Problem, aber vielleicht sind einige der Methoden, die zum Lösen verwendet werden, in diesem Fall anwendbar. Das Problem ist, dass Sie davon ausgehen, dass Sie eine metric space haben, in der die Berechnung der Entfernungsmetrik möglich ist - in Ihrem Fall macht es jedoch das Vorhandensein von einer Milliarde Punkten unerwünscht und schwierig, irgendeine Art von globalem Traversal durchzuführen (z. B. Sortieren der Abstände zwischen Punkte). Wie gesagt, nur ein Gedanke und vielleicht eine Quelle weiterer Inspiration.
Das klingt nach der 3-D-Variante des Set-Covering-Problems !! :-) –
Ihr Problem erinnert mich an "Vector QuantizatioN", die Ihnen einige Ideen geben kann: http://www.data-compression.com/vq.shtml. Auf den ersten Blick sollte das Problem nicht schwer zu lösen sein, wenn Sie diese Einschränkung entfernen * "der Abstand zwischen zwei Punkten dieser oberen N Punkte muss größer sein als R" * - diese Einschränkung verursacht ein großes Problem und erfordert a viel Denken, um es zu überwinden. – SigTerm