The knowledge of crystal structures is essential for scientists to understand materials properties and further develop materials with specified properties. The prediction of crystal structures using first principle calculations (e.g. Density Functional Theory) is generally not scalable to large problems. Although some data mining techniques have previously been successfully applied to predict crystal structures, the predicted structures are confined to a closed set of structural prototypes. In order to get over this confinement, we propose another data-driven approach which is based on learning the set of building blocks from known crystal structures. I will describe our current problem formulation using constrained co-clustering and an extension of the affinity propagation algorithm to solve the problem. Some toy examples will be used to illustrate the problem and the algorithmic idea.