Global climate change represents one of the greatest challenges facing society and ecosystems today. It impacts key aspects of everyday life and disrupts ecosystem integrity and function. The exponential growth of climate data combined with Knowledge-Discovery through Data-mining (KDD) promises an unparalleled level of understanding of how the climate system responds to anthropogenic forcing. To date, however, this potential has not been fully realized, in stark contrast to the seminal impacts of KDD in other fields such as health informatics, marketing, business intelligence, and smart city, where big data science contributed to several of the most recent breakthroughs. This disparity stems from the complexity and variety of climate data, as well as the scientific questions climate science brings forth. This perspective introduces the audience to benefits and challenges in mining large climate datasets, with an emphasis on the opportunity of using a KDD process to identify patterns of climatic relevance. The focus is on a particular method, δ-MAPS, stemming from complex network analysis. δ-MAPS is especially suited for investigating local and non-local statistical interrelationships in climate data and here is used is to elucidate both the techniques, as well as the results-interpretation process that allows extracting new insight. This is achieved through an investigation of similarities and differences in the representation of known teleconnections between climate reanalyzes and climate model outputs.