Identifying crystal structures in a new alloy is one of the most fundamental problems in materials science, and is an important step in many experimental and modeling efforts. Many researchers are therefore trying to find efficient techniques to predict crystal structures, which would be particularly valuable for materials developers screening large numbers of alloys. Empirical techniques, ranging from simple intuitive rules to more elaborate structure maps, have traditionally been the only option for structure prediction. However, modern total energy quantum mechanical techniques are now a powerful and practical tool, and have been used to make a number of impressive predictions. Unfortunately, the energy surface for different atomic arrangements is very large and has many local minima, making general crystal structure prediction a very difficult computational challenge. In this paper we describe a new data mining approach for computational structure prediction. This novel method combines the knowledge based methods of traditional empirical approaches with modern quantum mechanical tools. We believe that a data mining framework can provide a general structure prediction tool that makes optimal use of existing databases and computational methods.