{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T07:40:01Z","timestamp":1748590801587,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319235240"},{"type":"electronic","value":"9783319235257"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23525-7_3","type":"book-chapter","created":{"date-parts":[[2015,8,28]],"date-time":"2015-08-28T08:20:13Z","timestamp":1440750013000},"page":"36-52","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Generalized Matrix Factorizations as a Unifying Framework for Pattern Set Mining: Complexity Beyond Blocks"],"prefix":"10.1007","author":[{"given":"Pauli","family":"Miettinen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,29]]},"reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-03685-9_26","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"N Alon","year":"2009","unstructured":"Alon, N., Panigrahy, R., Yekhanin, S.: Deterministic approximation algorithms for the nearest codeword problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) PPROX and RANDOM 2009. LNCS, vol. 5687, pp. 339\u2013351. Springer, Heidelberg (2009)"},{"issue":"1","key":"3_CR2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10107-011-0459-x","volume":"129","author":"BPW Ames","year":"2011","unstructured":"Ames, B.P.W., Vavasis, S.A.: Nuclear norm minimization for the planted clique and biclique problems. Math. Program. B 129(1), 69\u201389 (2011)","journal-title":"Math. Program. B"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/978-3-662-44848-9_4","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"M Araujo","year":"2014","unstructured":"Araujo, M., G\u00fcnnemann, S., Mateos, G., Faloutsos, C.: Beyond blocks: hyperbolic community detection. In: Calders, T., Esposito, F., H\u00fcllermeier, E., Meo, R. (eds.) ECML PKDD 2014, Part I. LNCS, vol. 8724, pp. 50\u201365. Springer, Heidelberg (2014)"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. In: FOCS 1993, pp. 724\u2013733 (1993)","DOI":"10.1109\/SFCS.1993.366815"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"B\u011blohl\u00e1vek, R., Krmelova, M.: Beyond boolean matrix decompositions: toward factor analysis and dimensionality reduction of ordinal data. In: ICDM 2013, pp. 961\u2013966 (2013)","DOI":"10.1109\/ICDM.2013.127"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.jcss.2009.05.002","volume":"76","author":"R B\u011blohl\u00e1vek","year":"2010","unstructured":"B\u011blohl\u00e1vek, R., Vychodil, V.: Discovery of optimal factors in binary data via a novel method of matrix decomposition. J. Comput. Syst. Sci. 76(1), 3\u201320 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/978-3-642-15387-7_51","volume-title":"Knowledge-Based and Intelligent Information and Engineering Systems","author":"R Belohlavek","year":"2010","unstructured":"Belohlavek, R., Vychodil, V.: Factorizing three-way binary data with triadic formal concepts. In: Setchi, R., Jordanov, I., Howlett, R.J., Jain, L.C. (eds.) KES 2010, Part I. LNCS, vol. 6276, pp. 471\u2013480. Springer, Heidelberg (2010)"},{"key":"3_CR8","unstructured":"Berman, P., Karpinski, M.: Approximating minimum unsatisfiability of linear equations. In: SODA 2002, pp. 514\u2013516 (2002)"},{"issue":"3","key":"3_CR9","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1007\/s10618-012-0284-8","volume":"26","author":"L Cerf","year":"2013","unstructured":"Cerf, L., Besson, J., Nguyen, K.N.T., Boulicaut, J.F.: Closed and noise-tolerant patterns in n-ary relations. Data Min. Knowl. Discov. 26(3), 574\u2013619 (2013)","journal-title":"Data Min. Knowl. Discov."},{"issue":"3","key":"3_CR10","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10618-010-0209-3","volume":"23","author":"T De Bie","year":"2011","unstructured":"De Bie, T.: Maximum entropy models and subjective interestingness: an application to tiles in binary databases. Data Min. Knowl. Discov. 23(3), 407\u2013446 (2011)","journal-title":"Data Min. Knowl. Discov."},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/TIT.2002.806118","volume":"49","author":"I Dumer","year":"2003","unstructured":"Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inform. Theory 49(1), 22\u201337 (2003)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Ene, A., Horne, W., Milosavljevic, N., Rao, P., Schreiber, R., Tarjan, R.E.: Fast exact and heuristic methods for role minimization problems. In: SACMAT 2008, pp. 1\u201310 (2008)","DOI":"10.1145\/1377836.1377838"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for Approximating Set Cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"3_CR14","volume-title":"Computers and intractability: A guide to the theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-540-30214-8_22","volume-title":"Discovery Science","author":"F Geerts","year":"2004","unstructured":"Geerts, F., Goethals, B., Mielik\u00e4inen, T.: Tiling databases. In: Suzuki, E., Arikawa, S. (eds.) DS 2004. LNCS (LNAI), vol. 3245, pp. 278\u2013289. Springer, Heidelberg (2004)"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. 9, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR17","unstructured":"Junttila, E.: Patterns in permuted binary matrices. Ph.D. thesis, Helsinki University Press, Helsinki, August 2011"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"K\u00f6tter, T., G\u00fcnnemann, S., Berthold, M., Faloutsos, C.: Extracting taxonomies from bipartite graphs. In: WWW 2015 Companion, pp. 51\u201352 (2015)","DOI":"10.1145\/2740908.2742753"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Koutra, D., Kang, U., Vreeken, J., Faloutsos, C.: VoG: summarizing and understanding large graphs. In: SDM 2014, pp. 91\u201399 (2014)","DOI":"10.1137\/1.9781611973440.11"},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-662-44851-9_7","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"T Le Van","year":"2014","unstructured":"Le Van, T., van Leeuwen, M., Nijssen, S., Fierro, A.C., Marchal, K., De Raedt, L.: Ranked tiling. In: Calders, T., Esposito, F., H\u00fcllermeier, E., Meo, R. (eds.) ECML PKDD 2014, Part II. LNCS, vol. 8725, pp. 98\u2013113. Springer, Heidelberg (2014)"},{"issue":"2","key":"3_CR21","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"12","key":"3_CR22","doi-asserted-by":"publisher","first-page":"2900","DOI":"10.1109\/TKDE.2013.181","volume":"26","author":"C Lucchese","year":"2013","unstructured":"Lucchese, C., Orlando, S., Perego, R.: A Unifying Framework for Mining Approximate Top-k Binary Patterns. IEEE Trans. Knowl. Data Eng. 26(12), 2900\u20132913 (2013)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Maurus, S., Plant, C.: Ternary matrix factorization. In: ICDM 2014, pp. 400\u2013409 (2014)","DOI":"10.1109\/ICDM.2014.40"},{"issue":"4","key":"3_CR24","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.ipl.2008.05.007","volume":"108","author":"P Miettinen","year":"2008","unstructured":"Miettinen, P.: On the positive-negative partial set cover problem. Inform. Process. Lett. 108(4), 219\u2013221 (2008)","journal-title":"Inform. Process. Lett."},{"key":"3_CR25","unstructured":"Miettinen, P.: Matrix Decomposition Methods for Data Mining: Computational Complexity and Algorithms. Ph.D. thesis, Department of Computer Science, University of Helsinki (2009)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Miettinen, P.: Boolean tensor factorizations. In: ICDM 2011, pp. 447\u2013456 (2011)","DOI":"10.1109\/ICDM.2011.28"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Miettinen, P.: Fully dynamic quasi-biclique edge covers via Boolean matrix factorizations. In: DyNetMM 2013, pp. 17\u201324 (2013)","DOI":"10.1145\/2489247.2489250"},{"issue":"10","key":"3_CR28","doi-asserted-by":"publisher","first-page":"1348","DOI":"10.1109\/TKDE.2008.53","volume":"20","author":"P Miettinen","year":"2008","unstructured":"Miettinen, P., Mielik\u00e4inen, T., Gionis, A., Das, G., Mannila, H.: The Discrete Basis Problem. IEEE Trans. Knowl. Data Eng. 20(10), 1348\u20131362 (2008)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"3","key":"3_CR29","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131(3), 651\u2013654 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"3_CR30","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jda.2006.03.008","volume":"5","author":"D Peleg","year":"2007","unstructured":"Peleg, D.: Approximation algorithms for the Label-Cover$$_{MAX}$$ and Red-Blue Set Cover problems. J. Discrete Alg. 5(1), 55\u201364 (2007)","journal-title":"J. Discrete Alg."},{"key":"3_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/978-3-642-40988-2_33","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"J Ramon","year":"2013","unstructured":"Ramon, J., Miettinen, P., Vreeken, J.: Detecting bicliques in GF[q]. In: Blockeel, H., Kersting, K., Nijssen, S., \u017delezn\u00fd, F. (eds.) ECML PKDD 2013, Part I. LNCS, vol. 8188, pp. 509\u2013524. Springer, Heidelberg (2013)"},{"issue":"2","key":"3_CR32","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"HU Simon","year":"1990","unstructured":"Simon, H.U.: On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math. 3(2), 294\u2013310 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"3_CR33","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s10618-010-0202-x","volume":"23","author":"J Vreeken","year":"2011","unstructured":"Vreeken, J., van Leeuwen, M., Siebes, A.: Krimp: mining itemsets that compress. Data Min. Knowl. Discov. 23(1), 169\u2013214 (2011)","journal-title":"Data Min. Knowl. Discov."},{"issue":"2","key":"3_CR34","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s10618-010-0203-9","volume":"23","author":"Y Xiang","year":"2011","unstructured":"Xiang, Y., Jin, R., Fuhry, D., Dragan, F.F.: Summarizing transactional databases with overlapped hyperrectangles. Data Min. Knowl. Discov. 23(2), 215\u2013251 (2011)","journal-title":"Data Min. Knowl. Discov."},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Yang, J., Leskovec, J.: Overlapping community detection at scale: a nonnegative matrix factorization approach. In: WSDM 2013 (2013)","DOI":"10.1145\/2433396.2433471"},{"issue":"2","key":"3_CR36","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-Deletion Problems on Bipartite Graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23525-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T06:58:55Z","timestamp":1748588335000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-23525-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319235240","9783319235257"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23525-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"29 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}