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

[Joe Armstrong]

On Tue, May 27, 2014 at 1:26 PM, Tony Rogvall <tony@REDACTED> wrote:

> What about an ets ordered set table?
>

How? - the problem is the key I lookup are not in the table

Suppose I insert keys

    1, 46, 218, 345, 578, 6541, 14671, ....

And I lookup a key 400 - this is not in the list - I'd like
ets:nearest(400, Tab) to return
the key 354 entry - but there is no ets:nearest ...

/Joe



>
> /Tony
>
> On 27 maj 2014, at 12:58, Joe Armstrong <erlang@REDACTED> wrote:
>
>
> 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
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
> "Installing applications can lead to corruption over time. Applications
> gradually write over each other's libraries, partial upgrades occur, user
> and system errors happen, and minute changes may be unnoticeable and
> difficult to fix"
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140527/1fdd2ab2/attachment.htm>