Vertically aligned nanocomposites (VANs) films have self-assembled pillar-matrix nanostructures. Owing to their large area-to-volume ratios, interfaces in VAN films are expected to play key roles in inducing functional properties, but our understanding is hindered by limited knowledge about their structures. Motivated by the lack of definitive explanation for the experimentally-found enhanced ionic conductivity in Sm-doped-CeO2/SrTiO3 VAN films, we determine the structure at vertical interfaces using random structure searching and explore how it can affect ionic conduction. This record contains the candidate structures and provenance of the DFT validation calculations. Previously unknown interface structures are found, with lower energy than that of an optimized hand-built model. We find a strongly distorted oxygen sub-lattice which gives a complex landscape of vacancy energies. The cation lattice remains similar to the bulk phase but has a localized strain field. The excess energy of the interface is similar to that of high angle grain boundaries in SrTiO3.