R Baum- und Graphpartitionierungsbibliothek in R

Question

Ich muss effiziente d-dimensionale Punkte suchen und auch effiziente k-NN-Abfragen eines Punktes in d-Dimension machen. Daher benötige ich eine R-Tree Bibliothek. Ich benötige eine Bibliothek, die die R-Tree-Struktur zu bauen, die ich verwenden können, um Abfrage, wann immer benötigt.

Außerdem benötige ich eine Bibliothek wie die von METIS o hMETIS obwohl es bei meiner Anwendung nicht um Hypergraphen geht. Meine Anforderung ist es, die minimale Schnittmenge eines Graphen zu finden, die den Graphen in ungefähr zwei gleich große Graphen unterteilt.

Die Sache ist die, dass ich Bibliotheken benötigen würde, die diese in R unterstützen.

Ich habe eine Bibliothek gefunden RANN , die kd-Baum-basierte k-NN-Abfragen hat, aber das Problem ist, dass ich entweder alle k-NN-Abfragen auf einmal machen und die Ergebnisse in einem großen Array speichern muss, oder die Funktion aufrufen muss ( nn o nn2 ) jedes Mal, wenn ich es brauche, was den O(n lg n)-Zeitzuwachs bei der Suche zunichte macht.

Kann mir jemand sagen, ob es solche Bibliotheken in R gibt?

Anmerkung: Ich benötige die R-Tree-Bibliothek, um Clustering-Algorithmen effizient zu implementieren, und die Graphpartitionsbibliothek, um den CHAMELEON-Clustering-Algorithmus zu implementieren.

Answer 1

Nach einigen Studien über R und seine Bibliotheken denke ich, dass es besser ist, die benötigten Bibliotheken zu besorgen oder meinen eigenen Code in C oder C++ zu erstellen und ihn dann über das .C() o .Call() Schnittstelle von R zur Sprache C.

Answer 2

Außerdem benötige ich eine Bibliothek wie die von METIS oder hMETIS, obwohl meine Anwendung keine Hypergraphen beinhaltet. Meine Anforderung ist es, die minimale Schnittmenge eines Graphen zu finden, die den Graphen in ungefähr zwei gleich große Graphen unterteilt.

Obwohl dies eine alte Frage ist, habe ich kürzlich etwas Ähnliches geschrieben. Das ist,

1. Ein Kernighan-Lin-ähnlicher Algorithmus.
2. Ein Algorithmus zum Finden einer annähernd zusammenhängenden ausgeglichenen Partition nach der von Chlebíková (1996) vorgeschlagenen Methode.
3. Ein Algorithmus, der die mit der Methode in 2. gefundene Lösung nimmt und versucht, den Schnittpreis mit einem Kernighan-Lin-ähnlichen Algorithmus zu minimieren, wobei die beiden Mengen in der Partition immer noch verbunden sein müssen.

Bei den Graphen, mit denen ich arbeite, scheint 3. oft eine recht gute Lösung für größere Graphen zu finden (z.B. ~ 1-4 Millionen Kanten mit ~ 1 Million Eckpunkten). Das dauert Sekunden oder ein paar Minuten. Die Implementierung befindet sich im Paket pedmod unter https://github.com/boennecd/pedmod . Rufen Sie den folgenden Befehl auf, um das Paket zu installieren und eine Vignette mit weiteren Einzelheiten zu finden:

remotes::install_github("boennecd/pedmod", build_vignettes = TRUE)
vignette("pedigree_partitioning", package = "pedmod")

Ich bin mir allerdings nicht sicher, wie meine Implementierung in Bezug auf Geschwindigkeit und Qualität der Partition im Vergleich zu anderer Software abschneidet.

Referenzen

Chlebíková, Janka. 1996. "Approximating the Maximally Balanced Connected Partition Problem in Graphs". Information Processing Letters 60 (5): 225-30.

Kernighan, B. W., und S. Lin. 1970. "An Efficient Heuristic Procedure for Partitioning Graphs". The Bell System Technical Journal 49 (2): 291-307