I/O Scalable bregman co-clustering

Kuo Wei Hsu, Arindam Banerjee, Jaideep Srivastava

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Consider an MxN matrix, where the (i,j)th entry represents the affinity between the i_th entity of the first type and the j_th entity of the second type. Co-clustering is an approach to simultaneously cluster both types of entities, using the affinities as the information guiding the clustering. Co-clustering has been found to achieve clustering and dimensionality reduction at the same time, and therefore it is finding application in various problems. Bregman co-clustering algorithm, which has been recently proposed, converts the co-clustering task to the search for an optimal approximation matrix. It is much more scalable but memory-based implementations have a severe computational bottleneck. In this paper we show that a significant fraction of computations performed by the Bregman co-clustering algorithm naturally map to those performed by an on-line analytical processing (OLAP) engine, making the latter a well suited data management engine for the algorithm. Based on this observation, we have developed a version of Bregman co-clustering algorithm that works on top of OLAP. Our experiments show that this version is much more scalable, achieving an order of magnitude performance improvement over the memory-based implementation. We believe this unlocks the power of this novel technique for application to much larger datasets.

Original languageEnglish (US)
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 12th Pacific-Asia Conference, PAKDD 2008, Proceedings
Number of pages8
StatePublished - 2008
Externally publishedYes
Event12th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2008 - Osaka, Japan
Duration: May 20 2008May 23 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5012 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2008


  • Bregman co-clustering
  • Data cube
  • OLAP
  • SQL

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'I/O Scalable bregman co-clustering'. Together they form a unique fingerprint.

Cite this