关键词: 数据起源, 世系追踪, 频繁模式, 剪枝, 数据挖掘

Abstract: Data provenance studies the processes of data generation, transformation and update. Based on properties and features of frequent patterns (FP), this paper proposes an FP+ tree to store sources of frequent patterns. Then, it gives the related theories and proofs for tracking provenances of frequent patterns, proposes three tracking methods for frequent patterns based on different lineage tracing mechanism, and deduces the correctness and theoretical cost of each method. While mining frequent patterns, the lineages of frequent patterns can be traced without extra cost. According to the structure of conditional FP+ tree and properties of frequent patterns, the paper also proposes α-pruning for efficiently projecting conditional FP+ tree and improving the efficiency of lineage tracing. Experimental results show that the FP+ tree based tracking provenance of frequent patterns can get sources of frequent patterns efficiently, and α-pruning for conditional FP+ tree is efficient.

Key words: data provenance, lineage tracing, frequent patterns, pruning, data mining