Selection and Ranking of Propositional Formulas for Large-Scale Service Directories

Abstract

In this paper we consider scenarios, such as web service composition, where a planner needs to discover its operators by querying a potentially very large and dynamically changing directory. Our contribution is a directory system that represents service advertisements and requests as propositional formulas and provides a flexible query language allowing complex selection and ranking expressions. The internal structure of the directory enables efficient selection and ranking in the presence of a large number of services thanks to its organization as a balanced tree with an extra “intersection predicate”. In order to optimally exploit the index structure of the directory, a transformation scheme is applied to the original query. Experimental results on randomly generated service composition problems illustrate the benefits of our approach. 1