In pervasive computing environments, understanding the context of an entity is essential for adapting the application behavior to changing situations. In our view, context is a high-level representation of a user or entity's state and can capture location, activities, social relationships, capabilities, etc. Inherently, however, these high-level context metrics are difficult to capture using uni-modal sensors only and must therefore be inferred using multi-modal sensors. A key challenge in supporting context-aware pervasive computing is how to determine multiple high-level context metrics simultaneously and energy-efficiently using low-level sensor data streams collected from the environment and the entities present therein. A key challenge is addressing the fact that the algorithms that determine different high-level context metrics may compete for access to low-level sensors. In this paper, we first highlight the complexities of determining multiple context metrics as compared to a single context and then develop a novel framework and practical implementation for this problem. The proposed framework captures the tradeoff between the accuracy of estimating multiple context metrics and the overhead incurred in acquiring the necessary sensor data streams. In particular, we develop two variants of a heuristic algorithm for multi-context search that compute the optimal set of sensors contributing to the multi-context determination as well as the associated parameters of the sensing tasks (e.g., the frequency of data acquisition). Our goal is to satisfy the application requirements for a specified accuracy at a minimum cost. We compare the performance of our heuristics with a brute-force based approach for multi-context determination. Experimental results with SunSPOT, Shimmer and Smartphone sensors in smart home environments demonstrate the potential impact of the proposed framework.