Noname manuscript No. (will be inserted by the editor) Mining Frequent Itemsets Over Arbitrary Time Intervals in Data Streams

Abstract Mining frequent itemsets over a stream of transactions presents di cult new challenges over traditional mining in static transaction databases. Stream transactions can only be looked at once and streams have amuch richer frequent itemset structure due to their inherent temporal nature. We examine a novel data structure, an FP-stream, for maintaining information about itemset frequency histories. At any time, requests for itemsets frequent over user-de ned time intervals can be serviced by scanning the maintained FP-stream producing an approximate answer with error guaranteed to be no worse than a user-speci ed frequency and temporal threshold. We develop an algorithm for constructing and updating an FP-stream structure and present experiments illustrating the time and space required for maintenance