Abstract
As multiple service providers may compete to offer the same functionality with different quality of service (e.g., latency, fee, and reputation), a key issue in service computing is selecting service providers with the best user desired quality. Existing service selection approaches mostly rely on computing a predefined objective function. When multiple quality criteria are considered, users are required to express their preference over different (and sometimes conflicting) quality attributes as numeric weights. This is a rather demanding task and an imprecise specification of the weights could miss user desired services. We propose a multi-attribute optimization approach to tackle this issue. In particular, we develop a novel concept, called service skyline, and a set of service skyline computation techniques that return a set of most interesting service providers. These providers are non-dominant in all user interested quality attributes. Thus, the service skyline ensures that the user desired providers will be included. Analytical and experimental studies justify the performance of the proposed techniques. The relative small sizes of the service skylines also make it practical for service users to make selections from them.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Balke, W.-T., Guntzer, U., Zheng, J.X.: Efficient distributed skylining for web information systems. In: EDBT, pp. 256–273 (2004)
Bartolini, I., Ciaccia, P., Patella, M.: Efficient sort-based skyline evaluation. ACM Trans. Database Syst. 33(4), 1–49 (2008)
Berchtold, S., Keim, D.A., Kriegel, H.-P.: The X-tree: an index structure for high-dimensional data. In: VLDB (1996)
Bianchini, D., De Antonellis, V., Melchiori, M.: Flexible semantic-based service matchmaking and discovery. World Wide Web 11(2), 227–251 (2008)
Borzsonyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE (2001)
Bosc, P., Pivert, O.: SQLf: a relational database language for fuzzy querying. IEEE Trans. Fuzzy Syst. 3(1), 1–17 (1995)
Chang, Y.-C., Bergman, L., Castelli, V., Li, C.-S., Lo, M.-L., Smith, J.R.: The onion technique: indexing for linear optimization queries. In: SIGMOD (2000)
Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting. In: ICDE (2003)
Cohen, S., Nutt, W., Serebrenik, A.: Rewriting aggregate queries using views. In: PODS (1999)
Dong, X., Halevy, A.Y., Madhavan, J., Nemes, E., Zhang, J.: Simlarity search for Web services. In: VLDB Conference (2004)
Godfrey, P., Shipley, R., Gryz, J.: Maximal vector computation in large data sets. In: VLDB (2005)
Gupta, A., Harinarayan, V., Quass, D.: Aggregate-query processing in data warehousing environments. In: VLDB (1995)
Hellerstein, J.M., Stonebraker, M.: Predicate migration: optimizing queries with expensive predicates. In: SIGMOD, pp. 267–276. ACM, New York (1993)
Hristidis, V., Koudas, N., Papakonstantinou, Y.: Prefer: a system for the efficient execution of multi-parametric ranked queries. In: SIGMOD (2001)
Kossmann, D., Ramsak, F., Rost, S.: Shooting stars in the sky: an online algorithm for skyline queries. In: VLDB (2002)
Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469–476 (1975)
Lee, J., Hwang, S.-W.: Bskytree: scalable skyline computation using a balanced pivot selection. In: EDBT ’10: Proceedings of the 13th International Conference on Extending Database Technology, pp. 195–206. ACM, New York (2010)
Lo, E., Yip, K.Y., Lin, K.-I., Cheung, D.W.: Progressive skylining over web-accessible databases. Data Knowl. Eng. 57(2), 122–147 (2006)
Ouzzani, M., Bouguettaya, B.: Efficient access to Web services. IEEE Internet Computing 37(3), 34–44 (2004)
Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries. In: SIGMOD (2003)
Pei, J., Jin, W., Ester, M., Tao, Y.: Catching the best views of skyline: a semantic approach based on decisive subspaces. In: VLDB (2005)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Berlin (1985)
Schmidt, C., Parashar, M.: A peer-to-peer approach to web service discovery. World Wide Web 7(2), 211–229 (2004)
Skoutas, D., Sacharidis, D., Simitsis, A., Sellis, T.: Ranking and clustering web services using multicriteria dominance relationships. IEEE T. Service Computing 3, 163–177 (2010)
Srivastava, D., Dar, S., Jagadish, H.V., Levy, A.Y.: Answering queries with aggregation using views. In: VLDB (1996)
Srivastava, U., Widom, J., Munagala, K., Motwani, R.: Query optimization over Web services. In: VLDB (2006)
Tan, K., Eng, P., Ooi, B.: Efficient progressive skyline computation. In: VLDB (2001)
Tao, Y., Xiao, X., Pei, J.: Subsky: efficient computation of skylines in subspaces. In: ICDE (2006)
Xu, Z., Martin, P., Powley, W., Zulkernine, F.: Reputation-enhanced qos-based web services discovery. In: ICWS, pp. 249–256 (2007)
Yu, Q., Bouguettaya, A.: Framework for Web service query algebra and optimization. ACM Trans. Web 2(1), 1–35 (2008)
Yu, Q., Liu, X., Bouguettaya, A., Medjahed, B.: Deploying and managing web services: issues, solutions, and directions. VLDB J. 17(3), 537–572 (2008)
Yu, Q., Bouguettaya, A.: Computing service skyline from uncertain qows. IEEE T. Service Computing 3(1), 16–29 (2010)
Yu, T., Zhang, Y., Lin, K.-J.: Efficient algorithms for web services selection with end-to-end qos constraints. ACM Trans. Web 1(1), 6 (2007)
Yuan, Y., Lin, X., Liu, Q., Wang, W., Yu, J., Zhang, Q.: Efficient computation of the skyline cube. In: VLDB (2005)
Zeng, L., Benatallah, B., Dumas, M., Kalagnanam, J., Sheng, Q.: Quality-driven Web service composition. In: WWW (2003)
Zhang, S., Mamoulis, N., Cheung, D.W.: Scalable skyline computation using object-based space partitioning. In: SIGMOD ’09: Proceedings of the 35th SIGMOD International Conference on Management of Data, pp. 483–494. ACM, New York (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yu, Q., Bouguettaya, A. Multi-attribute optimization in service selection. World Wide Web 15, 1–31 (2012). https://doi.org/10.1007/s11280-011-0121-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11280-011-0121-9