[erlang-questions] Ordered set with lower_bound

[Evans, Matthew]

I faced a similar problem where I needed to search a database with a random index value, and have it return the "closest match". I initially used an mnesia table and used a mnesia:select with a guard to perform a query of the type:

Match = #my_data{key = '$1', index = '$2'},
Guard = [{'>= ','$2',SomeValue}],
Result = ['$1','$2'],
mnesia:select(my_data,[{Match,Guard,[Result]}]),

I soon realized that as my data set grew in size that the above method would be very inefficient.

Instead I created a secondary index implemented using gb_trees. I would query this secondary index using a random value, and have the result of that value being an exact match to "index".

To do this I had to modify the gb_tree module, with a new function that lets it return the "closest match" (i.e. as it iterates over the tree it will return the previous, or next node if it fails to find a match). Maybe you could do the same in your project, but have it return an iterator instead?

Matt

-----Original Message-----
From: erlang-questions@REDACTED [mailto:erlang-questions@REDACTED] On Behalf Of Max Lapshin
Sent: Monday, October 12, 2009 6:27 AM
To: Colm Dougan
Cc: erlang-questions
Subject: Re: [erlang-questions] Ordered set with lower_bound

> If by "frame number N" you mean "the Nth object in the ordered set"
> then you can use ets:slot for this
>
> Colm

No,no, I was not too clear: I store milliseconds as id of frame and
need something like following expression:

seek(Time) ->
  "SELECT id FROM frames WHERE is_keyframe = 't' AND timestamp <= Time
ORDER BY id DESC limit 1"

Something like this. Binary tree will be ideal.

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org