Author name cluster

Limsoon Wong

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

AAAI Conference 2006 Conference Paper

Minimum Description Length Principle: Generators Are Preferable to Closed Patterns

Jinyan Li
Limsoon Wong

The generators and the unique closed pattern of an equivalence class of itemsets share a common set of transactions. The generators are the minimal ones among the equivalent itemsets, while the closed pattern is the maximum one. As a generator is usually smaller than the closed pattern in cardinality, by the Minimum Description Length Principle, the generator is preferable to the closed pattern in inductive inference and classification. To efficiently discover frequent generators from a large dataset, we develop a depth-first algorithm called Gr-growth. The idea is novel in contrast to traditional breadth-first bottom-up generator-mining algorithms. Our extensive performance study shows that Gr-growth is significantly faster (an order or even two orders of magnitudes when the support thresholds are low) than the existing generator mining algorithms. It can be also faster than the state-of-the-art frequent closed itemset mining algorithms such as FPclose and CLOSET+.

PDF Details

IS Journal 2005 Journal Article

Guest Editors' Introduction: Data Mining in Bioinformatics

Jinyan Li
Limsoon Wong
Qiang Yang

This special issue aims to bridge the gap between bioinformatics and data mining by presenting research integrating the two. Data mining has the potential to provide the necessary tools for better understanding of gene expression, drug design, and other emerging problems in genomics and proteomics.

Details DOI

I&C Journal 2003 Journal Article

Incremental recomputation in local languages

Guozhu Dong
Leonid Libkin
Limsoon Wong

We study the problem of maintaining recursively defined views, such as the transitive closure of a relation, in traditional relational languages that do not have recursion mechanisms. The main results of this paper are negative ones: we show that a certain property of query languages implies impossibility of such incremental maintenance. The property we use is locality of queries, which is known to hold for relational calculus and various extensions, including those with grouping and aggregate constructs (essentially, plain SQL).

Details DOI

TCS Journal 2002 Journal Article

Lower bounds for invariant queries in logics with counting

Leonid Libkin
Limsoon Wong

We study the expressive power of counting logics in the presence of auxiliary relations such as orders and preorders. The simplest such logic is the first-order logic with counting. This logic captures the complexity class TC 0 over ordered structures. We also consider first-order logic with arbitrary unary quantifiers and with infinitary extensions. We start by giving a simple direct proof that first-order logic with counting, in the presence of pre-orders that are almost-everywhere linear orders, cannot express the transitive closure of a binary relation. The proof is based on locality of formulae. We then show that the technique cannot be extended to linear orders. We further show that this result does not say anything about the power of invariant queries in first-order logic with counting vs. the class TC 0, in the presence of these preorders. In the second part of the paper, we prove a separation result showing that, for all the counting logics above, a linear order is more powerful than a preorder that is a linear order almost everywhere. In fact, we prove that the expressive power of invariant queries in the presence of such preorders can be characterized by a property normally associated with first-order definability over unordered structures. We do this by using locality techniques from finite-model theory. However, as some standard notions of locality fail in this setting, we have to modify them to prove the main result.

Details DOI

TCS Journal 2000 Journal Article

Local properties of query languages

Guozhu Dong
Leonid Libkin
Limsoon Wong

In this paper we study the expressiveness of local queries. By locality we mean — informally — that in order to check if a tuple belongs to the result of a query, one only has to look at a certain predetermined portion of the input. Examples include all relational calculus queries. We start by proving a general result describing outputs of local queries. This result leads to many easy inexpressibility proofs for local queries. We then consider a closely related property, namely, the bounded degree property. It describes the outputs of local queries on structures that locally look “simple. ” Every query that is local is shown to have the bounded degree property. Since every relational calculus (first-order) query is local, the general results proved for local queries can be viewed as “off-the-shelf” strategies for proving inexpressibility results, which are often easier to apply than Ehrenfeucht–Fraı̈ssé games. We also show that some generalizations of the bounded degree property that were conjectured to hold, fail for relational calculus. We then prove that the language obtained from relational calculus by adding grouping and aggregates, which is essentially plain SQL, has the bounded degree property, thus answering a question that has been open for several years. Consequently, first-order queries with Härtig or Rescher quantifiers also have the bounded degree property. Finally, we apply our results to incremental maintenance of views, and show that SQL and relational calculus are incapable of maintaining the transitive closure view even in the presence of auxiliary relations of moderate degree.

Details DOI