Tool Search:

"Past, Present, and Future"

Ahmed Awan, Tyler Collins, Michelle Savage

Johns Hopkins University

September 15, 2022

Flaws With the Old Tool Search

• Poor ordering of search Results

​

• The tool you searched for was often randomly placed inside of the list of returned tools

​

• Didn’t allow for some more advanced filtering and searching options

​

​

Tool Search GCC

Cameron Hyde

Tyler Collins

Michelle Savage

Ahmed Awan

The Backend Search: What is Whoosh?

Whoosh is a python library of classes and functions for indexing text and then searching the index.

​

Essentially, Woosh allows us to develop a custom search engine for searching the tools loaded on a Galaxy instance.

Previous Search Index Schema

The first step in building the backend search is defining an index schema of all of the fields that should be searchable such as title or content.

Populating the Search Index

​

We then populate our index by looping through all of the available tools on a galaxy instance.

How Woosh searches the index

​

• Parse the Query and create a Query Object.
• Compare the Query Object against the created Document Index.
• Score the Results with some algorithm.
• Return a Result Object ordered by Score.

Parsing the Query

Galaxy was using a custom n-gram implementation to help parse the query after it was converted to lowercase.

​

Galaxy was also configured to default to an ‘or’ search instead of an ‘and’ search.

​

Galaxy also added a wild card search to the query.

Old Search Implementation

Galaxy would then sum the score of all the fields. The field scores were calculated by the scoring algorithm BM25F * by some boosting value that was defined to mark the importance of each field.

The BM25 Algorithm

​

=

• qi is the i^th query term
• The IDF component of our formula measures how often a term occurs in all of the documents and “penalizes” terms that are common.
• fieldLen/avgFieldLen can be thought of as as how long a document is relative to the average document length in the index.
• If b is bigger, the effects of the length of the document compared to the average length are more amplified.
• f(qi,D) boils down to the more times the query term(s) occur a document, the higher its score will be.
• K1 limits how much a single query term can affect the score of a given document.

What we did to Improve the Search

Changed Scoring Algorithm

• The BM25F algorithm was a poor choice for many of the short length fields in our index, such as name or id.

​

• As a result the scoring method was modified for those fields to switch to a simple frequency scoring algorithm instead.

​

• The BM25F algorithm is still being used in help text and had its parameters slightly modified to better fit galaxy use cases.

Fixed Boosting

• The old boosting method had minimal effect and didn’t succeed in differentiating field importance.
• The implemented method just modified the b term.
• Instead a new multiplicative boosting method was created that actually weights the fields differently.

​

• If b is bigger, the effects of the length of the document compared to the average length are more amplified.

​

Implemented Improved N-gram Search

• The previous custom N-gram search in Galaxy was relying on the use of wild-cards and wasn’t a true n-gram search.
• We went and implemented a woosh version of the Ngram Tokenizer and implemented that instead to parse the name field in the index.
• We also made it configurable with a min and max n-gram size for any admins to easily be able to adjust.

Implemented Woosh Analyzers

• An analyzer is a function or callable class that takes a unicode string and returns a generator of tokens.
• This lets us modify and transform the query string for each individual field that we define in our schema.
• For example it can allow us to apply a stemming filter to remove suffixes from words in a search query to help better find matches.

Fixed id Search

Additionally we fixed the ID field to actually be searchable now.

Changed how Config Params are Accessed

We also added all of the boost parameters and ngram sizes and other changes as customizable options to the config_schema.yml.

Results After Changes

Why refactor (or clean) code?

Why (any of below)

• readability (1+ devs)
• persistent bugs (6+ months)
• code alignment

credit: https://www.flickr.com/photos/mercer52/16141913875

API-to-Front End

Code Conventions

​

There are only two hard things in Computer Science: cache invalidation and naming things.

​

​

-- Phil Karlton

principal developer at Xerox PARC, Digital, Silicon Graphics, and Netscape (Karlton.org)

​

​

Code Conventions for Clarity*

​

Nice to Haves:

• Consistent variable structure: (camelCase OR under_score, not both)
• Object-oriented variable naming: ("data" = "tools", "results", "tags")
• Static object naming ("inputField" = "query", "date", "category")
• Consistent naming and ordering within methods (f[x,y] = p[x,y], z[x,y])
• Full words, no abbreviations (non-native language devs)
• Long variables/methods/functions (characters or lines) take priority over brevity** (large development teams)

​

____

* Unless a developer is working entirely on their own, the code must be easily understood for other developers to understand, maintain, and extend.

** sometimes there is a naming limitation on the coding language/tech so brevity in naming must be adhered to

Code Conventions for Clarity*

Before

After

SOLID coding principles

Key Takeaways (from code file top-to-bottom):

• Single-responsibility principle
• Concise code (methods/functions no more than 7 lines)
• Libraries are fine for limited use
• Open–closed principle
• Wrapped methods in Classes for easier sharing between variables within code object
• Liskov substitution principle
• Seamless connectivity (ToolboxWorkflow.vue)
• Interface segregation principle
• Constants held in database/API or listed at top of files
• Dependency inversion principle
• Naming variables using objects, nounces

https://en.wikipedia.org/wiki/SOLID

Front End Test Coverage *

* Integration coverage extremely helpful for more complex feature too.

Advanced Tool Search

• In 22.05, Advanced search was added to the history panel.
• Following the same pattern, the need arose for an advanced tool search.

Advanced Tool Search

Implemented and merged in dev, as a dropdown, advanced menu similar to the history:

Advanced Tool Search

• Filter not applied to the tool panel itself.
• Results show up in the center panel in a rich formatted b-table instead.
• Table shows tool name, short description, panel section, workflow compatibility and tool target (local/not local).

Advanced Tool Search

Clicking on a tool name may show tool help text/information.

Advanced Tool Search

​

• All tools retrieved from api/tools.
• Does not provide enough variables to query.
• Could be handy to have tool input/output data type as a filter in the future.

Special Thanks

​

• Cameron Hyde
• Dannon Baker
• Björn Grüning
• Aysam Guerler
• everyone else who added input!