Querying data sources containing heterogeneous and dynamic information is a complex task: high quality answers need to be produced fast to cope with the dynamicity of the environment. A common solution to reduce query processing time is to rely on approximate processing approaches, which provide a faster answer at the cost of a lower accuracy. On the other hand, user involvement in the interpretation of the request, is not adequate in dynamic contexts, where urgent requests hamper user interaction. In order to cope with the difficulties raised by the heterogeneity and dynamic nature of the considered environments, new solutions should be devised, relying either on additional knowledge about the current execution (e.g., query context or user profile) or previous executions of similar requests. The goal of this project is to exploit information related to requests recurring over time for efficiently and effectively process, in an approximate way, complex requests on heterogeneous and dynamic data spaces, each represented as a graph dataset, possibly available on a highly distributed environment, while guaranteeing user satisfaction and limiting as much as possible user interactions. The idea is to take advantage of prior processing in order to obtain shortcuts to different points in the query processing stack. The approach we envision generalizes smart caching methods allowing approximate matching and various kinds of information to be associated with cached queries in order to improve query processing even further. The proposed approaches are tailored to graph data stores.