ABSTRACT
Department of Computing and Information Systems, The University of Melbourne
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Background on Binary Decision Diagrams and ZBDDs . . . . . . . . . 32 4.3 Mining Emerging Patterns Using ZBDDs . . . . . . . . . . . . . . . . . . . . . . . 35 4.4 Discussion and Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
In this chapter, we study the computation of emerging patterns using a sophisticated data structure, known as a zero-suppressed binary decision diagram (ZBDD). We will see how the ZBDD data structure can be used to enumerate emerging patterns. The advantage of ZBDDs lies in their ability to store input data or output patterns in a highly compressed form. This is particularly advantageous for high dimensional datasets, such as gene expression data, where the number of features is very large and the number of emerging patterns that are output can be huge. The ZBDD data structure provides an interesting alternative to popular structures such as the frequent pattern tree [180], whose variants have previously been proposed as an effective emerging pattern mining method [33, 141], and which were reviewed in Chapter 3. The presentation is based on our work in [283].
