3

嗨，我一直在尝试为 Neo4j 实现 DBSCAN 算法，但遇到了严重的性能瓶颈。我将描述实现，然后寻求帮助。

我对可能的 epsilon 值进行了离散化，并将每个节点的每个离散化下的邻居数计数，以便能够在一个查询中检索所有核心节点。

START a = node(*)
WHERE a.rel<cutoff threshold>! >= {minp}
RETURN a

这部分很快，不快的部分是后续查询：

START a = node({i})
SET a.label<cutoff threshold>_<minpoints> = {clust}
WITH a
MATCH a -[:'|'.join(<valid distance relations>)]- (x)
WHERE not(has(x.label<cutoff threshold>_<minpoints>))
WITH x
SET x.label<cutoff threshold>_<minpoints>={clust}
RETURN x

然后我选择一个核心节点开始，只要还有核心节点邻居，运行上面的查询来标记他们的邻居。

我认为问题在于我的图具有非常不同的稀疏度 - 从只有弱相似性开始，它几乎是完全连接的，在 ~10k 节点之间有 ~50M 关系，而在强相似性时，~10k 之间的关系只有 ~20k节点（或更少）。无论如何，它总是真的很慢。我处理这个问题的最佳方法是什么？是否对关系类型和起始节点进行索引？我还没有找到关于这个问题的任何资源，而且令人惊讶的是还没有实现，因为这是一个非常标准的图形算法。我可以使用 scikit.learn 但我将仅限于内存中的距离矩阵:(

4

2 回答 2

0

你用什么版本的neo4j试过这个？

在 1.8 之前，性能一直不是 cypher（而是语言）的设计目标。看看最近的快照（1.9-SNAP）。

还要确保您的热数据集不只是从磁盘加载（否则您测量磁盘 io），以便您的内存映射设置和 JVM 堆足够大。

您可能还想查看 Neo4j 企业的 GCR 缓存，它具有较小的内存占用。

count(x)您的查询中的基数是什么？如果它太小，您有太多的小交易正在进行。取决于您运行的 python 嵌入式或 REST 是否使用更大的 tx-scope 或REST-batch-operations

您已经在使用非常棒的参数。你的 rel 类型的可变性是什么？

有没有机会与我们（Neo4j）分享您的数据集/生成器和代码，以便我们进行性能测试？

于 2012-09-28T15:31:20.800 回答
0

有一些使用索引的 DBSCAN 实现。我不了解，所以我无法确定您的方法是否有效。您可能需要预先计算的东西实际上是图的稀疏版本，只有在 epsilon 阈值内的边。

我想指出的是，显然您的数据集中有不同的密度，因此您可能想改用 OPTICS，它是 DBSCAN 的一种变体，它取消了 epsilon 参数（并且也不需要区分“核心”节点，因为每个节点都是某个 epsilon 的核心节点）。不要使用 Weka 版本（或浮动的受 weka 启发的 python 版本）。它们是一半 OPTICS 和一半 DBSCAN。

当您有可用的有效排序更新堆时，OPTICS 可以非常快。

于 2012-09-28T06:18:53.717 回答