Computational searches for new materials are naturally turning from binary systems, to ternary and other multicomponent systems, and beyond. Here, we select the industrially-relevant metals titanium and aluminium and report the results of an extensive structure prediction study on the ternary titanium-carbon-oxygen (Ti-C-O) and aluminium-carbon-oxygen (Al-C-O) systems. We map out for the first time the full phase stability of Ti-C-O and Al-C-O compounds using first-principles calculations, through simple, efficient and highly parallel random structure searching in conjunction with techniques based on complex network theory. These phase stabilities emerge naturally from our `data agnostic' approach, in which we map stable compounds without recourse to structural databases or other prior knowledge. A surprising find is the predicted ambient pressure stability of octet-rule-fulfiling titanium and aluminium carbonate: Ti(CO3)$2$ and Al$2$(CO3)$3$, neither of which has to our knowledge been synthesised before. These materials could potentially act as carbon sequestering compounds. Our searches discover several additional stable and metastable ternary compounds supported by the Ti-C-O and Al-C-O systems.