Caching Hierarchical Skylines for Efficient Service Composition on Service Graphs

Service-oriented computing (SOC) is a paradigm for developing applications by reusing existing services. Through a standardized publishing, discovery, and composition process, SOC enables the orchestration of multiple (including third-party) services to constitute new applications. Hereby the quality of a composite service is fundamentally determined by its constituent services. To satisfy users' non-functional requirements, it is important to identify the optimal set of constituent services to participate in the composition. Practical applications usually require the optimal set to be identified with high efficiency and accuracy. This poses challenges to existing service composition methods as they either provide no accuracy guarantee or are inapplicable to large-scale problems. The challenges become more evident when considering service graphs, which contain multiple execution paths that could multiply the computational overhead. In this paper, we propose a hierarchical skyline-based approach for highly efficient service composition, which maintains and reuses varying levels of service skylines to accelerate service composition. We discuss how the skylines can be selectively computed, lazily updated, and efficiently retrieved for reuse. Experiments demonstrate the effectiveness of our approach.