A Grammar-Based Index for Matching Business Processes

Bendick Mahleko, Andreas Wombacher, Peter Fankhauser

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

15 Citations (Scopus)
41 Downloads (Pure)

Abstract

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
Pages21-30
Number of pages10
ISBN (Print)0769524095
DOIs
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

Name
PublisherIEEE Computer Society Press
Volume1

Conference

ConferenceIEEE International Conference on Web Services, ICWS 2005
Abbreviated titleICWS
CountryUnited States
CityOrlando
Period11/07/0515/07/05
Other11-15 July 2005

Keywords

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

Cite this

Mahleko, B., Wombacher, A., & Fankhauser, P. (2005). A Grammar-Based Index for Matching Business Processes. In IEEE International Conference on Web Services (ICWS'05) (pp. 21-30). [10.1109/ICWS.2005.6] Los Alamitos, California, USA: IEEE Computer Society Press. https://doi.org/10.1109/ICWS.2005.6
Mahleko, Bendick ; Wombacher, Andreas ; Fankhauser, Peter. / A Grammar-Based Index for Matching Business Processes. IEEE International Conference on Web Services (ICWS'05). Los Alamitos, California, USA : IEEE Computer Society Press, 2005. pp. 21-30
@inproceedings{a0e7cdb1cf1b4e469bcdc45069901d0b,
title = "A Grammar-Based Index for Matching Business Processes",
abstract = "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.",
keywords = "EWI-10452, IR-64180, METIS-226868",
author = "Bendick Mahleko and Andreas Wombacher and Peter Fankhauser",
note = "Website conference: http://conferences.computer.org/icws/2005/",
year = "2005",
month = "7",
doi = "10.1109/ICWS.2005.6",
language = "Undefined",
isbn = "0769524095",
publisher = "IEEE Computer Society Press",
pages = "21--30",
booktitle = "IEEE International Conference on Web Services (ICWS'05)",

}

Mahleko, B, Wombacher, A & Fankhauser, P 2005, A Grammar-Based Index for Matching Business Processes. in IEEE International Conference on Web Services (ICWS'05)., 10.1109/ICWS.2005.6, IEEE Computer Society Press, Los Alamitos, California, USA, pp. 21-30, IEEE International Conference on Web Services, ICWS 2005, Orlando, United States, 11/07/05. https://doi.org/10.1109/ICWS.2005.6

A Grammar-Based Index for Matching Business Processes. / Mahleko, Bendick; Wombacher, Andreas; Fankhauser, Peter.

IEEE International Conference on Web Services (ICWS'05). Los Alamitos, California, USA : IEEE Computer Society Press, 2005. p. 21-30 10.1109/ICWS.2005.6.

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

TY - GEN

T1 - A Grammar-Based Index for Matching Business Processes

AU - Mahleko, Bendick

AU - Wombacher, Andreas

AU - Fankhauser, Peter

N1 - Website conference: http://conferences.computer.org/icws/2005/

PY - 2005/7

Y1 - 2005/7

N2 - 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.

AB - 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.

KW - EWI-10452

KW - IR-64180

KW - METIS-226868

U2 - 10.1109/ICWS.2005.6

DO - 10.1109/ICWS.2005.6

M3 - Conference contribution

SN - 0769524095

SP - 21

EP - 30

BT - IEEE International Conference on Web Services (ICWS'05)

PB - IEEE Computer Society Press

CY - Los Alamitos, California, USA

ER -

Mahleko B, Wombacher A, Fankhauser P. A Grammar-Based Index for Matching Business Processes. In IEEE International Conference on Web Services (ICWS'05). Los Alamitos, California, USA: IEEE Computer Society Press. 2005. p. 21-30. 10.1109/ICWS.2005.6 https://doi.org/10.1109/ICWS.2005.6