Loading...
Please wait, while we are loading the content...
Similar Documents
Labeling Recursive Workflow Executions On-the-Fly (2011)
| Content Provider | CiteSeerX |
|---|---|
| Author | Davidson, Susan B. Milo, Tova Bao, Zhuowei |
| Abstract | This paper presents a compact labeling scheme for answering reachability queries over workflow executions. In contrast to previous work, our scheme allows nodes (processes and data) in the execution graph to be labeled on-the-fly, i.e., in a dynamic fashion. In this way, reachability queries can be answered as soon as the relevant data is produced. We first show that, in general, for workflows that contain recursion, dynamic labeling of executions requires long (linearsize) labels. Fortunately, most real-life scientific workflows are linear recursive, and for this natural class we show that dynamic, yet compact (logarithmic-size) labeling is possible. Moreover, our scheme labels the executions in linear time, and answers any reachability query in constant time. We also show that linear recursive workflows are, in some sense, the largest class of workflows that allow compact, dynamic labeling schemes. Interestingly, the empirical evaluation, performed over both real and synthetic workflows, shows that our proposed dynamic scheme outperforms the state-of-the-art static scheme for large executions, and creates labels that are shorter by a factor of almost 3. |
| File Format | |
| Publisher Date | 2011-01-01 |
| Access Restriction | Open |
| Subject Keyword | Large Execution Recursive Workflow Execution On-the-fly Dynamic Fashion Execution Graph Reachability Query Dynamic Labeling Scheme Synthetic Workflow Dynamic Scheme Empirical Evaluation Workflow Execution Relevant Data State-of-the-art Static Scheme Dynamic Labeling Real-life Scientific Workflow Natural Class Linear Time Constant Time Linear Recursive Workflow Compact Labeling Scheme |
| Content Type | Text |
| Resource Type | Article |
