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

[Jesper Louis Andersen]

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/9eaacdeb/attachment.htm>