Finding relevant Web services and composing them into value-added applications is becoming increasingly important in cloud and service based marketplaces. The key problem with current approaches to finding relevant Web services is that most of them only provide searches over a discrete set of features using exact keyword matching. We demonstrate in this paper that by utilizing well known indexing scheme such as inverted file and R-tree indexes over Web services attributes, the Earth Mover's Distance (EMD) algorithm can be used efficiently to find partial matches between a query and a database of Web services.