<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0"
	xmlns:content="http://purl.org/rss/1.0/modules/content/"
	xmlns:wfw="http://wellformedweb.org/CommentAPI/"
	xmlns:dc="http://purl.org/dc/elements/1.1/"
	xmlns:atom="http://www.w3.org/2005/Atom"
	xmlns:sy="http://purl.org/rss/1.0/modules/syndication/"
	xmlns:slash="http://purl.org/rss/1.0/modules/slash/"
	>

<channel>
	<title>Datablend &#187; redis</title>
	<atom:link href="https://datablend.be/?cat=39&#038;feed=rss2" rel="self" type="application/rss+xml" />
	<link>https://datablend.be</link>
	<description>Big Data Simplified</description>
	<lastBuildDate>Mon, 07 Sep 2015 09:04:17 +0000</lastBuildDate>
	<language>en-US</language>
	<sy:updatePeriod>hourly</sy:updatePeriod>
	<sy:updateFrequency>1</sy:updateFrequency>
	<generator>http://wordpress.org/?v=3.6.1</generator>
		<item>
		<title>Redis and Lua: a NoSQL power-horse</title>
		<link>https://datablend.be/?p=278</link>
		<comments>https://datablend.be/?p=278#comments</comments>
		<pubDate>Tue, 29 Jan 2013 09:59:16 +0000</pubDate>
		<dc:creator>Davy Suvee</dc:creator>
				<category><![CDATA[chemoinformatics]]></category>
		<category><![CDATA[compound comparison]]></category>
		<category><![CDATA[NoSQL]]></category>
		<category><![CDATA[redis]]></category>

		<guid isPermaLink="false">http://datablend22.lin3.nucleus.be/?p=278</guid>
		<description><![CDATA[Recently, I&#8217;ve started implementing a number of Redis-based solutions for a Datablend customer. Redis is frequently referred to as the Swiss Army Knife of NoSQL databases and rightfully deserves that title. At its core, it is an in-memory key-value datastore. Values that are assigned to keys can be &#8216;structured&#8217; through the use of strings, hashes,<p><a href="https://datablend.be/?p=278">Continue Reading →</a></p>]]></description>
				<content:encoded><![CDATA[<p style="text-align: justify;">Recently, I&#8217;ve started implementing a number of Redis-based solutions for a Datablend customer. <a href="http://redis.io" target="_blank">Redis</a> is frequently referred to as the <span class="highlight"><em>Swiss Army Knife</em></span> of NoSQL databases and rightfully deserves that title. At its core, it is an <span class="highlight"><em>in-memory key-value</em></span> datastore. Values that are assigned to keys can be &#8216;structured&#8217; through the use of strings, hashes, lists, sets and sorted sets. The power of these simple data structures, combined with its intuitive API, makes Redis a true power-horse for solving various &#8216;Big Data&#8217;-related problems. To illustrate this point, I reimplemented my MongoDB-based <a href="http://datablend.be/?p=962" target="_blank">molecular similarity search</a> through Redis and its integrated Lua support. As always, the complete source code can be found on the <a target='_blank' href="https://github.com/datablend/redis-compound-comparison">Datablend public GitHub repository</a>.</p>
<p>&nbsp;</p>
<h3>1. Redis &#8216;fingerprint&#8217; data model</h3>
</p>
<p style="text-align: justify;"><span class="highlight">Molecular similarity</span> refers to the <em>similarity</em> of <em>chemical compounds</em> with respect to their structural and/or functional qualities. By calculating molecular similarities, Cheminformatics is able to help in the design of new drugs by screening large databases for potentially interesting chemical compounds. Chemical similarity can be determined through the use of so-called <span class="highlight"><em>fingerprints</em></span> (i.e. linear, substructure chemical patterns of a certain length). Similarity between compounds is identified by calculating the <a href="http://en.wikipedia.org/wiki/Jaccard_index" target='_blank'>Tanimoto coefficient</a>. This computation involves the calculation of <span class="highlight"><em>intersections</em></span> between sets of fingerprints, an operation that is natively supported by Redis.</p>
<p style="text-align: justify;">Our Redis-based data model for storing fingerprints requires three different data-structures:</p>
<ol>
<li>For each <span class="highlight"><em>compound</em></span>, identified by an <span class="highlight"><em>unique key</em></span>, we store its set of fingerprints (where each fingerprint is again identified by an unique key).</li>
<li>For each <span class="highlight"><em>fingerprint</em></span>, identified by an <span class="highlight"><em>unique key</em></span>, we store the set of compounds containing this fingerprint. These fingerprint sets can be conceived as the inverted indexes of the compound sets mentioned above.</li>
<li>For each <span class="highlight"><em>fingerprint</em></span>, we store its number of occurrences through a dedicated <span class="highlight"><em>weight</em>-key</span>.</li>
</ol>
<p>&nbsp;</p>
<p style="text-align: justify;">Fingerprints are calculated by using the, 33 and 35) are sufficient to create both the <span class="highlight"><em>inverted indexes</em></span> (compound->fingerprints and fingerprint->compounds) and incrementing the accompanying <span class="highlight"><em>counters</em></span>.</p>
<script src="https://gist.github.com/4666154.js"></script>
<p>&nbsp;</p>
<h3>2. Finding similar chemical compounds</h3>
<p style="text-align: justify;">For retrieving compounds that satisfy a particular Tanimoto coefficient, we reuse the same principles as outlined in my <a href="http://datablend.be/?p=962" target="_blank">original MongoDB article</a>. The number of round-trips to the Redis datastore is minimised by implementing the algorithm via the <span class="highlight"><em>build-in Lua scripting</em></span> support. We start by retrieving the number of fingerprints of the particular input compound. Based upon that cardinality, we  calculate the <span class="highlight"><em>fingerprints of interest</em></span> (i.e. the min-set of fingerprints that lead us to compounds that are able to satisfy the Tanimoto coefficient). For this, we need to identify the subset of compound fingerprints that occur the least throughout the entire dataset. Redis allows us to perform this query via a single <span class="highlight"><em>sort</em></span>-command; it takes the compound-key as input and sorts the contained fingerprints by employing the value of the external fingerprint weight keys. Out of this sorted set of fingerprints, we <span class="highlight"><em>sub-select the top x fingerprints</em></span> of interest. What a <span class="highlight"><em>powerful</em></span> and <span class="highlight"><em>elegant</em></span> command!</p>
<p style="text-align: justify;">We use the inverted index (fingerprint->compounds) to identify those compounds that are able to satisfy the particular input Tanimoto coefficient. Applying the Redis <span class="highlight"><em>union</em></span>-command upon the calculated set of fingerprint keys returns the set of potential compounds. Once this set has been identified, we calculate similarity by making use of the Redis <span class="highlight"><em>intersect</em></span>-command. Only compounds that satisfy the Tanimoto restriction are returned.</p>
<script src="https://gist.github.com/4667047.js"></script>
<p>&nbsp;</p>
<h3>3. Conclusion</h3>
<p style="text-align: justify;">With 25.000 stored compounds, Redis requires less then 20ms to retrieve compounds that are 70% similar to a particular input compound. Snappier compared to my original MongoDB implementation. In addition, Redis requires less then 1GB of RAM to maintain a live index of the <a href="http://cactus.nci.nih.gov/download/roadmap/">460.000 PubChem compounds</a> that have at least one associated assay. This allows scientist to host a local instance of the compound datastore, effectively eliminating the need for a dedicated (and expensive) compound database setup.</p>
<p></p>]]></content:encoded>
			<wfw:commentRss>https://datablend.be/?feed=rss2&#038;p=278</wfw:commentRss>
		<slash:comments>0</slash:comments>
		</item>
	</channel>
</rss>
