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

[Joe Armstrong]

You mean

test() ->
    E = ets:new(test, [ordered_set]),
           ets:insert(E, [{1,a},
   {22,b},
   {32,c},
   {47,d},
   {55,e},
   {97,f}]),
    N = ets:next(E, 40),
    P = ets:prev(E, 40),
    {N,P}.

Seems to work - so to find the K nearest I just iterate prev and next
keeping track of
which direction I have to move - very nice.

I had assumed that ets:next needed a pre-existing key in the table to
perform a
next or prev operation.

Problem solved - very neatly

Thanks

/Joe






On Tue, May 27, 2014 at 2:12 PM, Jesper Louis Andersen <
jesper.louis.andersen@REDACTED> wrote:

> Use ets:next/1 and ets:prev/1 to expand a window from your target key.
> They work even if the initial key is not in the window. This should be
> fairly easy to implement for the 1d case. For higher-dimensional cases,
> k,d-trees is a favorite of mine.
>
>
>
> On Tue, May 27, 2014 at 2:10 PM, Joe Armstrong <erlang@REDACTED> wrote:
>
>>
>>
>> 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"
>>>
>>>
>>>
>>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>
>
> --
> J.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140527/13e81558/attachment.htm>