Next: Adapting ILP Algorithms to Up: Query Packs Previous: Using Query Packs

## Computational Complexity

We estimate the speedup factor that can be achieved using query pack execution in two steps: first we consider one-level packs, then we extend the results towards deeper packs.

Lower and upper bounds on the speedup factor that can be achieved by executing a one-level pack instead of separate queries can be obtained as follows. For a pack containing queries , let be the time needed to compute the first answer substitution of if there are any, or to obtain failure otherwise. Let be the part of spent within and the part of spent in . Then and with representing the total time needed for executing all queries separately and the total time needed for executing the pack. Introducing , which roughly represents the ratio of the computational complexity in the shared part over that in the non-shared part, we have

 (1)

Now defining as the ratio of the maximal over the average , i.e.

we can rewrite Equation (1) as
 (2)

Since we know , which leads to the following bounds:
 (3)

Thus the speedup factor is bounded from above by the branching factor and by the ratio of computational complexity in the shared part over the computational complexity of the non-shared part; and a maximal speedup can be attained when (or, ), in other words when the for all queries are approximately equal.

For multi-level packs, we can estimate the efficiency gain as follows. Given a query , let be defined as above (the total time for finding 1 answer to or obtaining failure). Instead of and , we now define as the time spent on level of the pack when solving ; counting the root as level 0 and denoting the depth of the pack with we have . Further define as the time spent on level or deeper: with the depth of the pack. (Thus .). We will assume a constant branching factor in the pack. Finally, we define with . For simplicity, in the formulae we implicitly assume that always ranges from 1 to with the number of queries, unless explicitly specified otherwise. We then have

 (4)

where is the index of a child of the root and is the set of indexes of the queries belonging to that child. Now define and define as the smallest number such that with . Note . It then follows that
 (5)

which allows us to rewrite Equation (4) into
 (6)

where the equality holds if is equal in all . The reasoning can be continued up till the lowest level of the pack, yielding
 (7)

and finally
 (8)

with all between 1 and . We will further simplify the comparison with by assuming ; the can then be dropped and the inequality becomes an equality (because all maxima must be equal):
 (9)

Note that for we have

 (10)

It is clear, then, that the speedup will be governed by how the terms compare to the terms. (In the worst case, where , the latter become .) We therefore introduce as follows:
 (11)

The coefficients are always between 1 (if dominates) and (if strongly dominates); for all equal, is approximately .

Further, similar to in our previous analysis, define

 (12)

Some algebra then gives

 (13)

which needs to hold for all . We can interpret this as follows: for a certain level , roughly reflects the speedup gained by the fact that the part up till level needs to be executed only once; the factors reflect the speedup obtained within these parts because of the pack mechanism.

This inequality holds for all , hence we will find the best lower bound for the speedup factor by maximizing the right hand side. Note that increases and decreases monotonically with . It is clear that if at some point becomes much larger than 1, a speedup factor of roughly is obtained. On the other hand, if is smaller than 1, then the behaviour of is crucial. Now,

Our conclusion is similar to that for the one-level pack. If for some , , i.e., if in the upper part of the pack (up till level ) computations take place that are so expensive that they dominate all computations below level (even taking into account that the latter are performed times more often), then a speedup of can be expected. If , which will usually be the case for all except those near , the speedup can roughly be estimated as . The maximum of all these factors will determine the actual speedup.

Next: Adapting ILP Algorithms to Up: Query Packs Previous: Using Query Packs
Hendrik Blockeel 2002-02-26