A Grammar-Based Index for Matching Business Processes

Bendick Mahleko; Andreas Wombacher; Peter Fankhauser

doi:10.1109/ICWS.2005.6

A Grammar-Based Index for Matching Business Processes

Bendick Mahleko, Andreas Wombacher, Peter Fankhauser

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

17 Citations (Scopus)

198 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 language	Undefined
Title of host publication	IEEE International Conference on Web Services (ICWS'05)
Place of Publication	Los Alamitos, California, USA
Publisher	IEEE
Pages	21-30
Number of pages	10
ISBN (Print)	0769524095
DOIs	https://doi.org/10.1109/ICWS.2005.6
Publication status	Published - Jul 2005
Event	IEEE 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 2005 → 15 Jul 2005

Publication series

Name
Publisher	IEEE Computer Society Press
Volume	1

Conference

Conference	IEEE International Conference on Web Services, ICWS 2005
Abbreviated title	ICWS
Country/Territory	United States
City	Orlando
Period	11/07/05 → 15/07/05
Other	11-15 July 2005

Keywords

EWI-10452
IR-64180
METIS-226868

Access to Document

10.1109/ICWS.2005.6

Cite this

@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/; IEEE International Conference on Web Services, ICWS 2005 ; Conference date: 11-07-2005 Through 15-07-2005",

year = "2005",

month = jul,

doi = "10.1109/ICWS.2005.6",

language = "Undefined",

isbn = "0769524095",

publisher = "IEEE",

pages = "21--30",

booktitle = "IEEE International Conference on Web Services (ICWS'05)",

address = "United States",

}

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

CY - Los Alamitos, California, USA

T2 - IEEE International Conference on Web Services, ICWS 2005

Y2 - 11 July 2005 through 15 July 2005

ER -