TY - JOUR
T1 - Pattern Space Maintenance for Data Updates and Interactive Mining
JF - Computational Intelligence
Y1 - 2010
A1 - Mengling Feng
A1 - Guozhu Dong
A1 - Jinyan Li
A1 - Yap-Peng Tan
A1 - Limsoon Wong
KW - Data mining algorithms
KW - data update and interactive mining
KW - frequent pattern
KW - incremental maintenance
AB - This paper addresses the incremental and decremental maintenance of the frequent pattern space. We conduct an in-depth investigation on how the frequent pattern space evolves under both incremental and decremental updates. Based on the evolution analysis, a new data structure, Generator-Enumeration Tree (GE-tree), is developed to facilitate the maintenance of the frequent pattern space. With the concept of GE-tree, we propose two novel algorithms, Pattern Space Maintainer+ (PSM+) and Pattern Space Maintainer- (PSM-), for the incremental and decremental maintenance of frequent patterns. Experimental results demonstrate that the proposed algorithms, on average, outperform the representative state-of-the-art methods by an order of magnitude.
VL - 26
CP - 3
ER -
TY - CHAP
T1 - Maintenance of Frequent Patterns: A Survey
Y1 - 2009
A1 - Jinyan Li
A1 - Limsoon Wong
A1 - Mengling Feng
A1 - Guozhu Dong
AB - This chapter surveys the maintenance of frequent patterns in transaction datasets. It is written to be accessible to researchers familiar with the field of frequent pattern mining. The frequent pattern main-tenance problem is summarized with a study on how the space of frequent patterns evolves in response to data updates. This chapter focuses on incremental and decremental maintenance. Four major types of maintenance algorithms are studied: Apriori-based, partition-based, prefix-tree-based, and concise-representation-based algorithms. The authors study the advantages and limitations of these algorithms from both the theoretical and experimental perspectives. Possible solutions to certain limitations are also proposed. In addition, some potential research opportunities and emerging trends in frequent pat-tern maintenance are also discussed.
ER -
TY - CHAP
T1 - Mining Conditional Contrast Patterns
Y1 - 2009
A1 - Guozhu Dong
A1 - Guimei Liu
A1 - Limsoon Wong
A1 - Jinyan Li
AB - This chapter considers the problem of 'conditional contrast pattern mining.' It is related to contrast mining, where one considers the mining of patterns/models that contrast two or more datasets, classes, conditions, time periods, and so forth. Roughly speaking, conditional contrasts capture situations where a small change in patterns is associated with a big change in the matching data of the patterns. More precisely, a conditional contrast is a triple (B, F_{1}, F_{2}) of three patterns; B is the condition/context pattern of the conditional contrast, and F_{1} and F_{2} are the contrasting factors of the conditional contrast. Such a conditional contrast is of interest if the difference between F_{1} and F_{2} as itemsets is relatively small, and the difference between the corresponding matching dataset of B∪F_{1} and that of B∪F_{2 is relatively large. It offers insights on 'discriminating' patterns for a given condition B. Conditional contrast mining is related to frequent pattern mining and analysis in general, and to the mining and analysis of closed pattern and minimal generators in particular. It can also be viewed as a new direction for the analysis (and mining) of frequent patterns. After formalizing the concepts of conditional contrast, the chapter will provide some theoretical results on conditional contrast mining. These results (i) relate conditional contrasts with closed patterns and their minimal generators, (ii) provide a concise representation for conditional contrasts, and (iii) establish a so-called dominance-beam property. An efficient algorithm will be proposed based on these results, and experiment results will be reported. Related works will also be discussed.
ER -
TY - CONF
T1 - Evolution and Maintenance of Frequent Pattern Space When Transactions Are Removed. Proceedings of PAKDD
T2 - Evolution and Maintenance of Frequent Pattern Space When Transactions Are Removed. Proceedings of PAKDD
Y1 - 2007
A1 - Jinyan Li
A1 - Limsoon Wong
A1 - Yap-Peng Tan
A1 - Mengling Feng
A1 - Guozhu Dong
JA - Evolution and Maintenance of Frequent Pattern Space When Transactions Are Removed. Proceedings of PAKDD
ER -
TY - CONF
T1 - Minimum Description Length (MDL) Principle: Generators Are Preferable to Closed Patterns
T2 - Minimum Description Length (MDL) Principle: Generators Are Preferable to Closed Patterns
Y1 - 2006
A1 - Limsoon Wong
A1 - Jinyan Li
A1 - Guozhu Dong
A1 - H. Li
A1 - Jian Pei
JA - Minimum Description Length (MDL) Principle: Generators Are Preferable to Closed Patterns
ER -
TY - JOUR
T1 - DeEPs: A New Instance-based Discovery and Classification System
Y1 - 2004
A1 - Limsoon Wong
A1 - Kotagiri Ramamohanarao
A1 - Jinyan Li
A1 - Guozhu Dong
ER -
TY - JOUR
T1 - Incremental Recomputation in Local Languages
Y1 - 2003
A1 - Leonid Libkin
A1 - Limsoon Wong
A1 - Guozhu Dong
ER -
TY - JOUR
T1 - Local Properties of Query Languages
Y1 - 2000
A1 - Guozhu Dong
A1 - Limsoon Wong
A1 - Leonid Libkin
ER -
TY - JOUR
T1 - CAEP: Classification by Aggregating Emerging Patterns
Y1 - 1999
A1 - Limsoon Wong
A1 - Guozhu Dong
A1 - Xiuzhen Zhang
A1 - Jinyan Li
ER -
TY - JOUR
T1 - Maintaining Transitive Closure of Graphs in SQL
Y1 - 1999
A1 - Leonid Libkin
A1 - Jianwen Su
A1 - Guozhu Dong
A1 - Limsoon Wong
ER -
TY - JOUR
T1 - Using CAEP to Predict Translation Initiation Sites from Genomic DNA Sequences
Y1 - 1999
A1 - Xiuzhen Zhang
A1 - Limsoon Wong
A1 - Guozhu Dong
ER -
TY - JOUR
T1 - Relational expressive power of constraint query languages
Y1 - 1998
A1 - Michael Benedikt
A1 - Leonid Libkin
A1 - Guozhu Dong
A1 - Limsoon Wong
ER -
TY - JOUR
T1 - Local properties of query languages
Y1 - 1997
A1 - Limsoon Wong
A1 - Leonid Libkin
A1 - Guozhu Dong
ER -
TY - JOUR
T1 - Some Relationships between FOIES and Sigma 1 1 Arity Hierarchies
Y1 - 1997
A1 - Guozhu Dong
A1 - Limsoon Wong
ER -
TY - JOUR
T1 - Relational Expressive Power of Constraint Query Languages
JF - Journal of the ACM
Y1 - 1996
A1 - Michael Benedikt
A1 - Guozhu Dong
A1 - Leonid Libkin
A1 - Limsoon Wong
AB - The expressive power of first-order query languages with several classes of equality and inequality constraints is studied in this paper. We settle the conjecture that recursive queries such as parity test and transitive closure cannot be expressed in the relational calculus augmented with polynomial inequality constraints over the reals. Furthermore, noting that relational queries exhibit several forms of genericity, we establish a number of collapse results of the following form: The class of generic boolean queries expressible in the relational calculus augmented with a given class of constraints coincides with the class of queries expressible in the relational calculus (with or without an order relation). We prove such results for both the natural and active-domain semantics. As a consequence, the relational calculus augmented with polynomial inequalities expresses the same classes of generic boolean queries under both the natural and active-domain semantics. In the course of proving these results for the active-domain semantics, we establish Ramsey-type theorems saying that any query involving certain kinds of constraints coincides with a constraint free query on databases whose elements come from a certain innite subset of the domain. To prove the collapse results for the natural semantics, we make use of techniques from nonstandard analysis and from the model theory of ordered structures.
ER -
TY - CONF
T1 - On impossibility of decremental recomputation of recursive queries in relational calculus and SQ
Y1 - 1995
A1 - Guozhu Dong
A1 - Leonid Libkin
A1 - Limsoon Wong
PB - Fifth International Database Programming Languages Workshop
ER -
}