Databases Reference
In-Depth Information
Input
:
static traces
Output
:
partial order clusters
f
Identify all producers;
foreach
producer
do
Identify consumers;
Construct PC-chain;
Output PC-chain as a scenario;
end
end
Construct isolated partial orders from scenarios;
Collect the head APIs from isolated partial orders;
Construct partial order among head APIs to form partial order clusters;
return
partial order clusters
FIGURE 5.8: The PC-Chain algorithm for scenario extraction.
To be ecient and scalable, FRECPO prunes the futile branches and nar-
rows the search space as much as possible. Basically, three types of techniques
are used. First, FRECPO prunes infrequent items, edges, and partial orders.
If a partial order R in the set enumeration tree is infrequent, then the partial
orders in the subtree rooted at R, which are stronger than R, cannot be fre-
quent. The subtree can be pruned. Second, FRECPO prunes forbidden edges.
Not every edge can appear in the transitive reduction of a partial order. For
example, if every string containing ac also contains ab and bc, then edge ac
should not appear in the transitive reduction of any frequent closed partial
order. Edge ac is called a forbidden edge. Removing the forbidden edges can
also reduce the search space. Finally, FRECPO extracts transitive reductions
of frequent partial orders directly and does not need to compute the transitive
reductions.
5.2.2.7
Complexity
PDMC constructs PDAPfrom the program Control Flow Graph (a di-
rected graph G = (N;E)) where each node represents a program point and
each edge represents a valid program statement. PDMC takes O(E) time to
construct the PDAPfrom the CFG G, takes O(EjQj) (Q is the number of
states in the FSA) for computing P, the product of FSAFand PDAP, takes
O(jQj
2
E) for deciding if the PDA P is empty and O(jQj
2
)lgjQjElgN
for backtracking. The derivations are shown by Chen [18].
It has been shown that the problem of counting the complete set of frequent
closed partial order is #P-complete. In other words, FRECPO is of exponen-
tial complexity with respect to jAj. However, FRECPO is pseudo-linear. That
is, the runtime is linear with respect to the number of frequent closed partial
orders in the data set. In practice, the number of significant frequent closed
partial orders of APIs for a program is often small. Thus, it is highly feasible
and effective to use FRECPO in our application context.
Search WWH ::
Custom Search