Effective and efficient similarity search in scientific workflow repositories

• Published in: Future generation computer systems 2016-03, Vol.56, p.584-594
• Main Authors: Starlinger, Johannes, Cohen-Boulakia, Sarah, Khanna, Sanjeev, Davidson, Susan B., Leser, Ulf
• Format: Article
• Language: English
• Subjects: Bioinformatics; Computer Science; Scientific workflows; Similarity search
• ISSN: 0167-739X; 1872-7115
• DOI: 10.1016/j.future.2015.06.012

Scientific workflows have become a valuable tool for large-scale data processing and analysis. This has led to the creation of specialized online repositories to facilitate workflow sharing and reuse. Over time, these repositories have grown to sizes that call for advanced methods to support workflow discovery, in particular for similarity search. Effective similarity search requires both high quality algorithms for the comparison of scientific workflows and efficient strategies for indexing, searching, and ranking of search results. Yet, the graph structure of scientific workflows poses severe challenges to each of these steps. Here, we present a complete system for effective and efficient similarity search in scientific workflow repositories, based on the Layer Decomposition approach to scientific workflow comparison. Layer Decomposition specifically accounts for the directed dataflow underlying scientific workflows and, compared to other state-of-the-art methods, delivers best results for similarity search at comparably low runtimes. Stacking Layer Decomposition with even faster, structure-agnostic approaches allows us to use proven, off-the-shelf tools for workflow indexing to further reduce runtimes and scale similarity search to sizes of current repositories. •We present a complete system for efficient scientific workflow similarity search.•Workflow indexing integrates with repositories’ existing search—no graphs needed.•Layer Decomposition reranking of candidate workflows ensures high result quality.•We evaluate on a large corpus of workflows with similarity ratings by human experts.•Our system greatly improves previous results in speed and retains superior quality.