A Grammar-Based Index for Matching Business Processes

Bendick Mahleko, Andreas Wombacher, Peter Fankhauser

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    17 Citations (Scopus)
    138 Downloads (Pure)


    Complex services are composed of simple services which typically need to be processed in a particular order. Two complex services only match if they agree on both, their simple services and their processing order. This matching semantics can be formalized by means of modelling complex services as finite state automata (FSAs), and analysing the intersection of the FSAs. However, computing the intersection of FSAs is computationally expensive, and thus does not scale for large service repositories. This paper presents an approach for indexing and matching complex services using an abstraction that transforms the underlying FSA via its grammar into a form that can be indexed using available index mechanisms. Evaluation of this approach shows a performance gain of several orders of magnitude as compared to sequential matching.
    Original languageUndefined
    Title of host publicationIEEE International Conference on Web Services (ICWS'05)
    Place of PublicationLos Alamitos, California, USA
    PublisherIEEE Computer Society Press
    Number of pages10
    ISBN (Print)0769524095
    Publication statusPublished - Jul 2005
    EventIEEE International Conference on Web Services, ICWS 2005: Bridge the Gap between Business Services and IT Services - Orlando, Florida, USA, Orlando, United States
    Duration: 11 Jul 200515 Jul 2005

    Publication series

    PublisherIEEE Computer Society Press


    ConferenceIEEE International Conference on Web Services, ICWS 2005
    Abbreviated titleICWS
    Country/TerritoryUnited States
    Other11-15 July 2005


    • EWI-10452
    • IR-64180
    • METIS-226868

    Cite this