An important task of olfactory sensing is the discrimination of different odors. An odor captures the chemical state of the environment in a mixture of smell molecules, called odorants. Olfactory sensing is realized by the selective binding of odorants to a set of olfactory receptors, which in turn activates the corresponding olfactory sensory neurons, constructing the brain's first representation of the odor. Despite the high-dimensional nature of olfactory sensing, recent measurements with human olfactory receptors suggest that the odorant-receptor interaction is sparse; only a small fraction of all available pairs interact. What are the optimal interaction structures for effective olfactory discrimination, and are these optimal solutions employed by the real system? We investigate these questions by combining studies of model systems and analyses of experimental data. We show that optimization depends on the statistical properties of the olfactory environment, and furthermore suggest that the human olfactory receptors are adapted to the natural odor statistics.