TY - GEN

T1 - A quantitative study of two matrix clustering algorithms

AU - Slesarev, Alexander

AU - Galaktionov, Viacheslav

AU - Bobrov, Nikita

AU - Chernishev, George

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Database tuning

KW - Databases

KW - Experimentation

KW - Fragmentation

KW - Matrix clustering

KW - Physical design

KW - Vertical partitioning

UR - http://www.scopus.com/inward/record.url?scp=85067181126&partnerID=8YFLogxK

UR - http://ceur-ws.org/Vol-2372/SEIM_2019_paper_52.pdf

M3 - Conference contribution

AN - SCOPUS:85067181126

T3 - CEUR Workshop Proceedings

SP - 40

EP - 47

BT - 4th Conference on Software Engineering and Information Management, SEIM 2019

A2 - Trifonov, P.

A2 - Litvinov, Y.

PB - RWTH Aahen University

T2 - 4th Conference on Software Engineering and Information Management, SEIM 2019

Y2 - 13 April 2019

ER -