The COSSO is a new technique for discovering interpretable structures and for estimation in high dimensional data. It is based on the functional ANOVA approach, which decomposes a high dimensional function into main effects and interactions of different orders, thus gives interpretable structures and intuitive measures of the relative importance of different input variables. The COSSO fits functional ANOVA by a method of regularization with the penalty functional being the sum of component norms, instead of the squared norm employed in the traditional methods. We show that the COSSO selects variables and estimates ANOVA components simultaneously, and enjoys good theoretical properties in both aspects. It provides a unified framework for several recent proposals for variable selection and estimation in linear models and functional ANOVA in statistical and machine learning literature. The COSSO algorithm is fully automatic, and is suitable for data mining applications. We compare the COSSO with the MARS, a popular data mining tool which also builds functional ANOVA, in simulations and real examples. The COSSO gives very competitive performances both in terms of prediction accuracy and variable selection.