{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:49Z","timestamp":1750220509190,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,9]],"date-time":"2021-01-09T00:00:00Z","timestamp":1610150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007059","name":"Univerzita Palack\u00e9ho v Olomouci","doi-asserted-by":"crossref","award":["JG_2020_003,IGA_PrF_2020_019"],"award-info":[{"award-number":["JG_2020_003,IGA_PrF_2020_019"]}],"id":[{"id":"10.13039\/501100007059","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>We provide a detailed analysis and a first complete description of 8M\u2014an old but virtually unknown algorithm for Boolean matrix factorization. Even though the algorithm uses a rather limited insight into the factorization problem from today\u2019s perspective, we demonstrate that its performance is reasonably good compared to the currently available algorithms. Our analysis reveals that this is due to certain concepts employed by 8M that are not exploited by the current algorithms. We discuss the prospect of these concepts, utilize them to improve two well-known current factorization algorithms, and, furthermore, propose an improvement of 8M itself, which significantly enhances the performance of the original 8M. Our findings are illustrated by experimental evaluation.<\/jats:p>","DOI":"10.1145\/3428078","type":"journal-article","created":{"date-parts":[[2021,1,9]],"date-time":"2021-01-09T11:17:08Z","timestamp":1610191028000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The 8M Algorithm\u00a0from Today\u2019s Perspective"],"prefix":"10.1145","volume":"15","author":[{"given":"Radim","family":"Belohlavek","sequence":"first","affiliation":[{"name":"Palack\u00fd University Olomouc, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Trnecka","sequence":"additional","affiliation":[{"name":"Palack\u00fd University Olomouc, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Irvine, CA: University of California, School of Information and Computer Science.","author":"Bache K.","year":"2013","unstructured":"K. Bache and M. Lichman . 2013 . UCI Machine Learning Repository . Irvine, CA: University of California, School of Information and Computer Science. Retrieved from http:\/\/archive.ics.uci.edu\/ml. K. Bache and M. Lichman. 2013. UCI Machine Learning Repository. Irvine, CA: University of California, School of Information and Computer Science. Retrieved from http:\/\/archive.ics.uci.edu\/ml."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Workshop on Clustering High-Dimensional Data. 118--133","author":"Bartl E.","year":"2012","unstructured":"E. Bartl , R. Belohlavek , P. Osicka , and H. \u0158ezankov\u00e1 . 2012 . Dimensionality reduction in boolean data: Comparison of four BMF methods . In Proceedings of the International Workshop on Clustering High-Dimensional Data. 118--133 . E. Bartl, R. Belohlavek, P. Osicka, and H. \u0158ezankov\u00e1. 2012. Dimensionality reduction in boolean data: Comparison of four BMF methods. In Proceedings of the International Workshop on Clustering High-Dimensional Data. 118--133."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-014-9414-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.06.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.044"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.05.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"R. A. Brualdi and H. J. Ryser. 1991. Combinatorial Matrix Theory. Cambridge University Press.  R. A. Brualdi and H. J. Ryser. 1991. Combinatorial Matrix Theory. Cambridge University Press.","DOI":"10.1017\/CBO9781107325708"},{"key":"e_1_2_1_8_1","unstructured":"W. J. Dixon (ed.). 1992. BMDP Statistical Software Manual. University of California Press Berkeley CA.  W. J. Dixon (ed.). 1992. BMDP Statistical Software Manual. University of California Press Berkeley CA."},{"volume-title":"Proceedings of the 13th ACM Symposium on Access Control Models and Technologies. 1--10","author":"Ene A.","key":"e_1_2_1_9_1","unstructured":"A. Ene , W. Horne , N. Milosavljevic , P. Rao , R. Schreiber , and R. E. Tarjan . 2008. Fast exact and heuristic methods for role minimization problems . In Proceedings of the 13th ACM Symposium on Access Control Models and Technologies. 1--10 . A. Ene, W. Horne, N. Milosavljevic, P. Rao, R. Schreiber, and R. E. Tarjan. 2008. Fast exact and heuristic methods for role minimization problems. In Proceedings of the 13th ACM Symposium on Access Control Models and Technologies. 1--10."},{"key":"e_1_2_1_10_1","unstructured":"B. Ganter and R. Wille. 1991. Formal Concept Analysis: Mathematical Foundations. Springer Berlin.  B. Ganter and R. Wille. 1991. Formal Concept Analysis: Mathematical Foundations. Springer Berlin."},{"volume-title":"Proceedings of the 2004 International Conference on Discovery Science. 278--289","author":"Geerts F.","key":"e_1_2_1_11_1","unstructured":"F. Geerts , B. Goethals , and T. Mielik\u00e4inen . 2004. Tiling databases . In Proceedings of the 2004 International Conference on Discovery Science. 278--289 . F. Geerts, B. Goethals, and T. Mielik\u00e4inen. 2004. Tiling databases. In Proceedings of the 2004 International Conference on Discovery Science. 278--289."},{"volume-title":"Proceedings of the 2015 SIAM International Conference on Data Mining. 325--333","author":"Karaev S.","key":"e_1_2_1_12_1","unstructured":"S. Karaev , P. Miettinen , and J. Vreeken . 2015. Getting to know the unknown unknowns: Destructive-noise resistant Boolean matrix factorization . In Proceedings of the 2015 SIAM International Conference on Data Mining. 325--333 . S. Karaev, P. Miettinen, and J. Vreeken. 2015. Getting to know the unknown unknowns: Destructive-noise resistant Boolean matrix factorization. In Proceedings of the 2015 SIAM International Conference on Data Mining. 325--333."},{"volume-title":"Boolean Matrix Theory and Applications","author":"Kim K. H.","key":"e_1_2_1_13_1","unstructured":"K. H. Kim . 1982. Boolean Matrix Theory and Applications . M. Dekker , NY. K. H. Kim. 1982. Boolean Matrix Theory and Applications. M. Dekker, NY."},{"key":"e_1_2_1_14_1","first-page":"5","article-title":"2012. Constraint-aware role mining via extended Boolean matrix decomposition","volume":"9","author":"Lu H.","year":"2012","unstructured":"H. Lu , J. Vaidya , V. Atluri , and Y. Hong , 2012. Constraint-aware role mining via extended Boolean matrix decomposition . IEEE Transactions on Dependable and Secure Computing 9 , 5 ( 2012 ), 655--669. H. Lu, J. Vaidya, V. Atluri, and Y. Hong, 2012. Constraint-aware role mining via extended Boolean matrix decomposition. IEEE Transactions on Dependable and Secure Computing 9, 5 (2012), 655--669.","journal-title":"IEEE Transactions on Dependable and Secure Computing"},{"volume-title":"Proceedings of the 2010 SIAM International Conference on Data Mining. 165--176","author":"Lucchese C.","key":"e_1_2_1_15_1","unstructured":"C. Lucchese , S. Orlando , and R. Perego . 2010. Mining top-k patterns from binary datasets in presence of noise . In Proceedings of the 2010 SIAM International Conference on Data Mining. 165--176 . C. Lucchese, S. Orlando, and R. Perego. 2010. Mining top-k patterns from binary datasets in presence of noise. In Proceedings of the 2010 SIAM International Conference on Data Mining. 165--176."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.181"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.93"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.53"},{"volume-title":"Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 51--59","author":"Miettinen P.","key":"e_1_2_1_19_1","unstructured":"P. Miettinen and J. Vreeken . 2011. Model order selection for Boolean matrix factorization . In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 51--59 . P. Miettinen and J. Vreeken. 2011. Model order selection for Boolean matrix factorization. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 51--59."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1038\/sj.onc.1209717"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(78)90088-3"},{"volume-title":"Relational Mathematics","author":"Schmidt G.","key":"e_1_2_1_22_1","unstructured":"G. Schmidt . 2011. Relational Mathematics . Cambridge University Press . G. Schmidt. 2011. Relational Mathematics. Cambridge University Press."},{"volume-title":"Proceedings of the 12th ACM Symposium on Access Control Models and Technologies. 175--184","author":"Vaidya J.","key":"e_1_2_1_24_1","unstructured":"J. Vaidya , V. Atluri , and Q. Guo . 2007. The role mining problem: Finding a minimal descriptive set of roles . In Proceedings of the 12th ACM Symposium on Access Control Models and Technologies. 175--184 . J. Vaidya, V. Atluri, and Q. Guo. 2007. The role mining problem: Finding a minimal descriptive set of roles. In Proceedings of the 12th ACM Symposium on Access Control Models and Technologies. 175--184."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0203-9"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428078","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:23Z","timestamp":1750195463000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,9]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3428078"],"URL":"https:\/\/doi.org\/10.1145\/3428078","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2021,1,9]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}