Knowledge discovery in ubiquitous environments is an emerging area of research at the intersection of the two major challenges of highly distributed and mobile systems and advanced knowledge discovery systems. It aims to provide a unifying framework for systematically investigating the mutual dependencies of otherwise quite unrelated technologies employed in building next-generation intelligent systems: machine learning, data mining, sensor networks, grids, peer-to-peer networks, data stream mining, activity recognition, Web 2.0, privacy, user modelling and others. This state-of-the-art survey is the outcome of a large number of workshops, summer schools, tutorials and dissemination events organized by KDubiq (Knowledge Discovery in Ubiquitous Environments), a networking project funded by the European Commission to bring together researchers and practitioners of this emerging community. It provides in its first part a conceptual foundation for the new field of ubiquitous knowledge discovery - highlighting challenges and problems, and proposing future directions in the area of 'smart', 'adaptive', and 'intelligent' learning. The second part of this volume contains selected approaches to ubiquitous knowledge discovery and treats specific aspects in detail. The contributions have been carefully selected to provide illustrations and in-depth discussions for some of the major findings of Part I.