The emergence of Application Service Providers (ASP) hosting Internet-based data mining services is being seen as a viable alternative for organisations that value their knowledge resources but are constrained by the high cost of data mining software. Response time is an important Quality of Service (QoS) metric for web-based data mining service providers. The ability to estimate the response time of data mining algorithms apriori benefits both clients and service providers. The advantage for the clients is that it helps to impose QoS constraints on the service level agreements and the benefit for the service-providers is that it facilitates optimising resource utilisation and scheduling. In this paper we present a novel rough sets based technique for identifying similarity templates to estimate application run times. We also present experimental results and analysis of this technique.