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

[Joe Armstrong]

On Tue, May 27, 2014 at 2:39 PM, Kostis Sagonas <kostis@REDACTED> wrote:

> On 05/27/2014 12:58 PM, Joe Armstrong 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,
>
> 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.)
>

Now why would anybody want to put 20 byte binaries in a hash table and find
the K nearest hits :-)


>
> Do you want your data structure to be concurrent or not?
>

Sequential access is fine for now


>
> 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...
>
>
> Kostis
>
>
> <shameless_plug>
>   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.
>

Yes please :-)


> </shameless_plug>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140527/02868768/attachment.htm>