Mining Time-Delayed Associations from Discrete Event Datasets

Abstract

We study the problem of finding time-delayed associations among types of events from an event dataset. We present a baseline algorithm for the problem. We analyse the algorithm and identify two methods for improving efficiency. First, we propose pruning strategies that can effectively reduce the search space for frequent time-delayed associations. Second, we propose the breadth-first* (BF*) candidate-generation order. We show that BF*, when coupled with the least-recently-used cache replacement strategy, provides a significant saving in I/O cost. Experiment results show that combining the two methods results in a very efficient algorithm for solving the time-delayed association problem.