<div dir="ltr">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.<div>

<br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, May 27, 2014 at 2:10 PM, Joe Armstrong <span dir="ltr"><<a href="mailto:erlang@gmail.com" target="_blank">erlang@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><br><br><div class="gmail_quote"><div class="">On Tue, May 27, 2014 at 1:26 PM, Tony Rogvall <span dir="ltr"><<a href="mailto:tony@rogvall.se" target="_blank">tony@rogvall.se</a>></span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">What about an ets ordered set table?</div></blockquote><div><br></div></div><div>How? - the problem is the key I lookup are not in the table</div>


<div><br></div><div>Suppose I insert keys</div><div><br></div><div>    1, 46, 218, 345, 578, 6541, 14671, ....</div><div><br></div><div>And I lookup a key 400 - this is not in the list - I'd like ets:nearest(400, Tab) to return </div>


<div>the key 354 entry - but there is no ets:nearest ...</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>/Joe</div></font></span><div><div class="h5"><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


<div style="word-wrap:break-word"><div><br></div><div>/Tony</div><div><br><div><div><div><div>On 27 maj 2014, at 12:58, Joe Armstrong <<a href="mailto:erlang@gmail.com" target="_blank">erlang@gmail.com</a>> wrote:</div>


<br></div></div><blockquote type="cite"><div><div><div dir="ltr"><div><br></div>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<div>



<br></div><div>    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></div></div></div></div><div>
_______________________________________________<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>


</div></blockquote></div><br><div>
<span style="border-collapse:separate;color:rgb(0,0,0);font-family:Helvetica;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div>


<span style="color:rgb(51,51,51);font-family:Geneva,Arial,Helvetica,sans-serif;font-size:12px">"Installing applications can lead to corruption over time. </span><span style="color:rgb(51,51,51);font-family:Geneva,Arial,Helvetica,sans-serif;font-size:12px">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"</span></div>


<div><span style="color:rgb(51,51,51);font-family:Geneva,Arial,Helvetica,sans-serif;font-size:12px"><br></span></div></span><br>
</div>
<br></div></div></blockquote></div></div></div><br></div></div>
<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" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>J.
</div>