Efficient classification across multiple database relations: A crossMine approach

Xiaoxin Yin, Jiawei Han, J. Yang, Gabrielle Dawn Allen

Research output: Contribution to journalArticlepeer-review


Relational databases are the most popular repository for structured data, and is thus one of the richest sources of knowledge in the world. In a relational database, multiple relations are linked together via entity-relationship links. Multirelational classification is the procedure of building a classifier based on information stored in multiple relations and making predictions with it. Existing approaches of Inductive Logic Programming (recently, also known as Relational Mining) have proven effective with high accuracy in multirelational classification. Unfortunately, most of them suffer from scalability problems with regard to the number of relations in databases. In this paper, we propose a new approach, called CrossMine, which includes a set of novel and powerful methods for multirelational classification, including 1) tuple ID propagation, an efficient and flexible method for virtually joining relations, which enables convenient search among different relations, 2) new definitions for predicates and decision-tree nodes, which involve aggregated information to provide essential statistics for classification, and 3) a selective sampling method for improving scalability with regard to the number of tuples. Based on these techniques, we propose two scalable and accurate methods for multi relational classification: CrossMine-Rule, a rule-based method and CrossMine-Tree, a decision-tree-based method. Our comprehensive experiments on both real and synthetic data sets demonstrate the high scalability and accuracy of the CrossMine approach.

Original languageEnglish (US)
Pages (from-to)770-783
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
StatePublished - Jun 1 2006


  • Classification
  • Data mining
  • Relational databases

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Efficient classification across multiple database relations: A crossMine approach'. Together they form a unique fingerprint.

Cite this