Lithium-ion conductive solid oxide electrolytes are receiving increasing attention for the development of high-performance all-solid state rechargeable Li-ion batteries. In this study, we report an effective search method that uses a combination of ab initio calculations and multivariate analysis to find potential solid oxide electrolyte materials with low Li-ion hopping energies (EM) among 66 olivine-type oxides with an ordered structure LiMXO4 (main group M2+-X5+, M3+-M4+). The ionic size of M, with its associated octahedral distortion leading to the appreciable local lattice distortion during the actual Li ion hop, made the most significant contribution to the variation in EA values. Promising M X pairs (<0.30 eV) with experimental data in the Inorganic Crystal Structure Database include Mg-As (0.17 eV), Sc-Ge (0.22 eV), In-Ge (0.28 eV), and Mg-P (0.30 eV); Mg-As and Sc-Ge are reported here for the first time as battery materials. Promising theoretical compositions are also determined for Group 13 Al-X, Ga-X, and In X pairs, and for Ca-X pairs.