4

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

我还需要一些像METIS或hMETIS这样的库，尽管我的应用程序不涉及超图。我的要求是找到一个图的最小割集，它将图分成大致相等大小的两个图。

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

我找到了一个库RANN，它具有基于 kd-tree 的 k-NN 查询，但问题是我必须一次进行所有 k-NN 查询并将结果存储在一个巨大的数组中，或者需要调用每次我需要时都使用函数（nn或），这会破坏 O(n lg n) 检索时间的增长。nn2

谁能告诉我R中是否有这样的库？

注意：我需要 R-Tree 库来有效地实现聚类算法，并且需要图形分区库来实现 CHAMELEON 聚类算法。

4

2 回答 2

4

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

于 2012-06-19T12:54:46.030 回答
0

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

尽管这是一个老问题，但我最近写了类似的东西。那是，

  1. 类似 Kernighan-Lin 的算法。
  2. 使用 Chlebíková (1996) 建议的方法找到近似连接的平衡分区的算法。
  3. 一种算法，采用 2. 中的方法找到的解决方案，并尝试使用类似 Kernighan-Lin 的算法来最小化降价，同时仍然要求分区中的两个集合是连接的。

从我正在使用的图表中，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á，扬卡。1996. “在图中逼近最大平衡连通分区问题”。信息处理快报 60 (5): 225–30。

Kernighan、BW 和 S. Lin。1970.“划分图的有效启发式程序”。贝尔系统技术杂志 49 (2): 291–307

于 2021-05-20T06:13:36.457 回答