{"id":3001,"date":"2021-10-29T13:45:11","date_gmt":"2021-10-29T12:45:11","guid":{"rendered":"https:\/\/nextmovesoftware.com\/blog\/?p=3001"},"modified":"2021-11-01T13:00:30","modified_gmt":"2021-11-01T13:00:30","slug":"smallworld-5-0-faster-smaller-and-easier-to-use","status":"publish","type":"post","link":"https:\/\/nextmovesoftware.com\/blog\/2021\/10\/29\/smallworld-5-0-faster-smaller-and-easier-to-use\/","title":{"rendered":"SmallWorld 5.0: Faster, Smaller and Easier to use"},"content":{"rendered":"\n

SmallWorld<\/a> allows the searching of chemical space by graph edit distance. It works by enumerating and connecting the common subgraphs of chemical structures into a large network. Similar molecules are found by traversing the network using a breath-first-search (BFS)<\/a> to find the shortest path (minimum number of changes) between the molecules. <\/p>\n\n\n\n

The latest database release (2021<\/strong>) contains 675 billion<\/strong> graphs and 9.16 trillion<\/strong> directed connections. To search the database we need efficient techniques to store, access and handle the data. We\u2019ve just released version 5.0 of the SmallWorld search software which has some exciting improvements I want to highlight.<\/p>\n\n\n\n

Faster<\/h2>\n\n\n\n

Searches now run faster thanks to improved data structures, IO scheduling and format changes. <\/p>\n\n\n\n

Compressed Bitset<\/em><\/p>\n\n\n\n

To perform a BFS of the network we need to maintain the set of visited nodes. This was previously accomplished with a binary-tree (std::set<\/strong>) and used ~40 bytes<\/strong> per entry with access times on the order of log N<\/em><\/strong>. We now use a compressed bitmap (inspired by Roaring Bitmaps<\/a>) which uses ~1 byte<\/strong> per entry and has roughly constant time access. We avoid unnecessary calls to malloc<\/strong> by storing entries inline using a C union<\/strong> where possible.<\/p>\n\n\n\n

\"\"<\/a>

A compressed bitset divides values into containers (buckets) and then chooses the most compact representation for that container. An array container is accessed with binary search, small array containers can be stored inline. The bitmap containers are used for dense ranges of the set and use a traditional bitset. <\/figcaption><\/figure>\n\n\n\n

Route Taken<\/em><\/p>\n\n\n\n

To score chemical entries we need to know the route the search took through the network. We can store the route using back-pointers that record where we came from each time a connection is traversed. Unfortunately this uses twice the memory and since our hits are relatively sparse it is wasteful. All we really need for scoring is the Maximum Common Subgraph (MCS) between the query and hit and this can be captured by recording the inflection points of a search. This is much more efficient to store and adds minimal overhead to the traversal.<\/p>\n\n\n\n

\"\"<\/a>

Example route taken during a search. This allows us to know how to transform the molecule on the left to the one on the right in three steps. Adding a linker (-O-), a terminal (-NH2), and finally closing the ring.<\/figcaption><\/figure>\n\n\n\n

IO Stalls<\/em><\/p>\n\n\n\n

Typically when performing IO, a program requests data from a file and then waits for it to be returned. While the storage device is retrieving the data the program can\u2019t do anything and stalls. This is somewhat hidden when reading a file sequentially as the operating system (OS) speculates about what data is needed next. SmallWorld searches do not access data predictably meaning IO operations create a bottleneck. One method of reducing stalls and increasing throughput is with Asynchronous IO (AIO). This allows multiple IO requests to be queued at once and resolved when ready. Linux recently introduced io_uring<\/a> which makes this easier than previous implementations but it requires a very recent kernel version. The method we use to reduce the stalls is to advise the kernel what data we will need before we read it. This is achieved with the madvise<\/strong> and fadvise<\/strong> system calls – a preliminary pass over the data issues the calls and allows the OS to fetch these in the background. This provides a substantial speed up even when using the old database format.<\/p>\n\n\n\n

\"\"<\/a>

Speed comparison of v4.2 (last release) and v5 for selected queries in thousands of traversed edges per second (KTEPS). Times are recorded on a Raid0 array of spinning HDD.<\/figcaption><\/figure>\n\n\n\n

Smaller<\/h2>\n\n\n\n

The number of graphs and connections in the network grows with each release; Novel chemicals are inserted and their sub-graphs enumerated. As the network grows this requires more storage space. Each graph in the SmallWorld network is assigned an id based on its bond and ring count and a unique index (B{b}R{r}.{idx}<\/strong>). The connections are specified as pairs of indexes. Previously we stored the connection data in a compressed-sparse row<\/a> format using packed 5-byte integers (indexes up to 240<\/sup>) this averaged about ~7.2 bytes<\/strong>. Our initial compression approaches focused on bit-packing and VarByte encoding but this was only able to bring us down to ~5.8 bytes <\/strong>average. Using a technique similar to Grabowski and Bieniecki (2014)<\/a> where edges are grouped in blocks, we were able to bring this down to ~3 bytes <\/strong>average – significantly reducing the storage space required.<\/p>\n\n\n\n

\n
\n<\/td>		\nGraphs<\/strong>\n<\/td>\nConnections<\/strong>\n<\/td>\nOld Format<\/strong>\n<\/td>\nNew Format<\/strong>\n<\/td><\/tr>
\n2019<\/strong>\n<\/td>\n230 billion\n<\/td>\n2.75 trillion\n<\/td>\n20.6TB\n<\/td>\n8.1TB\n<\/td><\/tr>
\n2020<\/strong>\n<\/td>\n471 billion\n<\/td>\n6.12 trillion\n<\/td>\n44.6TB\n<\/td>\n18.3TB\n<\/td><\/tr>
\n2021<\/strong>\n<\/td>\n675 billion\n<\/td>\n9.16 trillion\n<\/td>\n66.0TB\n<\/td>\n27.6TB\n<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Not only do the storage requirements decrease but it happens to be more efficient to access the data:<\/p>\n\n\n\n

\"\"<\/a>

Speed comparison of the old vs new format on selected queries in millions of traversed edges per second (MTEPS)<\/figcaption><\/figure>\n\n\n\n

Hardware<\/h2>\n\n\n\n

Storage technology is evolving rapidly and given the new smaller database size we decided to invest in an NVME raid setup providing 56TB<\/strong> of fast storage (max of 7 in stock):<\/p>\n\n\n\n

\"\"
New hardware: 7x 8TB Sabrent Rocket Q NVME Drives<\/a> and HighPoint SSD7540<\/a> <\/figcaption><\/figure>\n\n\n\n

This allows even faster searches and we believe with further algorithm turning, parallelisation and AIO it should be possible to go faster still:<\/p>\n\n\n\n

\"\"<\/a>


Speed comparison of spinning HDD vs NVME Raid0 array. Speed is in millions of traversed edges per second (MTEPS)<\/figcaption><\/figure>\n\n\n\n

Easier to use<\/strong><\/h2>\n\n\n\n

The old storage format was very simple and it was easy to implement a BFS in any programming language. We had implementations in C++, Java, or Python. Decoding the new format is more complex and we decided it was time to provide a unified common API and bindings. A disadvantage of the multiple implementations were some were more advanced than others. Providing a common base allows SmallWorld searches from Python to run almost as fast as C++:<\/p>\n\n\n\n

import pysmallworld\n\ndb = pysmallworld.Db("chembl_29")\n\nnum_hits = 0\nfor hit in db.search("Clc1ccccc1", max_dist=4):\n  print (num_hits, hit.vector, hit.dbref, hit.smiles)\n  num_hits += 1<\/code><\/pre><\/div>\n\n\n\n
One of the new features that comes with the API is the ability to perform a multi-source BFS where hits are reported that are the closest to any of the provided queries:<\/p>\n\n\n\n
import pysmallworld\n\ndb = pysmallworld.Db("chembl_29")\n\nquery = db.new_query()\nquery.add_smiles("Clc1ccccc1")\nquery.add_smiles("Clc1c(C(C)(C)C)cccc1")\nquery.set_max_dist(4)\n\nnum_hits = 0\nfor hit in db.search_query(query):\n  print (num_hits, hit.vector, hit.dbref, hit.smiles)\n  num_hits += 1\n<\/code><\/pre><\/div>\n\n\n\n
SmallWorld v5.0 is now available to download and is better than ever. <\/p>\n\n\n\n
We\u2019re hiring!<\/em><\/strong> Engineers with a passion for cheminformatics and algorithms, head over to our <\/em>Careers<\/em><\/a> page for more info.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
SmallWorld allows the searching of chemical space by graph edit distance. It works by enumerating and connecting the common subgraphs of chemical structures into a large network. Similar molecules are found by traversing the network using a breath-first-search (BFS) to find the shortest path (minimum number of changes) between the molecules.  The latest database release … Continue reading SmallWorld 5.0: Faster, Smaller and Easier to use<\/span><\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/posts\/3001"}],"collection":[{"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/comments?post=3001"}],"version-history":[{"count":9,"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/posts\/3001\/revisions"}],"predecessor-version":[{"id":3023,"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/posts\/3001\/revisions\/3023"}],"wp:attachment":[{"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/media?parent=3001"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/categories?post=3001"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nextmovesoftware.com\/blog\/wp-json\/wp\/v2\/tags?post=3001"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}