我正在考虑将 PH 树添加到 ELKI。 我找不到任何示例教程，而且内部架构目前对我来说还不是很清楚。
- 您认为将 PH 树添加到 ELKI 是否有意义？
- 需要付出多少努力？
- 我能得到一些帮助吗？
- 像 kd-tree 那样(据我所知)只实现一个内存版本是否有意义？
一些背景: PH 树是在 SIGMOD'14 上发布的空间索引:paper , Java 源代码可用 here . 它有点类似于四叉树，但空间效率更高，不需要重新平衡并且可以很好地扩展维度。 PH-tree 与 R*-Tree 实现的不同之处在于没有叶子/内部节点的概念，并且节点不会直接映射到页面。它也适用于随机插入/删除(不需要批量加载)。
最佳答案
是的。
当然，如果在 ELKI 中有一个 PH 树，以允许其他人使用它进行试验，那就太好了。我们希望ELKI成为一个综合工具；它有 R 树、M 树、k-d 树、覆盖树、LSH、iDistance、倒排列表、空间填充曲线、PINN 等； X-tree、rank-cover-trees、bond 等有一些工作但尚未清理的实现。
我们想让研究人员能够轻松地研究哪种索引最适合他们的数据，当然，如果有 PH-tree 也很好。我们还尝试突破这些指标的极限，例如当支持欧氏距离以外的其他距离度量时。
努力取决于您在编码方面的经验； ELKI 使用了一些优化良好的数据结构，但这意味着出于性能考虑，我们在许多地方并没有使用标准的 Java API。例如，添加覆盖树花了我大约一天的时间(而且效果非常好)。我假设一个更灵活(但也更占用内存)的 k-d-tree 将有类似的工作量。我没有详细研究 PH 树，但我认为它比那稍微多一些努力。 我的胆量还说它不会像宣传的那样快。它似乎是一个前缀压缩的四叉树。在我的实验中，希尔伯特曲线所需的位交错方法可能非常昂贵。它也可能只适用于 Minkowski 指标。但欢迎你证明我错了。 ;-)
随时欢迎您在邮件列表或此处寻求帮助。
我会先做一个内存变体，以充分理解索引。然后对其进行基准测试以确定优化潜力，并对其进行调试。在那之前，您可能还没有弄清楚所有的极端情况，例如重复点处理、退化数据集等。
始终将磁盘上设为可选。如果您的数据适合内存，则纯内存实现将比任何磁盘版本快得多。
在为 ELKI 做贡献时，请:
- 避免外部依赖。我们在质量方面有过糟糕的经验。 Apache Commons，我们希望这个包易于安装和维护，所以我们希望将 .jar 依赖项保持在最低限度(此外，拥有大量具有冗余功能的 jar 会以性能成本为代价)。我倾向于只接受可选扩展模块的外部依赖。
- 不要从其他来源复制代码。 ELKI 已获得 AGPL-3 许可，对 ELKI 本身的任何贡献也应获得 AGPL-3 许可。在某些情况下，可能包括例如公共(public)域代码，但我们需要将它们保持在最低限度。我们可能使用 Apache 许可代码(在外部库中)，但不应混合使用它们。因此，快速浏览一下，您不能将其源代码复制到 ELKI 中。
如果您正在寻找数据挖掘项目的想法，这里是我们希望看到的对 ELKI 有贡献的文章/算法列表(我们会为学生实现项目更新此列表) :
关于indexing - 将 PH-Tree 添加到 ELKI，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31682151/