In today's world, the innovation of science and technology has become the key support for improving comprehensive national strength and changing the mode of social production and lifestyle. The country that possesses world-class scientific and technological innovation cities maximizes the attraction of global innovation factors and wins a strategic initiative in international competition. Based on the urban zip code geodatabase, an evaluation system of urban innovation with the perspective of innovation outputs, and the spatial evolutionary mode, concerning the structure of innovation space of Shanghai and Beijing from 1991 to 2014, was developed. The results of the research indicated that the zip code geodatabase provided a new perspective for studying the evolving spatial structure of urban innovation. The resulting evaluation of the spatial structure of urban innovation using the urban zip code geodatabase established by connecting random edge points, was relatively effective. The study illustrates the value of this methodology. During the study period, the spatial structure of innovation of Shanghai and Beijing demonstrated many common features: with the increase in urban space units participating in innovation year by year, the overall gap of regional innovation outputs has narrowed, and the trend towards spatial agglomeration has strengthened. The evolving spatial structure of innovation of Shanghai and Beijing demonstrated differences between the common features during the 25 years as well: in the trend towards the suburbanization of innovation resources, the spatial structure of innovation of Shanghai evolved from a single-core to a multi-core structure. A radiation effect related to traffic arteries as spatial diffusion corridors was prominent. Accordingly, a spatial correlation effect of its innovation outputs also indicated a hollowness in the city center; the spatial structure of innovation of Beijing had a single-core oriented structure all the way. Together with the tendency for innovation resources to be agglomerated in the city center, the spatial correlation effect of innovation outputs reflected the characteristics of the evolutionary feature where "rural area encircles cities". The innovation spatial structure of Shanghai and Beijing have intrinsic consistency with the spatial structure of their respective regions (Yangtze River Delta urban agglomeration and Beijing-Tianjin-Hebei metropolitan region), which suggested that the principle of proportional and disproportional distribution of a city-scale pattern of technological and innovational activities is closely related to its regional innovation pattern.