Chinese Journal of Computers   Full Text
Title	A Method of Semantic Web Service Discovery Based on Bipartite Graph Matching
Authors	DENG Shui-Guang YIN Jian-Wei LI Ying WU Jian WU Zhao-Hui
Address	(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027)
Year	2008
Issue	No.8(1364—1375)
Abstract &   Background	Abstract How to discover services for users efficiently is the key for the application of the Web service technology. The current semantic-based service discovery methods are of great inconvenience to be used and have much potential improvement for their performance. This paper proposes an information model of registered services that isn’t limited to specific service models and languages and supports semantic-annotation and interface-dependency declaration. Then, a method of service discovery based on bipartite graph matching is proposed that translates the service matchmaking to the problem of extended optimal matching for bipartite graph. It enhances the recall rate and precision as it considers the interface dependency relations within a service in matchmaking. A serial of experiments illustrate the method not only improves its efficiency much, but also has a linear complexity in time consumption to fulfill users’ requests. Keywords service oriented computing; Web service; service discovery; bipartite graph matching Background Service-Oriented Computing (SOC) is a new computing paradigm that utilizes services as fundamental elements to construct applications. It supports the development of rapid, low-cost and easy composition of distributed applications even in heterogeneous environments and also enables enterprises to flexibly solve enterprise-wide and cross-enterprise integration problems. The industry’s promotion of Web services in SOA has prompted providers to develop and publish many Web services, which are used in many areas such as business, finance and tourism. As a result, the number of services presented on the open Internet is growing at an explosive speed, which subsequently brings great challenges to the accurate, efficient and automatic retrieval of target services for consumers. Much work aspires to meet this challenge. Among those efforts, SWS (Semantic Web Service) is regarded as the most promising technology to retrieve services in an accurate and automatic way. However, most of the service matchmaking algorithms assume that each output fully depends on all the inputs in a service. In other words, it is imperative for service consumers to provide all the inputs of the service in order to get even one output of the service. According to the current matchmaking rules, a service request matches a service advertisement if the request provides all the inputs (possibly more) needed by the advertisement while the advertisement generates all the outputs (possibly more) needed by the requester. In other words, the successful match criterion demands the request to provide all the inputs of the advertised service in order to get even a part of outputs of the service. This requirement has been widely accepted by most matchmaking algorithms. However, it is too strict and can lead to some unwanted situations. If they are used, some deserved target services are not returned only because the number of each service’s input is less than the one specified in the service request, even if other information is the same. In order to overcome the shortcoming of the current methods, in this paper, the authors propose an information model of registered services that isn’t limited to specific service models and languages and supports semantic-annotation and interface-dependency declaration. Then, they propose a method of service discovery based on bipartite graph matching that translates the service matchmaking to the problem of extended optimal matching for bipartite graph. During matchmaking, the interface dependency relations within a service in matchmaking are considered. The simulations result shows that the method has better performance in decision and recall rate than others.