good points. for that type of case, I would agree. probably a good solution
is to use hashmap as default and use tree for ranges. best of both worlds
peter
On 12/18/06, Edson Tirelli <[EMAIL PROTECTED]> wrote:
Mark,
My feeling is that once someone is using an "ordering" constraint (>,
>=, <, <=), it means the attribute will have several possible values
(not a discrete small set of possible values). So, the issue is not
really the overhead of a Tree x Hashmap, but if the overhead of a tree
pays off the overhead of not using indexing for cases like that. My
feeling is that it does pays off and is worth at least a try.
I'm saying this because what I think you are refering to when you say
a hashmap+training-data approach (or hints as suggested by Michael) will
not address the general case.
I mean, when you have a rule like:
when
A( $var : attr )
B( attr2 > $var )
then
Using a hashmap will lead to a buckets count explosion that may cause
the hashmap to perform worse than the tree. Also, realize that in the
above case, a naive approach will cause a single B fact to be added to
multiple buckets, since it may match more than one A with different
"attr" values.
So, thats why I think a tree is better for the general case of
"ordering" constraints. Specific cases may be handled in a different way.
I know htrees only by name. Any specific feature you think may be
useful for us?
[]s
Edson
Mark Proctor wrote:
> I wonder if the overhead of a btree, btw have you seen htrees,
> compared to hashmap is worth while, I expect it is as join ordering
> can make a big difference.
>
> Mark
>
> Edson Tirelli wrote:
>
>> Mark,
>>
>> The approach I was looking into that time was not feasible because
>> we used to keep order of asserted fact/tuples on a node basis. With
>> the core changes you made in 3.1, we can implement range ordering by
>> replacing the current hashmap index for a tree index. No need for
>> training data, in my understanding.
>> Maybe we will need a composed index approach to work some cases,
>> but the general solution idea is simple.
>>
>> []s
>> Edson
>>
>> Mark Proctor wrote:
>>
>>> Actually I was just thinking about some stuff Edson has done.
>>> With solvers we know the available data and ranges, right? We can
>>> use this to order indexes, I know this was something Edson looked
>>> into - but without training data, we couldn't make it worth
>>> while - same for custom indexing. So we can start to incorporate
>>> those to get faster joins for known data sets.
>>>
>>> Mark
>>> Geoffrey De Smet wrote:
>>>
>>>> The more I learn from JCHS (or prolog for that matter),
>>>> the more I am starting to think that this is a different way of
>>>> solving.
>>>>
>>>> 1) JCHS/prolog looks like (or is) declarative solving.
>>>>
>>>> 2) Taseree is actually more hybrid, the general idea behind it is:
>>>> - Drools (declarative programming) is very easy for evaluation
>>>> but very difficult for solving.
>>>> - Local/tabu search (procedural programming) is easy for solving
>>>> but difficult for evaluation.
>>>>
>>>>
>>>> Both have it's disadvantages and advantages, for example:
>>>> Local search is generally faster but doesn't recognize the optimal
>>>> solution.
>>>>
>>>> To me it seems they are both interesting to implement,
>>>> there must be some common ground too.
>>>> We should hold a conference call about it this weekend?
>>>>
>>>> It would be a good idea to compare JCHS and Taseree on a couple of
>>>> problems, like the tt problem:
>>>> http://mat.gsia.cmu.edu/TOURN/
>>>>
>>>
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe from this list please visit:
>>>
>>> http://xircles.codehaus.org/manage_email
>>>
>>>
>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe from this list please visit:
>
> http://xircles.codehaus.org/manage_email
>
>
--
Edson Tirelli
Software Engineer - JBoss Rules Core Developer
Office: +55 11 3124-6000
Mobile: +55 11 9218-4151
JBoss, a division of Red Hat @ www.jboss.com
---------------------------------------------------------------------
To unsubscribe from this list please visit:
http://xircles.codehaus.org/manage_email
