The existing service discovery infrastructure with UDDI as the de facto standard, is limited in that it does not support more complex searching based on matching business processes. Two business processes match if they agree on their simple services, their processesing order as well as any mandatory or optional requirements for the service. This matching semanctics can be formalized by modelling business processes as annotated finite state autamata (aFSAs) and deciding emptiness of intersection aFSA. Computing the intersection of aFSAs and deciding emptiness are computationally expensive, being more than quadratic on the number of states and transistions, thus does not scale for large service repositories. This paper presents an approach for indexing and matching business processes modeled as aFSAs, for the purpose of service directory. Evaluation of this approach shows a preformance gain of several orders of magnitude over sequential matching and linear complexity with regard to the data size.