[erlang-questions] finding the nearest key in a key-value table

[Evgeny M]

There's a library which could be used for this task with minor modifications
https://github.com/brigadier/bisect/blob/master/src/bisect.erl
have a look on the floor() function
Just a standard binary search over large binary blob. If Key not found just 
step back the position from the last seek operation and copy the binary to 
the end.

вторник, 27 мая 2014 г., 14:58:36 UTC+4 пользователь Joe Armstrong написал:
>
>
> What's the best data structure to support a "nearest key" operation?
>
> I want a data structure that supports the following operations:
>
>      new() -> NewTree
>
>      insert(Key, Value, Tree) -> NewTree
>      
>     delete(Key, Tree)  -> NewTree
>    
>     nearest(Key, N, Tree)     -> [{Key1,Val1},{Key2,Val2} ...].
>
>     Keys are 20 byte binaries, values are 6 byte binaries
>
>     The maximum number of keys of Key-Value pairs is 10 million.
>
>    nearest(Key, N, Tree) returns the N nearest items to Key in the tree
>
>    "near" means that the keys are near to each other. Often the key I want 
> will not
> be in the tree, so I want nearby keys. The nearness measure is just the
> "distance" between the two keys (ie the nearest N keys to the given key if 
> the keys were to
> be sorted)
>
> Are there any Erlang libraries that do this?
>
> /Joe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140527/3f2763b9/attachment.htm>