Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r72591 - sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html
From: cpp.cabrera_at_[hidden]
Date: 2011-06-14 17:19:41


Author: alejandro
Date: 2011-06-14 17:19:41 EDT (Tue, 14 Jun 2011)
New Revision: 72591
URL: http://svn.boost.org/trac/boost/changeset/72591

Log:
Added various links to future directions section.
Text files modified:
   sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/design.html | 35 +++++++++++++++++++++++++++--------
   1 files changed, 27 insertions(+), 8 deletions(-)

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/design.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/design.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/design.html 2011-06-14 17:19:41 EDT (Tue, 14 Jun 2011)
@@ -98,20 +98,39 @@
       There are a few planned features that have not yet made it to the Bloom filter package:
     </p>
     <ul>
- <li>[De]Compression policy support via template policy class</li>
+ <li>[De]Compression policy support via template policy class:
+ <ul>
+ <li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.119.6895&amp;rep=rep1&amp;type=pdf">
+ Compressed Bloom Filters.</a> M. Mitzenmacher. IEEE/ACM TON. 2002.
+ </li>
+ <li><a href="http://bcl.comli.eu/index.php?media=manual">
+ Basic Compression Library Manual. </a> Chp. 4, pp. 12-15.
+ </li>
+ </ul>
+ </li>
       <li>Bloom filter variations implemented as separate classes:
       <ul>
- <li>Counting Bloom filter (deletion support)</li>
- <li>Scaling Bloom filter (constant false positive rate)</li>
- <li>Two-hash Bloom filter (uses two-hash functions to generate k hash values)</li>
- <li>Bloomier filters (?)</li>
+ <li>Counting Bloom filter (deletion support): <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.96.6789&amp;rep=rep1&amp;type=pdf">
+ Summary Cache. Fan et al. ACM SIGCOMM. 1998.
+ </a>
+ </li>
+ <li>Scaling Bloom filter (constant false positive rate): <a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CBsQFjAA&amp;url=http%3A%2F%2Fgsd.di.uminho.pt%2Fmembers%2Fcbm%2Fps%2Fdbloom.pdf&amp;ei=ZH_2TbboIeeu0AH5o4XtDA&amp;usg=AFQjCNFGN0RS1-bUCxZJwUmD0C8cTnllQg&amp;sig2=__OvO8j0bdnj5gDH0xt4mw">
+ Scalable Bloom Filter. </a>Almeida et al. Elsevier. 2007.
+ </li>
+ <li>Two hash function Bloom filter (uses two hash functions to generate k hash values):
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.2442&amp;rep=rep1&amp;type=pdf">
+ Less Hashing, Same Performance: Building a Better Bloom Filter. Kirsch et al. Springer. 2006.
+ </a>
+ </li>
+ <li>Bloomier filters: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.4154&amp;rep=rep1&amp;type=pdf">
+ The Bloomier Filter. </a>Chazelle et al. ACM SODA. 2004.
+ </li>
       </ul>
       </li>
- <li>Union/intersection of Bloom filters of the same size and same number/type of hash functions differing only by type (types must be convertible).</li>
       <li>Parallel execution of hashing, especially useful for large (>1MB, >32 hash functions) Bloom filters. Such a feature should have a smart, defaulting mechanism that enables parallelism once Size/HashFunction parameters exceed a certain threshold, if parallelism is available on the given platform.</li>
     </ul>
     <p>
- The design space for Bloom filter-like data structures is immense. Given feedback in the future, this section is likely to grow. Please send suggestions to <a href="mailto:cpp.cabrera_at_[hidden]">Alejandro Cabrera</a>
+ The design space for Bloom filter-like data structures is immense. Given feedback in the future, this section is likely to grow. Please send suggestions to <a href="mailto:cpp.cabrera_at_[hidden]">Alejandro Cabrera</a>.
     </p>
     <hr/>
     <div class="spirit-nav">
@@ -128,7 +147,7 @@
 
     <footer>
       <p>
- Last revised: <time datetime="2011-06-06">June 6, 2011</time>.
+ Last revised: <time datetime="2011-06-13">June 13, 2011</time>.
       </p>
 
       <p class="copyright">


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk