<p>The problem you're describing is a <strong>Nearest Neighbor Search (NNS)</strong>. There are two main methods of solving NNS problems: <strong>exact</strong> and <strong>approximate</strong>.</p>

<p>If you need an exact solution, I would recommend a <strong>metric tree</strong>, such as the <strong>M-tree</strong>, the <strong>MVP-tree</strong>, and the <strong>BK-tree</strong>. These trees take advantage of the triangle inequality to speed up search.</p>

<p>If you're willing to accept an approximate solution, there are much faster algorithms. The current state of the art for approximate methods is <a href="https://arxiv.org/abs/1603.09320" rel="nofollow noreferrer">Hierarchical Navigable Small World (hnsw)</a>. The <a href="https://github.com/nmslib/nmslib" rel="nofollow noreferrer">Non-Metric Space Library (nmslib)</a> provides an efficient implementation of hnsw as well as several other approximate NNS methods.</p>

<p>(You can compute the Levenshtein distance with <a href="https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm" rel="nofollow noreferrer">Hirschberg's algorithm</a>)</p>
Finding the most similar string among a set of millions of strings
<p>Let's say I have a dictionary (word list) of millions upon millions of words. Given a query word, I want to find the word from that huge list that is most similar.</p>

<p>So let's say my query is <code>elepant</code>, then the result would most likely be <code>elephant</code>.</p>

<p>If my word is <code>fentist</code>, the result will probably be <code>dentist</code>.</p>

<p>Of course assuming both <code>elephant</code> and <code>dentist</code> are present in my initial word list.</p>

<p>What kind of index, data structure or algorithm can I use for this so that the query is fast? Hopefully complexity of <code>O(log N)</code>.</p>

<p><strong>What I have:</strong> The most naive thing to do is to create a "distance function" (which computes the "distance" between two words, in terms of how different they are) and then in O(n) compare the query with every word in the list, and return the one with the closest distance. But I wouldn't use this because it's slow.</p>