<p dir="ltr"><br>
On May 27, 2014 8:32 AM, "Benoit Chesneau" <<a href="mailto:bchesneau@gmail.com">bchesneau@gmail.com</a>> wrote:<br>
><br>
> ---------- 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>
><br>
> On May 27, 2014 1:23 PM, "Dmitry Kolesnikov" <<a href="mailto:dmkolesnikov@gmail.com">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>
> ><br>
><br>
> here is an implementation of an rtree in erlang. not sure how much efficient it is but it works.<br>
><br>
> > 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">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">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>
> > ></p>
<p dir="ltr">Unsure how efficient you could make it in erlang, pretty efficient I think, it sounds like what you want is a Patricia Trie.  It by default gets the node you ask for or the nearest matching one with the longest prefix of whatever accuracy you wish, a minor change could just have it go down nearby existing nodes to get the nearest match instead of just the matching based on prefix, especially if you statically know the length of the binaries.</p>

<p dir="ltr"> _______________________________________________<br>
> > > erlang-questions mailing list<br>
> > > <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
> > > <a href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
> ><br>
> > _______________________________________________<br>
> > erlang-questions mailing list<br>
> > <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
> > <a href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
><br>
><br>
> _______________________________________________<br>
> erlang-questions mailing list<br>
> <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
> <a href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
><br>
</p>