<p>Since the <a href="https://github.com/neo4j-contrib/neo4j-apoc-procedures/blob/4.0/src/main/java/apoc/text/Strings.java" rel="nofollow noreferrer">implementations</a> of <code>apoc.text.levenshteinDistance</code> and <code>apoc.text.levenshteinSimilarity</code> simply rely on <a href="https://commons.apache.org/proper/commons-text/apidocs/org/apache/commons/text/similarity/LevenshteinDistance.html" rel="nofollow noreferrer">org.apache.commons.text.similarity.LevenshteinDistance</a> to do the calculation, the APOC library does not introduce any complexity improvements.</p>

<p>In any case, such a calculation should just compare 2 strings of text and should not in any way rely on the graphical nature of the DB.</p>

<p>And finally, <a href="https://ui.adsabs.harvard.edu/abs/2014arXiv1412.0348B/abstract" rel="nofollow noreferrer">it has been proven</a> that the complexity <strong>cannot</strong> be improved (unless the <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">Strong Exponential Time Hypothesis</a> is wrong).</p>
Does the Levenshtein (Edit Distance) algorithm perform faster than O(n*m) in a native graph database?
<p>Would the Levenshtein (Edit Distance) have better time complexity in a native graph database such as Neo4j than the current limit of O(n*m)? If so, why?</p>