It has been widely recognised that matchmaking is an important component for environments populated with heterogeneous services. Several researchers have developed powerful techniques for the matchmaking problem in general. There are also specific representation of service capabilities such as DAML-S which provide a more specific framework for matchmaking.

Most approaches to matchmaking have assumed a sequential search for a service with matching capabilities. This may become intractable when the number of available services gets large. In this paper, we consider how matchmaking can be developed into service directories that can be searched and maintained efficiently. Our main contribution is to show how matchmaking with DAML-S specifications can be integrated with efficient methods for searching and maintaining balanced directory trees. We also report on experimental results using an implementation based on generalised search trees.