Growing demand for the tasty and healthy food has driven the development of low-calorie sweeteners, sweet taste modulators, and bitter masking compounds originated from natural sources. With the discovery of human taste receptors, increasing numbers of sweet taste modulators have been identified through human taste response and molecular docking techniques. However, the discovery of novel taste-active molecules in nature can be accelerated by using advanced spectrometry technologies based on structure-activity relationships (SARs). SARs explain why structurally similar compounds can elicit similar taste qualities. Given the characterization of structural information from reported data, strategies employing SAR techniques to find structurally similar compounds become an innovative approach to expand knowledge of sweeteners. This review aims to summarize the structural patterns of known natural non-nutritive sweeteners, sweet taste enhancers, and bitter masking compounds. Innovative SAR-based approaches to explore sweetener derivatives are also discussed. Most sweet-tasting flavonoids belong to either the flavanonols or the dihydrochalcones and known bitter masking molecules are flavanones. Based on SAR findings that structural similarities are related to the sensory properties, innovative methodologies described in this paper can be applied to screen and discover the derivatives of taste-active compounds or potential taste modulators.