[erlang-questions] Fwd: Re: finding the nearest key in a key-value table
Wed May 28 05:01:26 CEST 2014
On 05/27/2014 01:08 PM, OvermindDL1 wrote:
> Unsure how efficient you could make it in erlang, pretty efficient I think, it sounds like what you want is a Patricia Trie. It by default gets the node you ask for or the nearest matching one with the longest prefix of whatever accuracy you wish, a minor change could just have it go down nearby existing nodes to get the nearest match instead of just the matching based on prefix, especially if you statically know the length of the binaries.
Code for a patricia trie is here https://github.com/okeuday/trie . The source code is more efficient with string() (list of integer) usage, but the same code works with binaries with the separate btrie module (with macro magic). There isn't any nearest functions, but instead functions that match using a string pattern that contains "*" wildcard characters and functions that use a prefix to find similar keys. The nearest function shouldn't be hard to implement, if that was pursued.
More information about the erlang-questions