The purpose of the search is to test models of co-occurrence and find those that seem to represent significant dependencies between events in time. Because of the computational problems of increasing the number and character of the potential models, the dependency detection algorithm also was modified to apply local instead of exhaustive search. In this case, local search refers to a process of starting with a randomly selected initial pattern (a precursor and target event combination) and applying operators to find the best pattern from that one; the search continues until no better pattern can be found through operator application. Multiple initial starts of local search are done to collect different dependencies and explore different parts of the search space.
Local search has several advantages over exhaustive search for this application. First, we can control how much time is devoted to search through the operators applied and the number of trials. Second, we can be assured of getting the strongest dependencies; local search prunes the number of dependencies to be considered and usually prunes spurious dependencies based on few data.
The algorithm incorporates local search as follows:
New patterns are generated by applying a local search operator to the current best. Several local search operators were considered that permute the pattern by reordering and replacing pattern elements, but the best operator, in terms of efficiency and efficacy, is 1-OPT. 1-OPT optimizes one element in the pattern at a time. Progressing through the pattern positions in order, this operator considers all available elements as replacements; the operator replaces the element originally in the position with the best element for that position by testing the possibilities.
The algorithm continues to apply 1-OPT to subsequent best patterns until the resulting G value cannot be improved. The G values are obtained by constructing contingency tables and applying the G test as was described in the last subsection. The output is a list of the patterns returned in each of the T trials.