R-Tree实现Java

我在过去几天中搜索R-Tree的稳定实现，支持无限维（20左右就足够了）。我只发现这个http://sourceforge.net/projects/jsi/，但他们只支持2个维度。R-Tree实现Java

另一个选项将是间隔树的多维实现。

也许我对使用R-Tree或Intervall-Tree来解决我的问题的想法完全错误，所以我简单地说明了问题，您可以发送给我您关于此问题的想法。

我需要解决的问题是某种最近邻居搜索。我有一组天线和房间，每个天线间隔整数。例如。天线1，最小-92，最大-85。实际上，它可以表示为房间 - >天线集合 - >天线间隔。这个想法是，每个房间在R-Tree上跨过天线的维度和每个维度的间隔。

如果我用N天线和每个天线的值得到一个查询，那么我可以仅仅将信息表示为房间中的查询点并检索距离“最近”的房间。

希望你有问题的想法和我的想法。

来源

2011-12-10 drame

nvm它的一个旧线程：请注意，有数据结构专门设计用于支持像M-trees这样的最近邻居查询。 https://en.wikipedia.org/wiki/M-tree –

我并不完全清楚你的确切问题是什么，但是R树或区间树在20个维度中不能很好地工作。这并不是很多维度，但它足以让维度的诅咒开始显现。为了明白我的意思，可以考虑仅仅考虑一个盒子的所有邻居，包括角落和边缘以外的所有邻居。有20个尺寸，您将有3 - 1或3,486,784,400个相邻的盒子。（通过认识到每个轴上的邻居可以是-1单位，0单位或+1单位，但（0,0,0）不是邻居，因为它代表原始框。）

我很抱歉，但你要么需要接受蛮力搜索，要么更好地分析你的问题，并提出一个更聪明的解决方案。

来源

2011-12-10 16:33:43 btilly

Y我知道维度的诅咒。但是我会尝试使用R-Tree，因为20维是最糟糕的情况。也许我甚至可以以某种方式减小尺寸。但我想测试一下，并将其与其他更好的解决方案进行比较。 – drame

这取决于您的数据。我已经在27+维颜色直方图上成功使用了R-Trees。 –

请注意，当您有离散数据时，R-Trees可能会严重降级。你首先需要找出合适的数据表示，然后测试你的查询是否适用于数据的一个子集。

R-Trees只会让您的查询更快。如果他们一开始不工作，这将无济于事。 你应该先测试你的方法，而不要先使用R-Trees。除非您点击大量数据（比如100.000个对象），否则内存中的线性扫描可以轻松地胜过R-Tree，特别是当您需要某个适配器层时，因为它与代码没有很好的整合。

这里明显的方法是只使用使用边界矩形，并线性扫描它们。如果它们能够工作，则可以将MBR存储在R-Tree中以获得一些性能改进。 但是，如果它不与线性扫描工作，也不会与R-树工作，要么（它不会工作得更快。）

来源

2011-12-11 13:24:41

是的。但是为了测试，我首先需要一个可行的实现。 ;） – drame

是的，但不是R-Tree。只需通过线性扫描来完成！再次; R-树只会*加速*，而不能解决以前无法完成的任何任务。 –

加速正是我想要的。因此我正在寻找一个通用的，免费的，稳定的实现。例如在背景中使用红黑树的TreeMap的本地实现。 – drame

我发现这个R *在Java中实现-Tree这似乎提供许多功能：

https://github.com/davidmoten/rtree

你可能想看看！

来源

2015-03-06 16:20:36 Phil

这里还有一个3D版本：https：//github.com/davidmoten/rtree-3d – Warkst

在Java中的另一个很好的实现是ELKI：https://elki-project.github.io/。

来源

2016-12-13 14:37:06 user3282611

回答

相关问题