我在空间域中有一个图结构（比如一个密集的社区结构）和一个查询点。我想设计有效的算法+数据结构来计算整个组与查询点之间的距离。

这里一个合适的距离函数可以是平均所有点到查询点的距离。另一种功能可能是取所有距离中的最大值。

我该如何解决这个问题？

我有一张如下表

这是我将如何为此创建索引的方法。

这将创建一个 BTREE 索引。但是我愿意建立一个RTree索引，因为我在做全文搜索。如何在 MySQL 中创建此索引？

我有一个 rtree，其中包含点，即 left == right && top == bottom：

代替点的是一些长代码，它定义了“point”、“newpoint”、“i”以及循环中的所有内容。标有 * 的行返回类似：

问题是如何得到一个点，即（左、下、右、上）知道这个输出？

MacOS Python Rtree 安装 OSError: dlopen(libspatialindex_c.dylib, 6): image not found。

我按照http://toblerity.org/rtree/install.html#nix上的说明进行操作，如下所示：

首先，从以下位置下载并安装libspatialindex库的 1.7.0 版本：

$ ./配置；制作; 进行安装

但是当我这样做时：

$ pip 安装 Rtree。

我收到以下错误：

在 MiniGUI 中，我可以看到db.index. 如何tree.spatial.rstarvariants.rstar.RStartTreeFactory通过 Java 代码将其设置为？

我已经实现：

对于addParameter()函数tree.spatial...RStarTreeFactory类的第二个参数未找到

我越来越NullPointerException。我使用RStarTreeFactory.class正确吗？

我正在使用 libspatialindex ( http://libspatialindex.github.io/ ) 库来构建 r-tree：我正在使用以下代码批量加载 r-tree 中的 (latitude,longitude)。我需要批量加载给定地点的（id、纬度、经度）。以下代码执行批量加载。但我不知道为什么它不接受输入文件——没有关于 libspatial 索引的文档，因此我很困惑。

对于输入，我使用以下文件：

但我收到以下错误：

有人可以帮我看看我哪里出错了！！

我正在尝试使用 ELKI 库实现 DBSCAN 集群测试应用程序。我的数据集是 6 维的，由大约 100.000 个对象组成。

我曾尝试在我的代码中使用 R*-Tree ELKI 优化，但对代码进行基准测试似乎仍然使用 O(n^2)。

这是我在应用程序中使用的代码：

运行上面的代码会导致以下结果：

使用简单的 System.currentTimeMillis() 围绕 dbscan.run(db) 对时间进行基准测试。查看时间列，您可以看到趋势类似于 n^2 而不是 nlog(n)，但我无法理解将 ELKI DBSCAN 与 R*-Tree 优化一起使用时缺少什么。

感谢您的任何帮助或建议。

所以我有大约 7000 万条空间记录要添加到空间层（我用一小部分测试过，一切都很顺利，查询返回与 postgis 相同的结果，层操作似乎很好）但是当我尝试将所有空间记录添加到数据库中，性能迅速下降到在大约 500 万条（大约 2 小时运行时间）记录时变得非常缓慢，并在大约 770 万条（经过 8 小时后）处挂起。

由于空间索引是使用图结构构建自身的 Rtree，我想知道为什么当 os 记录数增加时它会降级。如果我没记错的话，Rtree 插入是 O(n)，这就是为什么我担心它可能是重新排列边界框之间的事情，不是树叶的节点导致 addToLayer 过程随着时间的推移而变慢。

目前我正在向这样的层添加节点（很多硬编码的东西，因为我试图在模式和代码风格之前找出问题）：

有什么想法吗 ？关于如何提高性能的任何想法？

ps.：使用 java API Neo4j 2.1.2，Spatial 0.13 Core i5 3570k @4.5Ghz，32GB ram 专用 2TB 7200 硬盘到数据库（没有操作系统，没有虚拟内存文件，只有数据本身）

ps2.：所有几何图形都是 LineStrings（如果这很重要：P），它们代表街道、道路等。

ps3.：节点已经在数据库中，我只需要将它们添加到图层中，以便我可以执行空间查询，bbox 和 wkb 属性都可以，经过测试并适用于一小部分。

先感谢您

更改并再次运行代码后（仅将点插入数据库需要 5 小时，不涉及层）发生这种情况，将尝试增加 jvm 堆和嵌入式图形内存参数。

28/07 -> 增加内存没有帮助，现在我正在测试 RTreeIndex 和 LayerRTreeIndex 中的一些修改（该字段到底有什么maxNodeReferences作用？

它被硬编码为 100，并且当（明智地添加的节点数）我的addToLayer方法崩溃到 OutOfMemory 错误时，更改其值会发生变化，如果我没记错的话，更改该字段的值会增加或减少树的宽度和深度（比 50 宽 100， 50 比 100 深）。

总结到目前为止的进展：

• @Jim 纠正的交易使用不正确
• 根据@Peter 的建议，内存堆增加到 27GB
• 3 个空间层，但现在问题变得真实，因为它们是大的。
• 在向空间层添加节点时做了一些内存分析，我发现了有趣的点。

内存和 GC 分析： http: //postimg.org/gallery/biffn9zq/

在整个过程中使用最多内存的类型是 byte[]，我只能假设它属于几何 wkb 属性（几何本身或 rtree 的 bbox）。考虑到这一点，我还注​​意到（您可以查看新的分析图像）使用的堆空间量从未低于 18GB 标记。

根据这个问题是java原语垃圾收集java中的原 语类型是原始数据，因此不会受到垃圾收集，并且仅在方法返回时从方法的堆栈中释放（所以也许当我创建一个新的空间层时，所有那些wkb 字节数组将保留在内存中，直到我手动关闭图层对象）。

这有任何意义吗 ？难道没有更好的方法来管理内存资源，这样该层就不会一直加载未使用的旧数据吗？

如何检查boost r-tree中的任何二维点是否在给定的矩形中？这是我在 boost中了解 r-tree 的网站。

但是我很困惑如何检查 r-tree 中的任何点是否位于给定的矩形内。C ++代码将是可观的。

问题

我正在使用 openstreetmap-data 并想测试它们所在的多边形中的点特征。总共有 10.000 个多边形和 100.000.000 个点。我可以将所有这些数据保存在内存中。多边形通常有 1000 个点，因此进行多边形中的点测试非常昂贵。

主意

我可以用 R-Tree 索引所有多边形，允许我只检查边界框被命中的多边形。

可能的新问题

由于多边形相互接触（想想​​行政边界），在不止一个多边形的边界框中有很多点，因此迫使许多点在多边形测试。

问题

你有什么比使用 R-Tree 更好的建议吗？