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&rep=rep1&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&rep=rep1&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&source=web&cd=1&ved=0CBsQFjAA&url=http%3A%2F%2Fgsd.di.uminho.pt%2Fmembers%2Fcbm%2Fps%2Fdbloom.pdf&ei=ZH_2TbboIeeu0AH5o4XtDA&usg=AFQjCNFGN0RS1-bUCxZJwUmD0C8cTnllQg&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&rep=rep1&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&rep=rep1&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">