neo4j - Levenshtein(编辑距离)算法在原生图形数据库中的执行速度是否比 O(n*m) 快？

Question

Levenshtein(编辑距离)在原生图形数据库(如 Neo4j)中的时间复杂度是否会比 O(n*m) 的当前限制更好？如果是这样，为什么？

Answer 1

自 implementations的 apoc.text.levenshteinDistance和 apoc.text.levenshteinSimilarity只需依靠 org.apache.commons.text.similarity.LevenshteinDistance为了进行计算，APOC 库没有引入任何复杂性改进。

在任何情况下，这样的计算应该只比较 2 个文本字符串，并且不应该以任何方式依赖于 DB 的图形特性。

最后，it has been proven复杂性不能 得到改进(除非 Strong Exponential Time Hypothesis 是错误的)。