Top-k dominant web services under multi-criteria matching

ABSTRACT

As we move from a Web of data to a Web of services, enhancing the capabilities of the current Web search engines with effective and efficient techniques for Web services retrieval and selection becomes an important issue. Traditionally, the relevance of a Web service advertisement to a service request is determined by computing an overall score that aggregates individual matching scores among the various parameters in their descriptions. Two drawbacks characterize such approaches. First, there is no single matching criterion that is optimal for determining the similarity between parameters. Instead, there are numerous approaches ranging from using Information Retrieval similarity metrics up to semantic logic-based inference rules. Second, the reduction of individual scores to an overall similarity leads to significant information loss. Since there is no consensus on how to weight these scores, existing methods are typically pessimistic, adopting a worst-case scenario. As a consequence, several services, e.g., those having a single unrelated parameter, can be excluded from the result set, even though they are potentially good alternatives. In this work, we present a methodology that overcomes both deficiencies. Given a request, we introduce an objective measure that assigns a dominance score to each advertised Web service. This score takes into consideration all the available criteria for each parameter in the request. We investigate three distinct definitions of dominance score, and we devise efficient algorithms that retrieve the top-k most dominant Web services in each case. Extensive experimental evaluation on real requests and relevance sets, as well as on synthetically generated scenarios, demonstrates both the effectiveness of the proposed technique and the efficiency of the algorithms.

REFERENCES

• 1: R. Akkiraju and et. al. Web Service Semantics -- WSDL-S. In W3C Member Submission, November 2005.
• 2: G. Alonso, F. Casati, H. A. Kuno, and V. Machiraju. Web Services -- Concepts, Architectures and Applications. Data-Centric Systems and Applications. Springer, 2004.
• 3: Javed A. Aslam , Mark Montague, Models for metasearch, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.276-284, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384007]
• 4: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: W.-T. Balke, U. Güntzer, and C. Lofi. Eliciting matters -- controlling skyline sizes by incremental integration of user preferences. In DASFAA, pages 551--562, 2007.
• 6: W.-T. Balke and M. Wagner. Cooperative Discovery for User-Centered Web Service Provisioning. In ICWS, pages 191--197, 2003.
• 7: Ilaria Bartolini , Paolo Ciaccia , Marco Patella, Efficient sort-based skyline evaluation, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-49, November 2008 [doi>10.1145/1412331.1412343]
• 8: U. Bellur and R. Kulkarni. Improved Matchmaking Algorithm for Semantic Web Services Based on Bipartite Graph Matching. In ICWS, pages 86--93, 2007.
• 9: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 10: M. Burstein and et. al. OWL-S: Semantic Markup for Web Services. In W3C Member Submission, November 2004.
• 11: Jorge Cardoso, Discovering Semantic Web Services with and without a Common Ontology Commitment, Proceedings of the IEEE Services Computing Workshops, p.183-190, September 18-22, 2006 [doi>10.1109/SCW.2006.12]
• 12: Suleyman Cetintas , Luo Si, Exploration of the tradeoff between effectiveness and efficiency for results merging in federated search, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277869]
• 13: Chee-Yong Chan , H. V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , Zhenjie Zhang, Finding k-dominant skylines in high dimensional space, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142530]
• 14: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with Presorting. In ICDE, pages 717--816, 2003.
• 15: John Colgrave , Rama Akkiraju , Richard Goodwin, External Matching in UDDI, Proceedings of the IEEE International Conference on Web Services, p.226, June 06-09, 2004 [doi>10.1109/ICWS.2004.57]
• 16: Xin Dong , Alon Halevy , Jayant Madhavan , Ema Nemes , Jun Zhang, Similarity search for web services, Proceedings of the Thirtieth international conference on Very large data bases, p.372-383, August 31-September 03, 2004, Toronto, Canada
• 17: Mohamed Farah , Daniel Vanderpooten, An outranking approach for rank aggregation in information retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277843]
• 18: E. A. Fox and J. A. Shaw. Combination of Multiple Searches. In 2nd TREC, NIST, pages 243--252, 1993.
• 19: H. Lausen, A. Polleres, and D. Roman (eds.). Web Service Modeling Ontology (WSMO). In W3C Member Submission, June 2005.
• 20: Thorsten Joachims , Filip Radlinski, Search Engines that Learn from Implicit Feedback, Computer, v.40 n.8, p.34-40, August 2007 [doi>10.1109/MC.2007.289]
• 21: Frank Kaufer , Matthias Klusch, WSMO-MX: A Logic Programming Based Hybrid Service Matchmaker, Proceedings of the European Conference on Web Services, p.161-170, December 04-06, 2006 [doi>10.1109/ECOWS.2006.39]
• 22: M. Klusch and B. Fries. Hybrid OWL-S Service Retrieval with OWLS-MX: Benefits and Pitfalls. In SMRR, 2007.
• 23: Matthias Klusch , Benedikt Fries , Katia Sycara, Automated semantic web service discovery with OWLS-MX, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160796]
• 24: Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
• 25: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 26: Joon Ho Lee, Analyses of multiple evidence combination, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-276, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 27: Ken C. K. Lee , Baihua Zheng , Huajing Li , Wang-Chien Lee, Approaching the skyline in Z order, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 28: Lei Li , Ian Horrocks, A software framework for matchmaking based on semantic web technology, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775199]
• 29: David Lillis , Fergus Toolan , Rem Collier , John Dunnion, ProbFuse: a probabilistic approach to data fusion, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148197]
• 30: X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. Selecting Stars: The k Most Representative Skyline Operator. In ICDE, pages 86--95, 2007.
• 31: Mark Montague , Javed A. Aslam, Condorcet fusion for improved retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584881]
• 32: Massimo Paolucci , Takahiro Kawamura , Terry R. Payne , Katia P. Sycara, Semantic Matching of Web Services Capabilities, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.333-347, June 09-12, 2002
• 33: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005 [doi>10.1145/1061318.1061320]
• 34: Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 35: Jian Pei , Yidong Yuan , Xuemin Lin , Wen Jin , Martin Ester , Qing Liu , Wei Wang , Yufei Tao , Jeffrey Xu Yu , Qing Zhang, Towards multidimensional subspace skyline analysis, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1335-1381, December 2006 [doi>10.1145/1189769.1189774]
• 36: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 37: L. Si and J. Callan. CLEF 2005: Multilingual Retrieval by Combining Multiple Multilingual Ranked Lists. In Proceedings of the 6th Workshop of the Cross-Language Evalution Forum, pages 121--130, 2005.
• 38: David E. Simmen , Mehmet Altinel , Volker Markl , Sriram Padmanabhan , Ashutosh Singh, Damia: data mashups for intranet applications, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376734]
• 39: D. Skoutas, A. Simitsis, and T. K. Sellis. A Ranking Mechanism for Semantic Web Service Discovery. In IEEE SCW, pages 41--48, 2007.
• 40: Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
• 41: Christopher C. Vogt , Garrison W. Cottrell, Fusion Via a Linear Combination of Scores, Information Retrieval, v.1 n.3, p.151-173, October 1999 [doi>10.1023/A:1009980820262]
• 42: Man Lung Yiu , Nikos Mamoulis, Efficient processing of top-k dominating queries on multi-dimensional data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria