Very interesting model that suffers from a couple of things that other data structures solve better IMO. One thing that I don't understand and I guess I have to go back and read the article again, is how the distance from any node X to the arbitrarily selected root M tells me anything about the distance between X and the query term Q. If I live in London and the distance from me to Paris is 50.000 km, and you live in Rome, 70.000 km from Paris, that does not give me enough to calculate the distance between Rome and London.

IMO there is no data structure better suited for a search tree than the doubly-chained character trie [0], as it has the following features:

- small in memory (every word is stored once at the most, but more often less than once)

- traversing and doing exact matching allow you to prune half of the tree at every step

- requires you to calculate the distance only at querying time, not when constructing the tree

- apart from exact and fuzzy matches also support prefix matches (traverse up to the path of the prefix, return all children that are EndOfWords)

- can be represented on disk in a way that makes reading insignificantly slower than reading from memory

- if nodes are lexically sorted when tree is constructed, you have also pretty much solved range queries

[0] https://github.com/kreeben/resin/blob/master/src/Resin/IO/Lc...

The trie is to be the perfect tool for when you find yourself combatting big data. What you find out eventually about all of the cloud offerings from all of the big players that claim they will solve both storing and map/reducing over your data is that you can do the same thing on your laptop, for cheap money, as long as the data is represented in a compressed form that still allow for querying. The trie is a zip file and a search engine in one.

Edit: formatting and clarification