<!DOCTYPE html> <html class="writer-html5" lang="en" > <head> <meta charset="utf-8" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" /> <meta name="viewport" content="width=device-width, initial-scale=1.0" /> <title>Morris — Bouncer 0.0.1 documentation</title> <link rel="stylesheet" href="_static/pygments.css" type="text/css" /> <link rel="stylesheet" href="_static/css/theme.css" type="text/css" /> <!--[if lt IE 9]> <script src="_static/js/html5shiv.min.js"></script> <![endif]--> <script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script> <script src="_static/jquery.js"></script> <script src="_static/underscore.js"></script> <script src="_static/doctools.js"></script> <script async="async" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> <script src="_static/js/theme.js"></script> <link rel="index" title="Index" href="genindex.html" /> <link rel="search" title="Search" href="search.html" /> <link rel="next" title="Sketches" href="Sketches.html" /> <link rel="prev" title="Counters" href="Counters.html" /> </head> <body class="wy-body-for-nav"> <div class="wy-grid-for-nav"> <nav data-toggle="wy-nav-shift" class="wy-nav-side"> <div class="wy-side-scroll"> <div class="wy-side-nav-search" > <a href="index.html" class="icon icon-home"> Bouncer </a> <div role="search"> <form id="rtd-search-form" class="wy-form" action="search.html" method="get"> <input type="text" name="q" placeholder="Search docs" /> <input type="hidden" name="check_keywords" value="yes" /> <input type="hidden" name="area" value="default" /> </form> </div> </div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu"> <p class="caption" role="heading"><span class="caption-text">Classes:</span></p> <ul class="current"> <li class="toctree-l1 current"><a class="reference internal" href="table_of_contents.html">Bouncer</a><ul class="current"> <li class="toctree-l2 current"><a class="reference internal" href="Counters.html">Counters</a><ul class="current"> <li class="toctree-l3 current"><a class="current reference internal" href="#">Morris</a></li> </ul> </li> <li class="toctree-l2"><a class="reference internal" href="Sketches.html">Sketches</a></li> </ul> </li> </ul> </div> </div> </nav> <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" > <i data-toggle="wy-nav-top" class="fa fa-bars"></i> <a href="index.html">Bouncer</a> </nav> <div class="wy-nav-content"> <div class="rst-content"> <div role="navigation" aria-label="Page navigation"> <ul class="wy-breadcrumbs"> <li><a href="index.html" class="icon icon-home"></a> »</li> <li><a href="table_of_contents.html">Bouncer</a> »</li> <li><a href="Counters.html">Counters</a> »</li> <li>Morris</li> <li class="wy-breadcrumbs-aside"> <a href="_sources/Morris.rst.txt" rel="nofollow"> View page source</a> </li> </ul> <hr/> </div> <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article"> <div itemprop="articleBody"> <section id="morris"> <h1>Morris<a class="headerlink" href="#morris" title="Permalink to this headline"></a></h1> <p>The Morris counter is one of the first streaming algorithms ever discovered. For a stream of <span class="math notranslate nohighlight">\(n\)</span> tokens, the Morris counter seeks to approximate the number of items in the stream in only <span class="math notranslate nohighlight">\(O(\log n)\)</span> bits of memory. Because the Morris counter acts as an unbiased estimator, we can approximate <span class="math notranslate nohighlight">\(n\)</span> up to value <span class="math notranslate nohighlight">\(2^{256}\)</span>, using just one byte of memory for the counter. The algorithm works strictly on a vanilla model, meaning it can only record event insertions and does not allow for deletions.</p> <dl class="py class"> <dt class="sig sig-object py" id="bouncer.counters.Morris"> <em class="property"><span class="pre">class</span> </em><span class="sig-prename descclassname"><span class="pre">bouncer.counters.</span></span><span class="sig-name descname"><span class="pre">Morris</span></span><span class="sig-paren">(</span><em class="sig-param"><span class="n"><span class="pre">version</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">epsilon</span></span></em>, <em class="sig-param"><span class="n"><span class="pre">delta</span></span></em><span class="sig-paren">)</span><a class="headerlink" href="#bouncer.counters.Morris" title="Permalink to this definition"></a></dt> <dd><p><strong>Parameters</strong></p> <blockquote> <div><dl class="simple"> <dt><strong>version : {“Morris”, “Morris+”, “Morris++”}, default=”Morris”</strong></dt><dd><p>Specify the type of Morris counter.</p> <ul class="simple"> <li><p><code class="docutils literal notranslate"><span class="pre">"Morris"</span></code>: One 8-bit Morris counter.</p></li> <li><p>“Morris+”: <span class="math notranslate nohighlight">\(s = \lceil \frac{1}{\epsilon^2 \delta} \rceil\)</span> “Morris” counters.</p></li> <li><p>“Morris++”: <span class="math notranslate nohighlight">\(t = \lceil \frac{18}{\log \delta} \rceil\)</span> “Morris+” counters, where <span class="math notranslate nohighlight">\(s =\lceil \frac{3}{ 2 \epsilon^2} \rceil\)</span>.</p></li> </ul> </dd> <dt><strong>epsilon : float, range=(0,1)</strong></dt><dd><p>Accepted error range of true count. Only implemented for ‘Morris+’, ‘Morris++’.</p> </dd> <dt><strong>delta : float, range=(0,1)</strong></dt><dd><p>Probability of exceeding epsilon error range. Only implemented for ‘Morris+’, ‘Morris++’.</p> </dd> </dl> </div></blockquote> <p><strong>Attributes</strong></p> <blockquote> <div><dl class="simple"> <dt><strong>version : str</strong></dt><dd><p>Type of Morris object.</p> </dd> <dt><strong>epsilon : float</strong></dt><dd><p>Epsilon of Morris object.</p> </dd> <dt><strong>delta : float</strong></dt><dd><p>Delta of Morris object.</p> </dd> <dt><strong>raw_counts : list</strong></dt><dd><p>List with count(s) of the Morris object.</p> </dd> <dt><strong>shape : tuple (n_morris+, n_morris)</strong></dt><dd><p>Shape of raw_counts. For “Morris++”, returns <span class="math notranslate nohighlight">\((t,s)\)</span>, for “Morris+”, <span class="math notranslate nohighlight">\((1,s)\)</span>, and for “Morris”, <span class="math notranslate nohighlight">\((1,)\)</span>.</p> </dd> </dl> </div></blockquote> <p><strong>Methods</strong></p> <blockquote> <div><dl class="py function"> <dt class="sig sig-object py" id="bouncer.counters.Morris.update"> <span class="sig-name descname"><span class="pre">update</span></span><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="headerlink" href="#bouncer.counters.Morris.update" title="Permalink to this definition"></a></dt> <dd><p>Updates count(s) <span class="math notranslate nohighlight">\(x\)</span> w.p. <span class="math notranslate nohighlight">\(\frac{1}{2^x}\)</span>.</p> </dd></dl> <dl class="py function"> <dt class="sig sig-object py" id="bouncer.counters.Morris.output"> <span class="sig-name descname"><span class="pre">output</span></span><span class="sig-paren">(</span><span class="sig-paren">)</span><a class="headerlink" href="#bouncer.counters.Morris.output" title="Permalink to this definition"></a></dt> <dd><ul class="simple"> <li><p><code class="docutils literal notranslate"><span class="pre">"Morris"</span></code>: Returns <span class="math notranslate nohighlight">\(2^x - 1\)</span>.</p></li> <li><p>“Morris+”: Returns the mean of <span class="math notranslate nohighlight">\(s = \lceil \frac{1}{\epsilon^2 \delta} \rceil\)</span> “Morris” outputs.</p></li> <li><p>“Morris++”: Returns median of <span class="math notranslate nohighlight">\(t = \lceil \frac{18}{\log \delta} \rceil\)</span> “Morris+” outputs, where <span class="math notranslate nohighlight">\(s =\lceil \frac{3}{ 2 \epsilon^2} \rceil\)</span>.</p></li> </ul> </dd></dl> </div></blockquote> <p><strong>Examples</strong></p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">>></span> <span class="kn">from</span> <span class="nn">bouncer.counters</span> <span class="kn">import</span> <span class="n">Morris</span> <span class="o">>></span> <span class="o">>></span> <span class="n">m</span> <span class="o">=</span> <span class="n">Morris</span><span class="p">(</span><span class="n">version</span><span class="o">=</span><span class="s2">"Morris"</span><span class="p">)</span> <span class="o">>></span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">10</span><span class="p">):</span> <span class="o">...</span> <span class="n">m</span><span class="o">.</span><span class="n">update</span><span class="p">()</span> <span class="o">...</span> <span class="o">>></span> <span class="o">>></span> <span class="n">m</span><span class="o">.</span><span class="n">output</span><span class="p">()</span> <span class="o">>></span> <span class="mi">15</span> <span class="o">>></span> <span class="n">m</span><span class="o">.</span><span class="n">shape</span> <span class="o">>></span> <span class="p">(</span><span class="mi">1</span><span class="p">,)</span> <span class="o">>></span> <span class="n">m</span><span class="o">.</span><span class="n">raw_counts</span> <span class="o">>></span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">>></span> <span class="o">>></span> <span class="n">m1</span> <span class="o">=</span> <span class="n">Morris</span><span class="p">(</span><span class="n">version</span><span class="o">=</span><span class="s2">"Morris+"</span><span class="p">,</span> <span class="n">epsilon</span> <span class="o">=</span> <span class="mf">.2</span><span class="p">,</span> <span class="n">delta</span> <span class="o">=</span> <span class="mf">.5</span><span class="p">)</span> <span class="o">>></span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">10</span><span class="p">):</span> <span class="o">...</span> <span class="n">m1</span><span class="o">.</span><span class="n">update</span><span class="p">()</span> <span class="o">...</span> <span class="o">>></span> <span class="o">>></span> <span class="n">m1</span><span class="o">.</span><span class="n">output</span><span class="p">()</span> <span class="o">>></span> <span class="mf">7.639999866485596</span> <span class="o">>></span> <span class="n">m1</span><span class="o">.</span><span class="n">shape</span> <span class="o">>></span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">25</span><span class="p">)</span> <span class="o">>></span> <span class="n">m1</span><span class="o">.</span><span class="n">raw_counts</span> <span class="o">>></span> <span class="p">[</span><span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">]</span> <span class="o">>></span> <span class="o">>></span> <span class="n">m2</span> <span class="o">=</span> <span class="n">Morris</span><span class="p">(</span><span class="n">version</span><span class="o">=</span><span class="s2">"Morris++"</span><span class="p">,</span> <span class="n">epsilon</span> <span class="o">=</span> <span class="mf">.2</span><span class="p">,</span> <span class="n">delta</span> <span class="o">=</span> <span class="mf">.5</span><span class="p">)</span> <span class="o">>></span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">10</span><span class="p">):</span> <span class="o">...</span> <span class="n">m2</span><span class="o">.</span><span class="n">update</span><span class="p">()</span> <span class="o">...</span> <span class="o">>></span> <span class="o">>></span> <span class="n">m2</span><span class="o">.</span><span class="n">output</span><span class="p">()</span> <span class="o">>></span> <span class="mf">10.894737243652344</span> <span class="o">>></span> <span class="n">m2</span><span class="o">.</span><span class="n">shape</span> <span class="o">>></span> <span class="p">(</span><span class="mi">13</span><span class="p">,</span> <span class="mi">38</span><span class="p">)</span> </pre></div> </div> </dd></dl> <div class="admonition note"> <p class="admonition-title">Note</p> <p>This implementation requires 26 bytes of overhead per instantiation. This is due to the overhead of PyObject_HEAD and other python fields required for all python object allocations.</p> </div> <p>Analysis and proof of correctness of the bounds can be found in Jelani Nelson’s lecture notes under chapter 2.1.2: <a class="reference external" href="https://www.sketchingbigdata.org/fall20/lec/notes.pdf">https://www.sketchingbigdata.org/fall20/lec/notes.pdf</a></p> </section> </div> </div> <footer><div class="rst-footer-buttons" role="navigation" aria-label="Footer"> <a href="Counters.html" class="btn btn-neutral float-left" title="Counters" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a> <a href="Sketches.html" class="btn btn-neutral float-right" title="Sketches" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right" aria-hidden="true"></span></a> </div> <hr/> <div role="contentinfo"> <p>© Copyright 2022, Ben Badnani.</p> </div> Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. </footer> </div> </div> </section> </div> <script> jQuery(function () { SphinxRtdTheme.Navigation.enable(true); }); </script> </body> </html>