问题标签 [r-tree]

我正在尝试使用 JSI RTree 实现https://github.com/aled/jsi为我的应用程序索引地理位置。我用大约 7M 条目加载它，然后使用包含马萨诸塞州和康涅狄格州周围的边界框的 contains 方法对其进行查询。返回的结果实际上并不在那个边界框中。这是用户错误还是 RTree 实现中的错误？

这是我的边界框：

矩形 r = 新矩形(-73.630F,43.185F,-69.675F,40.946F);

返回的许多错误结果之一就是这个

“经度”：-74.24565887，“纬度”：40.66231918

......但其中许多离箱更远。

我检查过我没有不小心将索引中的 ID 错误地映射到错误的数据。

当我进行一些初始测试时，我在索引中添加了几十个点并使用边界框查询它，发现结果是准确的。所以我很难过。希望有人有一些建议。

这些是来自http://elki.dbs.ifi.lmu.de/的引号：

“本质上，我们将抽象距离查询绑定到数据库，然后对这个距离进行最近邻搜索。此时，ELKI 会自动选择最合适的 kNN 查询类。如果存在适合我们距离函数的索引（不是每一个索引都能加速每一个距离！），这里会自动使用。”

“getKNNForDBID 方法可能归结为缓慢的线性扫描，但是当数据库有合适的索引时，会使用索引查询。然后算法可以在 O(nk log n) 甚至 O(nk) 时间内运行。”

问题是：ELKI 选择运行索引查询的依据是什么？

什么是：“当数据库有适当的索引时”，我如何保证？

关于“运行”方法签名的另一个不相关的问题，为什么有 3 个签名而不是只有 1 个？它们之间有什么区别，确定使用哪个签名的标准是什么？

如何快速找到一组多边形中的哪一个包含给定点？

我在POSTGis数据库中有一组多边形。我在 ruby​​ 端使用RGeo来操作、保存和从数据库中提取信息。

我从外部机器接收到一个点（x 和 y 坐标），并且需要知道该点位于我的哪个多边形内。我不能使用数据库，因为出于性能原因我需要在内存中完成此操作。

我相信我可能需要一个r-tree，但我并不完全想写一个。

RGeo提供了一种contains?方法，我可以使用它来确保一个点在感兴趣的多边形内，但我需要知道要检查哪个多边形。我有大约 1,000 个多边形，进行线性搜索的时间效率不足以满足我的需求。

我在 5 维空间中有大约 10 K 点。我们可以假设这些点在空间 (0,0,0,0,0) 和 (100,100,100,100,100) 中随机分布。显然，整个数据集可以很容易地驻留在内存中。

我想知道 k 最近邻的哪种算法运行得更快，kd-tree 或 RTree。

尽管我对这两种算法有一些非常高级的想法，但我不确定哪个会运行得更快，以及为什么。如果有的话，我愿意探索其他可以快速运行的算法。如果可能，请说明算法运行速度更快的原因。

我有一个地板，在地板上的不同位置放置了各种传感器。对于每个传输设备，传感器可能会检测到其读数。地板上可能有 6-7 个传感器，并且某些传感器可能无法检测到特定读数，但可能会被其他一些传感器检测到。

对于我得到的每一个读数，我想确定那个读数在地板上的位置。我们在逻辑上将地板划分为 TILE（5x5 英尺区域），并找到每个 TILE 的理想读数应该由每个传感器设备检测到（基于一些传输路径损耗方程）。

我使用来自每个 TILE 的“N”传感器设备的预计算读数作为 N 维空间中的一个点。当我得到一个真实的生活读数时，我会找到这个读数最近的邻居，并将这个读数分配给那个位置。

我想知道是否有 K 最近邻的变体，其中一个维度可以从考虑中删除。当特定传感器未报告任何读数时，这将特别有用。我知道使用 kd-tree 或 R 树之类的算法不可能对维度进行加权。但是，我想知道在计算最近邻时是否可以丢弃维度。有没有这样的算法？

