Searching for a Web service that meets the user requirements can be a complex task especially when the system starts to scale up by increasing the number of Web services, w, in the UDDI registry and by enlarging the number of QoS features (f) by which each Web service is described. This can be perceived as the commonly known nearest neighbor search problem, which typically imposes a time or storage complexity that is exponential in f. In this work, we present a new algorithm (wsSVD) that is founded on the algebraic matrix operation called Singular Value Decomposition (SVD). The basic idea is to encode the features of each Web service by a single value using the SVD. When a user seeks a Web service based on some specific requirements, these requirements get encoded by a single value using the same algorithm, and the matching process takes place in order to find the closest Web service that fulfills the user requirements. Our experiments show that the wsSVD algorithm performs and scales up well in comparison with other matching algorithms.