Abstract: With the increasing growth in popularity of Web services, extensive efforts have been brought forth to assist in Web service discovery. Web services are usually described by WSDL and advertised in UDDI registries. UDDI provides limited keyword-based search which is not powerful enough. To address this problem, information retrieval techniques are exploited to assess the similarity between two services descriptions. However, Web services description languages are schema-first, and the systems require hard up-front investment before offering powerful functionalities for Web service discovery, that is, the current research does not study how to discover Web services in a pay-as-you-go fashion. In this paper, a framework based on dataspace techniques is proposed to discover Web services in a pay-as-you-go fashion. A loosely structured data model is presented to describe Web services and the relationships among them, and then the ways to lazily compute and query this model are discussed. Furthermore, similarity is defined as intensional edges in the data model, the service information used to measure the degree of similarity can be obtained lazily, and thus the similarity can be computed in a pay-as-you-go fashion. An algorithm to support similarity-based service discovery is also presented along with a proof of its correctness. Finally, the validity of the framework is proved by the experiment.