The analysis of complex data distributed over large or highly textured regions poses new challenges for spatial statistics. Object Oriented Spatial Statistics (O2S2) is a recent system of ideas and methods that allows to analyze high dimensional and complex data when their spatial dependence is an important issue. We present the key concepts of O2S2, as a general approach to analyze and predict georeferenced complex data, interpreted as objects in appropriate mathematical spaces. Examples of object data include functional data, distributional data or tensors. We discuss the extension of key geostatistical concepts (e.g., stationarity) and methods (e.g., Kriging) to the context of O2S2, and discuss recent extensions of these methods that permit the analysis of object data distributed over complex regions. Here, we shall ground our developments on computational intensive methods, based on random domain decompositions of the study domain, and on a novel model valid on tree-structured domains. The presented models and methods will be illustrated through real environmental case studies.