Matrix clustering is a technique which permutes rows and columns of a matrix to form densely packed regions. It originated in the 70's and initially was used for various object grouping problems, such as machine-component grouping. The database community noticed these algorithms and successfully applied them to the vertical partitioning problem. Recently, there has been a resurgence of interest in these algorithms. Nowadays, they are being considered for dynamic (on-line) vertical partitioning and tuning of multistores. In our previous papers we have described our project aimed at studing the applicability of recent matrix clustering algorithms for the vertical partitioning problem. We have presented our evaluation approach and reported results concerning several of these algorithms. Our idea was to evaluate them directly using the PostgreSQL database. Previous studies have found that these algorithms can be of use if they employ the attribute replication strategy. In this paper, we continue our investigation and consider a novel algorithm of this class. Its distinctive feature is that it performs attribute replication during the branch and bound search. We compare it with the best one of the earlier algorithms using both real and synthetic workloads. Our experiments have demonstrated that the novel algorithm produces slightly worse configurations (about 10%), but its run times are significantly better and are almost independent of the cohesion parameter.

Original languageEnglish
Title of host publication4th Conference on Software Engineering and Information Management, SEIM 2019
EditorsP. Trifonov, Y. Litvinov
PublisherRWTH Aahen University
Publication statusPublished - 1 Jan 2019
Event4th Conference on Software Engineering and Information Management, SEIM 2019 - Saint Petersburg
Duration: 13 Apr 2019 → …

Publication series

NameCEUR Workshop Proceedings
PublisherRWTH Aahen University
ISSN (Print)1613-0073


Conference4th Conference on Software Engineering and Information Management, SEIM 2019
CountryRussian Federation
CitySaint Petersburg
Period13/04/19 → …

Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A quantitative study of two matrix clustering algorithms'. Together they form a unique fingerprint.

Cite this