algorithm - How to find pattern groups in boolean array? -

given 2d array of boolean values want find patterns consist of @ least 2 columns , @ least 2 rows. problem close finding cliques in graph.

in example below green cells represent "true" bits, greys "false". pattern 1 contains cols 1,3,4 , 5 , rows 1 , 2. pattern 2 contains columns 2 , 4, , rows 2,3,4.

business idea behind finding similarity patterns among various groups of social network users. in real world number of rows can go 3e7, , number of columns 300.

can't figure out solution other brute force matching.

please advice proper name of problem, read more, or advice elegant solution.

this (equivalent to) asking bicliques (complete bipartite subgraphs) larger size in bipartite graph. here rows vertices of 1 part of graph, , columns vertices of other part b, , there edge between u \in , v \in b whenever cell @ row u, column v green.

although want find patterns, want find maximal ones -- is, patterns cannot extended become larger patterns adding more rows or columns. (otherwise, pattern c >= 2 columns , r >= 3 rows, more 2^(c-2)*2^(r-3) non-maximal patterns can formed deleting of rows or columns.)

but listing maximal patterns can take time exponential in number of rows , columns, assuming p != np. that's because problem of finding maximum (i.e. largest-possible) pattern, in terms of total number of green cells, has been proven np-complete: if possible list maximal patterns in polynomial time, so, , pick largest, thereby solving np-complete problem in polynomial time.