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
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.
>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.
Yes, but you do know that the distance from London to Rome is less than 12,000 km, because of the triangle inequality axiom. So if that's too far, that search path is discarded.
Then we just start the process over again, by comparing each subtree back to the original location.
I'm struggling with finding a use case for that data structure through. Why would you construct a BK-tree that would only become powerful when it contains millions of words, which would then create a nuisance when representing that amount of data in memory, making it not so fast anymore, when you could represent the same data in a compressed form and with the same (as well as an extended set of) querying capabilities?
Perhaps BK-trees are for big machines with powerful CPUs? I'm sure there is a setup that would make that tree in fact better than any other tree.
I don't think the best use case for BK-trees is spell-checking and words. The area in which they are used most successfully is image deduplication. In that case the metric you're going to use is some form of perceptual hashing.
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