您好,我一直在尝试为 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 关系,而在强相似性下只有~20k 关系在 ~10k 个节点(或更少)之间。无论如何,它总是非常慢。我处理这个问题的最佳方法是什么?是根据关系类型和起始节点建立索引吗?我还没有找到关于这个问题的任何资源,令人惊讶的是还没有实现,因为这是一个非常标准的图形算法。我可以使用 scikit.learn,但那样我就只能使用内存中的距离矩阵了 :(
最佳答案
您使用的是什么版本的 neo4j?
直到 1.8 性能一直不是 cypher 的设计目标(而是语言) 查看最近的快照 ( 1.9-SNAP )。
还要确保你的热数据集不只是从磁盘加载(否则你测量磁盘 io)所以你的 memory mapped settings而且 JVM 堆也足够大。
您可能还想检查 Neo4j enterprise 的 GCR 缓存,它具有较小的内存占用量。
查询中 count(x)
的基数是多少?如果它太小,你有太多的小交易正在进行。取决于您运行的 python embedded 或 REST 使用更大的 tx-scope 还是 REST-batch-operations
您已经在使用很棒的参数。您的 rel-types 的可变性是什么?
是否有机会与我们 (Neo4j) 分享您的数据集/生成器和代码,以便在我们这边进行性能测试?
关于python - 在 Cypher/Python 中为 neo4j 优化 DBSCAN,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12632736/