In this work, we present UDDI registry by example (Urbe), a novel approach for Web service retrieval based on the evaluation of similarity between Web service interfaces. Our approach assumes that the Web service interfaces are defined with Web service description language (WSDL) and the algorithm combines the analysis of their structures and the analysis of the terms used inside them. The higher the similarity, the less are the differences among their interfaces. As a consequence, Urbe is useful when we need to find a Web service suitable to replace an existing one that fails. Especially in autonomic systems, this situation is very common since we need to ensure the self-management, the self-configuration, the self-optimization, the self-healing, and the self-protection of the application that is based on the failed Web service. A semantic-oriented variant of the approach is also proposed, where we take advantage of annotations semantically enriching WSDL specifications. Semantic Annotation for WSDL (SAWSDL) is adopted as a language to annotate a WSDL description. The Urbe approach has been implemented in a prototype that extends a universal description, discovery and integration (UDDI) compliant Web service registry.