Top K Query for QoS-Aware Automatic Service Composition

With the proliferation of Web services, service engineers demand automatic service composition algorithms that not only synthesize the correct service compositions from thousands of services but also satisfy the quality requirements of users. This is known as QoS-aware automatic service composition problem. Our observation is that current research of only finding the optimal service composition result has several shortcomings. Users have to utilize the optimal one, which will make it rigid, and consequently bring about problems, such as overload of “hot services” and lack of choices for users. To cope with these problems, a top k query mechanism is introduced in this paper, and a progressive and incremental Key-Path-Based Loose (KPL) algorithm with 100 percent accuracy is proposed. Our QSynth, which won the performance championship of Web Service Challenge 2009 and 2010, is extended to support top k query based on KPL algorithm. Evaluations show that, compared to the state of the art, KPL algorithm achieves superior scalability and accuracy with respect to a large variety of composition scenarios. Moreover, we generalize a new graph problem: top k DAGs (Directed Acyclic Graphs) problem based on the above work. Applications of this new graph problem contain API recommender, supply chain, and so on. KPL algorithm illustrated in this paper can address them efficiently, too.