« Return to Thread: quoestion on index/1
Re: quoestion on index/1
by Jan Wielemaker
::
Rate this Message:
Lukas,
On Wednesday 07 May 2008 10:59, Lukas Degener wrote:
> I was reading through the online help entry for index/1.
> There are two things that I am not sure I understand:
>
> "Indexing as specified by this predicate uses a quick but linear scan."
> Does this mean that the process of creating an index uses a linear scan,
> or that index lookups are linear?
Both :-)
> Then further down, there is this subclass example.
> It is recommended there that if one wants to use the predicate
> sub_type/2 for both finding subtypes and supertypes, one should resort
> to index/1. But on the other hand, it is said that lookups will still be
> linear - which sounds dramatically worse than those of the hash index
> structure that is used by default.
>
> What is this index/1 thing good for, if the lookup is still linear? The
> manual states that "this type of indexing makes selecting clauses much
> faster". Could you give more details on what this indexing actually does?
Each clause has a mask and a key. For the actually goal it also computes
a mask and a key. Now, finding a candidate clause walks the linked list
of clauses and does a simple and-and-compare to decide whether the
clause is a candidate. It is guaranteed that if that simple check fails,
unification will fail too, so it only starts running the clause if this
check succeeds. The scan is quite fast, but linear.
It isn't good for many things today. It is still quite nice for tables
you need to use with multiple patterns that have no more than 10s of
clauses. The system badly needs proper just-in-time indexing of multiple
arguments as well as deeper indexing.
> And finally, at least for dynamic predicates with a lot of clauses,
> wouldn't it make more sense to use two predicates (one for each
> "direction")?
>
> Something like this:
> :- dynamic sub_type_X/2, sub_type_XX/2.
>
> sub_type(Sub,Super):-
> ( nonvar(Super)
> -> sub_type_X(Sub,Super)
> ; sub_type_XX(Super,Sub)
> ).
Except that you wrote it exactly the wrong way around :-), this is often
the best option in the current system. Some applications may also
consider using the RDF store, which provides persistency as well as
elaborate indexing on triples.
Cheers --- Jan
------------
For further info, please visit http://www.swi-prolog.org/
To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...
On Wednesday 07 May 2008 10:59, Lukas Degener wrote:
> I was reading through the online help entry for index/1.
> There are two things that I am not sure I understand:
>
> "Indexing as specified by this predicate uses a quick but linear scan."
> Does this mean that the process of creating an index uses a linear scan,
> or that index lookups are linear?
Both :-)
> Then further down, there is this subclass example.
> It is recommended there that if one wants to use the predicate
> sub_type/2 for both finding subtypes and supertypes, one should resort
> to index/1. But on the other hand, it is said that lookups will still be
> linear - which sounds dramatically worse than those of the hash index
> structure that is used by default.
>
> What is this index/1 thing good for, if the lookup is still linear? The
> manual states that "this type of indexing makes selecting clauses much
> faster". Could you give more details on what this indexing actually does?
Each clause has a mask and a key. For the actually goal it also computes
a mask and a key. Now, finding a candidate clause walks the linked list
of clauses and does a simple and-and-compare to decide whether the
clause is a candidate. It is guaranteed that if that simple check fails,
unification will fail too, so it only starts running the clause if this
check succeeds. The scan is quite fast, but linear.
It isn't good for many things today. It is still quite nice for tables
you need to use with multiple patterns that have no more than 10s of
clauses. The system badly needs proper just-in-time indexing of multiple
arguments as well as deeper indexing.
> And finally, at least for dynamic predicates with a lot of clauses,
> wouldn't it make more sense to use two predicates (one for each
> "direction")?
>
> Something like this:
> :- dynamic sub_type_X/2, sub_type_XX/2.
>
> sub_type(Sub,Super):-
> ( nonvar(Super)
> -> sub_type_X(Sub,Super)
> ; sub_type_XX(Super,Sub)
> ).
Except that you wrote it exactly the wrong way around :-), this is often
the best option in the current system. Some applications may also
consider using the RDF store, which provides persistency as well as
elaborate indexing on triples.
Cheers --- Jan
------------
For further info, please visit http://www.swi-prolog.org/
To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...
« Return to Thread: quoestion on index/1
| Free Forum Powered by Nabble | Forum Help |