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

Question

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

Answer 1

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

无论如何，这样的计算应该只比较 2 个文本字符串，而不应该以任何方式依赖于数据库的图形性质。

最后，it has been proven复杂性无法提高(除非Strong Exponential Time Hypothesis是错误的)。