<div class="gmail_quote">---------- Forwarded message ----------<br>From: "Benoit Chesneau" <<a href="mailto:bchesneau@gmail.com">bchesneau@gmail.com</a>><br>Date: May 27, 2014 4:31 PM<br>Subject: Re: [erlang-questions] finding the nearest key in a key-value table<br>
To: "Dmitry Kolesnikov" <<a href="mailto:dmkolesnikov@gmail.com">dmkolesnikov@gmail.com</a>><br>Cc: <br><br type="attribution"><p dir="ltr"><br>
On May 27, 2014 1:23 PM, "Dmitry Kolesnikov" <<a href="mailto:dmkolesnikov@gmail.com" target="_blank">dmkolesnikov@gmail.com</a>> wrote:<br>
><br>
> Hello,<br>
><br>
> r-tree / kd-tree might be use-full for you to handle “nearest” lookup.<br>
> however, I am not aware of efficient implementation on Erlang.<br>
></p>
<p dir="ltr">here is an implementation of an rtree in erlang. not sure how much efficient it is but it works.<br></p>
<p dir="ltr">> Another, the best possible “available” option for your problem domain is sorted trees.<br>
> It gives you log N complexity. If the key distance is multi-dimentional then z-ordered<br>
> curve technique would help you to cluster “nearby” keys.<br>
><br>
> You might take a look into my modification of gb_trees that allows to execute range queries (via iterator).<br>
> <a href="https://github.com/fogfish/feta/blob/master/src/gbt.erl" target="_blank">https://github.com/fogfish/feta/blob/master/src/gbt.erl</a><br>
><br>
> Therefore, nearest key lookup becomes a range lookup according criteria of your application.<br>
><br>
> nearest(Key, N, Tree) -><br>
>    iterator_to_list(<br>
>       gbt:range(key_to_range(Key, N), Tree)<br>
>      ,[]<br>
>    ).<br>
><br>
> iterator_to_list(Iter0, Acc) -><br>
>    case gbt:iterator(Iter) of<br>
>       none -><br>
>          lists:reverse(Acc);<br>
>       {Key, Val, Iter} -><br>
>          iterator_to_list(Iter, [{Key, Val}|Acc])<br>
>    end.<br>
><br>
> I’ve notice that 10M key might be large for Erlang data structures (e.g. I am trying to limit gb_trees to 1 - 2M in my apps) if you have many writes. Therefore, you might convert you lookup table to ets but same techniques is applicable to search nearest keys.<br>


><br>
> Best Regards,<br>
> Dmitry<br>
><br>
><br>
><br>
> On 27 May 2014, at 13:58, Joe Armstrong <<a href="mailto:erlang@gmail.com" target="_blank">erlang@gmail.com</a>> wrote:<br>
><br>
> ><br>
> > What's the best data structure to support a "nearest key" operation?<br>
> ><br>
> > I want a data structure that supports the following operations:<br>
> ><br>
> >      new() -> NewTree<br>
> ><br>
> >      insert(Key, Value, Tree) -> NewTree<br>
> ><br>
> >     delete(Key, Tree)  -> NewTree<br>
> ><br>
> >     nearest(Key, N, Tree)     -> [{Key1,Val1},{Key2,Val2} ...].<br>
> ><br>
> >     Keys are 20 byte binaries, values are 6 byte binaries<br>
> ><br>
> >     The maximum number of keys of Key-Value pairs is 10 million.<br>
> ><br>
> >    nearest(Key, N, Tree) returns the N nearest items to Key in the tree<br>
> ><br>
> >    "near" means that the keys are near to each other. Often the key I want will not<br>
> > be in the tree, so I want nearby keys. The nearness measure is just the<br>
> > "distance" between the two keys (ie the nearest N keys to the given key if the keys were to<br>
> > be sorted)<br>
> ><br>
> > Are there any Erlang libraries that do this?<br>
> ><br>
> > /Joe<br>
> > _______________________________________________<br>
> > erlang-questions mailing list<br>
> > <a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
> > <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
><br>
> _______________________________________________<br>
> erlang-questions mailing list<br>
> <a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
> <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</p>
</div>