PQR sort: using PQR trees for binary matrix reorganization
Celmar Guimarães da Silva, Marivaldo Felipe de Melo, Felipi de Paula e Silva, João Meidânis · Journal of the Brazilian Computer Society · 2014
Abstract Background Reorganization of rows and columns of a matrix does not modify data but may ease or impair visual analysis of data similarities in this structure, according to Gestalt spatial proximity laws. However, there are a factorial number of permutations of rows and columns. Matrix reordering algorithms, such as 2D sort and Sugiyama-based reordering, permute matrix rows and columns in order to highlight hidden patterns. Methods We present PQR sort, a matrix reordering algorithm based on a recent data structure called PQR tree, and compare it with the previous ones in terms of time complexity and quality of reordering, according to predefined evaluation criteria. Results We found that PQR sort is an interesting method for minimizing minimal span loss functions based on Jaccard or simple matching coefficients, specially for a given pattern called Rectnoise with a noise ratio of 0.01 or 0.02 and a matrix size of 100 × 100 or 1,000 × 1,000. Conclusion We concluded that “PQR sort” is a valid alternative method for matrix reordering, which may also be extended for other visual structures.