2

我正在考虑将 PH 树添加到 ELKI。我找不到任何示例教程，而且目前内部架构对我来说并不完全清楚。

  1. 你认为将 PH-tree 添加到 ELKI 中有意义吗？
  2. 那要付出多大的努力？
  3. 我能得到一些帮助吗？
  4. 只实现内存版本是否有意义，就像对 kd-tree 所做的那样（据我所知）？

一些上下文：PH-tree 是在 SIGMOD'14 上发布的空间索引：论文，Java 源代码可在此处获得。它有点类似于四叉树，但空间效率更高，不需要重新平衡并且可以很好地扩展维度。PH-tree 与 R*-Tree 实现的不同之处在于没有叶子/内部节点的概念，并且节点不会直接映射到页面。它也适用于随机插入/删除（不需要批量加载）。

4

1 回答 1

1

是的。

当然，如果在 ELKI 中有一个 PH-tree，让其他人进行试验，那就太好了。我们希望 ELKI 成为一个综合性的工具；它有 R-trees、M-trees、kd-trees、cover-trees、LSH、iDistance、倒排列表、空间填充曲线、PINN、...；X-tree、rank-cover-trees、bond 等有一些工作但未清理的实现。

我们希望让研究人员能够轻松地研究哪种索引最适合他们的数据，当然拥有 PH-tree 也会很好。我们还尝试突破这些指标的限制，例如在支持欧几里得距离以外的其他距离度量时。

工作量取决于您在编码方面的经验；ELKI 使用了一些优化良好的数据结构，但这意味着我们在很多地方没有使用标准的 Java API，因为性能原因。例如，添加封面树花了我大约一天的时间（它表现得非常好）。我假设更灵活（但也更占用内存）的 kd-tree 将是类似的工作量。我没有详细研究过 PH-tree，但我认为它比这更努力。我的胆量还说它不会像广告宣传的那么快。它似乎是一个前缀压缩的四叉树。在我的实验中，希尔伯特曲线所需的比特交错方法可能非常昂贵。它也可能仅适用于 Minkowski 指标。但欢迎你证明我错了。;-)

随时欢迎您在邮件列表或此处寻求帮助。

我会先做一个内存变体，以完全理解索引。然后对其进行基准测试以识别优化潜力并对其进行调试。在那之前，您可能还没有弄清楚所有极端情况，例如重复点处理、退化数据集等。

始终使磁盘上可选。如果您的数据适合内存，那么纯内存实现将比任何磁盘版本快得多。

在为 ELKI 做贡献时，请：

  • 避免外部依赖。我们对例如 Apache Commons 的质量有过不好的体验，我们希望该软件包易于安装和维护，因此我们希望将 .jar 依赖项保持在最低限度（此外，还有大量具有冗余功能的 jar以性能为代价）。我倾向于只接受可选扩展模块的外部依赖项。
  • 不要从其他来源复制代码。ELKI 已获得 AGPL-3 许可，对 ELKI 本身的任何贡献也应获得 AGPL-3 许可。在某些情况下，可能包括例如公共领域的代码，但我们需要将这些保持在最低限度。我们可能可以使用Apache 许可代码（在外部库中），但不应该混合使用它们。因此，快速浏览一下，您是不允许将他们的源代码复制到 ELKI 中的。

如果您正在寻找数据挖掘项目的想法，这里是我们希望看到对 ELKI 做出贡献的文章/算法列表（我们会为学生实施项目更新此列表）：

http://elki.dbs.ifi.lmu.de/wiki/ProjectIdeas

于 2015-07-29T08:36:23.770 回答