编辑：

我想知道的是，相同的 R/kd 树是否可以用于具有不同查询的 k 最近搜索，其中每个查询具有不同的维度权重？我不想为每个不同的维度权重构建另一个 kd-tree。

编辑2：

python中是否有任何库，可让您指定自定义距离函数并搜索k个最近邻居？本质上，我想对不同的查询使用不同的自定义距离函数。

我遇到的问题是矩形中有矩形。想想一张地图，除了以下特征，关键点是：具有相似密度的矩形通常与其他矩形共享相似的尺寸和在 x 轴上的相似位置，但有时这些矩形之间的距离可能很大但通常很小。如果 x 轴上的位置或尺寸明显偏离，它们就不会相似。

• 矩形不相交，较小的矩形完全位于较大的矩形内。

• 矩形通常具有相似的 x 位置和相似的尺寸（相似的高度和宽度），并且内部具有较小的矩形。矩形本身将被视为它自己的集群。

• 有时这些集群与另一个集群的距离可能相当大（想想岛屿）。通常这些簇共享相同或相似的维度以及相同或相似的子矩形密度。如果是这样，尽管两个集群之间存在距离，但它们应被视为同一集群的一部分。

• 矩形越密集（内部的矩形越小），附近有相似或相同的密集矩形共享相同或相似维度的可能性就越大。

我附上了一张图表来更清楚地描述这种情况：

• 红色边框表示这些组是异常值，不属于任何集群并被忽略。

• 蓝色边框有很多簇（黑色边框包含黑色实心矩形）。由于上述标准（相似的宽度、相似的 X 位置、相似的密度），它们形成了一组相似的集群。由于标准（相似的宽度、相似的 X 位置、相似的密度），即使是右下角的集群仍然被认为是该组的一部分。

• 绿松石边框有很多簇（黑色边框包含黑色实心矩形）。然而，这些集群在维度、x 位置和密度上与蓝色边框中的集群不同。他们被认为是他们自己的一个群体。

到目前为止，我发现 DBSCAN 之类的密度聚类似乎很完美，因为它考虑了噪声（异常值），而且您不需要提前知道会有多少聚类。

但是，您需要定义形成集群所需的最小点数和阈值距离。如果您不知道这两个会发生什么，并且它可能会根据上述问题而有所不同？

另一个看似合理的解决方案是分层（凝聚）聚类（r-tree），但我担心我仍然需要知道树深度级别的截止点以确定它是否是一个集群。

我正在桌面和 android 上的 sqlite 数据库上执行以下查询：

这是数据的结构

这是 android 上面 EXPLAIN QUERY 的结果

这是桌面的结果

桌面上的 sqlite 是使用 apt-get 安装的，而 android 上的 sqlite 是使用源代码中的以下选项编译的：

sqlite不在android上使用索引的原因可能是什么？行验证是两个表中的主键，因此除了在 r​​tree 的子查询中完成的扫描之外，不应进行任何扫描。

什么是STR树？它与 R-tree 有什么不同？. 每当我搜索“STR-trees”时，我都会得到 R-tree 的搜索结果。有人可以帮我弄这个吗 ？

我正在使用 JTS 和 Netbeans 来实现 STRtrees 。我正在尝试为一组点（坐标）构建一个 STRtree。这是我的代码：

代码符合并运行，但我希望这些点按此顺序排序（roots->children->leaves）。但我的输出包含包络区域中的随机点。我哪里做错了？

在当前场景中，我有一个 Rtree 实例，我在其中添加了数百万条记录，这需要大约 1 小时来创建。我想知道是否可以使用多个映射器来创建多个 RTree，然后将它们合并到 reducer 中以创建最终的 RTree？是否有特定的合并 Rtree 技术可用？我应该如何解决这个问题？任何帮助都非常感谢？