R树与R中的图划分库

Question

我需要进行有效的d维点搜索，也需要对d维中的一个点进行有效的k查询。因此我需要一个R-树库。我需要一个库来构建R-树结构，我可以在需要的时候使用它来查询。

此外，我还需要一些类似于梅蒂斯或hMETIS的库，尽管我的应用程序不涉及超图。我的要求是找到一个图的最小割集，它把图划分成大约两个大小相等的图。

问题是，我需要在R中支持这些的库。

我已经找到了一个库兰恩，它具有基于kd-树的k-NN查询，但问题是，要么我必须一次完成所有kd查询并将结果存储在一个巨大的数组中，要么需要每次需要时调用该函数(nn或nn2)，这与O(n lg n)检索增长的时间增长背道而驰。

有人能告诉我R中是否有这样的图书馆吗？

注意:为了高效地实现聚类算法，我需要R-树库，而实现变色龙聚类算法需要图形分区库。

Answer 1

在研究了R及其库之后，我认为最好用C或C++编写自己的代码，然后通过.C()或.Call() R到C语言接口使用它。

Answer 2

此外，我还需要一些类似METIS或hMETIS的库，尽管我的应用程序不涉及超图。我的要求是找到一个图的最小割集，它把图划分成大约两个大小相等的图。

尽管这是一个古老的问题，我最近写了这样的东西。那是,

1. 像Kernighan那样的算法。
2. 利用Chlebíková(1996)提出的方法寻找一个近似连通的平衡划分的算法。
3. 一种算法，它采用该方法在2中找到的解，并尝试使用Kernighan类算法将降价最小化，同时仍然要求分区中的两个集合是连接的。

从我正在处理的图中，3.似乎经常能找到一个很好的解决方案--通常是对于较大的图(例如~ 1-4百万条边，有大约100万个顶点)。这需要几秒钟或几分钟。实现在https://github.com/boennecd/pedmod的pedmod包中。请拨打以下电话以安装该软件包，并查找包含更多详细信息的小插曲：

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

不过，我不知道与其他软件相比，我的实现在分区的速度和质量方面如何比较。

参考文献

Chlebíková，Janka1996年。“逼近图中的最大平衡连通划分问题。”信息处理信函60 (5)：225-30。

克尼汉，B.W.和S.林。1970年。“一种有效的分割图的启发式方法。”贝尔系统技术期刊49 (2)：291-307