Generality and Computational Cost

GENERALITY AND COMPUTATIONAL COST

Azriel Rosenfeld Computer Science Center University of Maryland College Park, Maryland 20742

U.S.A.

The purpose of this note is pedagogi­ cal. It discusses how one can reduce the computational cost of applying a set of operators (or predicates) by breaking them up into combinations of commonly occurring, simpler ones. This can be thought of as a process of generalization, in the sense that the common, simple oper­ ators are more "general" than the original, more complex ones. We are thus suggesting that even when one has a priori knowledge of a specialized nature (i.e., that the complex operators are applic­ able), it may still be desirable to use generalized operators in order to reduce computational cost.

To illustrate this idea, suppose that we want to apply a set of predicates P 1 , ... ,Pn to an input I, and suppose that the cost of applying predicate Pi is (pro­ portional to) the cardinality lsil of its set of support si ~ I. Thus the total cost of applying the P's is

n L IS . I· For example, applying P; might i=l ~ ·

involve a template-matching process, where Pi is true iff. a perfect match to the template is found in I. Here I could be an image, or a string (where the "template" is the right-hand side of a rule in a grammar), or a graph (where the "template" is a subgraph). In what follows, we will use the image/template metaphor.

Suppose now that there exists a set of subtemplates Ql, .·. ,Qm such that, for 1 ~ i ~ n, P. is a concatenation of n. of ~ ~ the Qj's. The cost of applying the Qj's

to I is L~ 1 1T . 1, where T. is Q . 's set of J= J J J

support. If we store the match positions in a new array I', then to test for Pi' we need only apply a template of cardin­ ality ni to I' . Thus testing for all the Pi's costs L~=l ni, and the total cost of the two-step matching process is LIT ·I + In . · J ~

Under what circumstances is the two­ step cost less than the brute-force cost IISil of applying the Pi's directly? We

claim that this depends on the degree to which the Q's "generalize" the P's -­ i.e., on how few Q's are needed to con­ struct all the P's. For concreteness, suppose that all the Qj's have the same support size IT. I = r, and that each P. J ~ consists of the same number n. = s of ~ Qj's. Thus each Pi has support size

Is. I = rs, and the costs of the brute-~ force and two-step approaches are nrs and mr+ns, respectively. If there are few Q's, they must be used repeatedly, and we have m << ns (m=ns would mean that each Q is used only once) ; thus mr+ns will be much smaller than nrs. The fewer Q's we need, the greater a saving mr+ns is over nrs. Thus the more we can generalize the P's, the lower the computational cost.

This template example is certainly not a universal one. It would be desir­ able to extend this type of analysis to other situations. (On the advantages of hierarchical matching in the graph/sub­ graph case see Barrow et al. (1972) .) However, our example does illustrate the idea that it may be advantageous to use generalized rather than specialized knowledge (see Zucker et al. (1975)), be­ cause this can lead to savings in compu­

tational cost.