[Boost-commit] svn:boost r73235 - sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut

Subject: [Boost-commit] svn:boost r73235 - sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut
From: cpp.cabrera_at_[hidden]
Date: 2011-07-19 02:38:58

Author: alejandro
Date: 2011-07-19 02:38:57 EDT (Tue, 19 Jul 2011)
New Revision: 73235
URL: http://svn.boost.org/trac/boost/changeset/73235

Log:
Completed the module on false positive rates.
Text files modified: 
   sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/false_positive.html |    23 +++++++++++++++++++++++                 
   1 files changed, 23 insertions(+), 0 deletions(-)

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/false_positive.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/false_positive.html	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/false_positive.html	2011-07-19 02:38:57 EDT (Tue, 19 Jul 2011)
@@ -40,6 +40,29 @@
 
     <h1 class="title">Controlling the False Positive Rate</h1>
 
+    <p>
+      A false positive occurs when a query on an element not in the Bloom filter 
+      returns true. The probability of such an event occurring is determined by
+      the bit capacity (m) of the Bloom filter, the number of hashers (k) used,
+      and the number of bits set (n). An approximate formula is:      
+    </p>
+
+    <div class="math">
+      1 - [1 - 1/m]<sup>kn</sup> &#8773; (1 - e<sup>-kn/m</sup>)<sup>k</sup>
+    </div>
+
+    <p>
+      The forumla above provides a close approximation of the actual false postive 
+      rate. In order to find the best combination of parameters for your application,
+      it is always best to benchmark.
+    </p>
+
+    <p>
+      For more details on the false positive rate of a Bloom filter, see
+      <a href="http://people.scs.carleton.ca/~kranakis/Papers/TR-07-07.pdf">
+      here.</a>
+    </p>
+
     <hr/>
     <div class="spirit-nav">
       <a accesskey="p" href="quick.html">