R-Tree实现Java

Question

我在过去的几天里一直在寻找R-Tree的稳定实现，支持无限的维度(20个左右就足够了)。我只找到了这个http://sourceforge.net/projects/jsi/，但它们只支持2个维度。

另一种选择是区间树的多维实现。

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

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

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

希望你对这个问题和我的想法有所了解。

Answer 1

请注意，当您具有离散数据时，R树可能会严重退化。您真正需要找出的第一件事是适当的数据表示，然后测试您的查询是否在数据的子集上工作。

R-Trees只会让你的查询速度更快。如果它们一开始就不起作用，那就不会有什么帮助。除非你遇到了大量的数据(比如100.000个对象)，否则内存中的线性扫描可以很容易地胜过R树，特别是当你需要一些适配器层时，因为它与你的代码没有很好地集成。

这里最明显的方法是使用边界矩形进行，然后线性扫描它们。如果它们有效，那么您可以将MBR存储在R-Tree中，以获得一些性能改进。但是如果它不适用于线性扫描，那么它也不适用于R树(它不会更快地工作。)

Answer 2

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

https://github.com/davidmoten/rtree

你可能会想去看看它！

Answer 3

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