Lossy Count Algorithm

<h2 id="algorithm">Algorithm</h2>
<p>The general algorithm is as follows<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<ul><li>Step 1: Divide the incoming data stream into buckets of width 
  
    
      
        w
        =
        1
        
          /
        
        ϵ
      
    
    {\displaystyle w=1/\epsilon }
  
, where 
  
    
      
        ϵ
      
    
    {\displaystyle \epsilon }
  
 is mentioned by user as the error bound (along with minimum support threshold = 
  
    
      
        σ
      
    
    {\displaystyle \sigma }
  
).</li>
<li>Step 2: Increment the frequency count of each item according to the new bucket values. After each bucket, decrement all counters by 1.</li>
<li>Step 3: Repeat – Update counters and after each bucket, decrement all counters by 1.</li></ul>

<ul><li>Motwani, R; Manku, G.S (2002). "Approximate frequency counts over data streams". <i>VLDB '02 Proceedings of the 28th International Conference on Very Large Data Bases</i>: 346–357.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Han, Jiawei. (2006). Data mining : concepts and techniques. Kamber, Micheline. (2nd ed.). Amsterdam: Elsevier. ISBN 978-0-08-047558-5. OCLC 143252170. <a href="978-0-08-047558-5" target="_blank">978-0-08-047558-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Lossy Count Algorithm open-in-new

Lossy Count Algorithm