<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 27, 2014 at 2:39 PM, Kostis Sagonas <span dir="ltr"><<a href="mailto:kostis@cs.ntua.gr" target="_blank">kostis@cs.ntua.gr</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On 05/27/2014 12:58 PM, Joe Armstrong wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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<br>
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<br>
if the keys were to<br>
be sorted)<br>
<br>
Are there any Erlang libraries that do this?<br>
</blockquote>
<br></div></div>
Joe,<br>
<br>
You have not really told us the most interesting aspect of your requirements. (Although one would be tempted to make an educated guess knowing you.)<br></blockquote><div><br></div><div>Now why would anybody want to put 20 byte binaries in a hash table and find the K nearest hits :-)</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Do you want your data structure to be concurrent or not?<br></blockquote><div><br></div><div>Sequential access is fine for now</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<br>
If you want a concurrent such data structure, I am afraid you need to do something (much) more complicated than the code you posted a while ago...<br>
<br>
<br>
Kostis<br>
<br>
<br>
<shameless_plug><br>
  Incidentally, we have done some very recent work on measuring the scalability (or lack thereof) of concurrent ETS tables of type ordered_set and propose to base the implementation on a different, much more scalable data structure which dynamically adapts to contention.  To those interested, we can send a paper privately.<br>
</blockquote><div><br></div><div>Yes please :-)</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</shameless_plug><div class="HOEnZb"><div class="h5"><br>
______________________________<u></u>_________________<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/<u></u>listinfo/erlang-questions</a><br>
</div></div></blockquote></div><br></div></div>