next up previous
Next: Conclusions Up: Results Previous: Finding Dependencies in Phoenix

Finding Dependencies in Synthetic Data

In addition to the Phoenix data, the local search algorithm was tested on finding dependencies in synthetic data. The synthetic data was used to probe a concern: Can local search find dependencies even when there is no relationship between similar patterns?

The synthetic data was produced by generating token streams with biases. For this test, the bias was three patterns that were selected in advance. For each pattern, the precursor would appear at each position in the event streams with a likelihood of .05; if the precursor was inserted, then the target event followed it with likelihood of .80. Twenty seven synthetic data sets were generated, which included three numbers of tokens (15, 25, 35), three stream lengths (100, 500 1000), and three pattern lengths (2, 3, 4). Local search found all the patterns of length 2 and 3 with 15 or 25 tokens and at least 500 events in the streams, but none of the patterns of length 4 with 15 or 35 tokens. In addition, few of the patterns were found when there were 35 tokens. These results suggest that local search can detect relative order dependencies even when the neighborhoods have less meaning. However, increasing numbers of tokens and length of precursor means that local search is less likely to effectively search the space.

adele howe
Wed Mar 6 09:01:10 MST 1996