In context-aware systems, the contextual information about human and computing situations has a strong temporal aspect i.e. it remains valid for a period of time. This temporal property can be exploited in caching mechanisms that aim to exploit such locality of reference. However, different types of contextual information have varying temporal validity durations and a varied spectrum of access frequencies as well. Such variation affects the suitability of a single caching strategy and an ideal caching mechanism should utilize dynamic strategies based on the type of context data, quality of service heuristics and access patterns and frequencies of context consuming applications. This paper presents an investigation into the utility of various context-caching strategies and proposes a novel bipartite caching mechanism in a Cloud-based context provisioning system.