Abstract: A conjecture of Gyàrfàs and Lehel asks if the sequence of trees T1
,T2 , . . . , Tn , where Ti , is a tree on i vertices, can be packed into Kn We show that if each Ti is restricted to a star or a path, then the sequence can be packed. We also give an explicit construction for a restricted case when the paths and stars alternate.Abstract: We present two algorithms for maintaining the exact counts of all itemsets over a stream of transactions. The count of each subset in a transaction is maintained by mapping it to substrings of the alphabet. This technique allows efficient time processing of the items in a single pass over the data stream. The two algorithms differ in their mapping schemes and data structures. The first algorithm performs prefix-based-scan of each transaction taken as a Boolean string, while the second algorithm improves on the first by exploiting the capability of suffix tree like structure for online enumeration of transaction suffixes. Correctness proofs and theoretic bounds on time and space complexity of these algorithms are presented. The algorithms are implemented and evaluated on several synthetic datasets. The results confirm that these algorithms are well suited to association rule mining over data streams for many practical situations.