|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r73342 - sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html
From: cpp.cabrera_at_[hidden]
Date: 2011-07-24 19:42:19
Author: alejandro
Date: 2011-07-24 19:42:18 EDT (Sun, 24 Jul 2011)
New Revision: 73342
URL: http://svn.boost.org/trac/boost/changeset/73342
Log:
Added a great deal of content to the bibliography. Divided bibliography into three sections: general sources, Bloom filter variants, and applications. Fixed error in design.html.
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/bibliography.html | 157 +++++++++++++++++++++++++++++++++------
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/design.html | 7 -
2 files changed, 134 insertions(+), 30 deletions(-)
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/bibliography.html
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/design.html
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
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/bibliography.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/bibliography.html 2011-07-24 19:42:18 EDT (Sun, 24 Jul 2011)
@@ -37,45 +37,150 @@
<h2 class="title">Bibliography</h2>
- <div class="citations">
- <ol>
- <li>
- Wikipedia.com. (2011, June). <em>Bloom Filter</em>.
- Retrieved June 8, 2011, from
- <a href="http://en.wikipedia.org/wiki/Bloom_filter">
- http://en.wikipedia.org/wiki/Bloom_filter>
- </li>
- <li>
- www.strchr.com. (2010, November).
- <em>Hash Functions: An Empirical Comparison.</em>
- Retrieved June 8, 2011 from
- <a href="http://www.strchr.com/hash_functions">
- http://www.strchr.com/hash_functions>
- </li>
- <li>
- [Geelnard 2006] Marcus, G..
- <em>Basic Compression Library: Manual</em>. Chp. 4, pp. 12-15.
- <a href="http://bcl.comli.eu/index.php?media=manual">
- http://bcl.comli.eu/index.php?media=manual>
- </li>
- </ol>
- </div>
+ <h3>General Sources</h3>
- <br/>
+ <ol>
+ <li>
+ Wikipedia.com. (2011, June). <em>Bloom Filter</em>.
+ Retrieved June 8, 2011, from
+ <a href="http://en.wikipedia.org/wiki/Bloom_filter">
+ http://en.wikipedia.org/wiki/Bloom_filter>
+ </li>
+ <li>
+ www.strchr.com. (2010, November).
+ <em>Hash Functions: An Empirical Comparison.</em>
+ Retrieved June 8, 2011 from
+ <a href="http://www.strchr.com/hash_functions">
+ http://www.strchr.com/hash_functions>
+ </li>
+ <li>
+ [Geelnard 2006] Marcus, G..
+ <em>Basic Compression Library: Manual</em>. Chp. 4, pp. 12-15.
+ <a href="http://bcl.comli.eu/index.php?media=manual">
+ http://bcl.comli.eu/index.php?media=manual>
+ </li>
+ <li>
+ [P. Bose et al., 2008]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.147.9455&rep=rep1&type=pdf">
+ <em>On the False-Positive Rate of Bloom Filters</em></a>.
+ In <em>Information Processing Letters</em> 2008.
+ Vol. 108, issue 4, pp. 210-213.
+ </li>
+ <li>
+ [D. Guo et al., 2010]
+ <a href="http://repository.ust.hk/dspace/bitstream/1783.1/6538/1/FalseNegative.pdf">
+ <em>False Negative Problem of Counting Bloom Filters</em></a>.
+ In <em>IEEE Transactions on Knowledge and Data
+ Engineering</em> 2010. vol. 22, issue 5, pp. 651-664.
+ </li>
+ </ol>
- <h2 class="title">Future Sources</h2>
+ <h3>Bloom Filter Variants</h3>
<div class="citations">
<ol>
<li>
[Kirsch et al., 2008]
A. Kirsch, M. Mitzenmacher.
- <em>Less Hashing, Same Performance: Building a Better Bloom Filter</em>.
+ <a href="http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf">
+ <em>Less Hashing, Same Performance: Building a Better Bloom Filter</em>.
+ </a>
In <em>Random Structures and Algorithms</em>, pages 187-219.
</li>
+ <li>
+ [Pagh et al., 2005]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.4131&rep=rep1&type=pdf">
+ <em>An Optimal Bloom Filter Replacement</em></a>.
+ In <em>Symposium on Discrete Algorithms</em>, 2005.
+ </li>
+ <li>
+ [M. Mitzenmacher, 2002]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.119.6895&rep=rep1&type=pdf">
+ <em>Compressed Bloom Filters</em></a>.
+ In <em>IEEE/ACM Transactions on Networking</em>,
+ vol. 10, issue 5, 2002.
+ </li>
+ <li>
+ [F. Bonomi et al., 2006]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.6328&rep=rep1&type=pdf">
+ <em>An Improved Construction for Counting Bloom Filters</em></a>.
+ In <em>Lecture Notes in Computer Science</em>, vol. 4168,
+ pp. 684-695.
+ </li>
+ <li>
+ [J. Bruck et al., 2006]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.152.8571&rep=rep1&type=pdf">
+ <em>Weighted Bloom Filter</em></a>.
+ In <em>IEEE International Symposium on Information Theory</em>,
+ pp. 2304-2308.
+ </li>
+ <li>
+ [P. S. Almeida et al., 2006]
+ <a href="http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf">
+ <em>Scalable Bloom Filters</em></a>.
+ In <em>Information Processing Letters</em>,
+ vol. 101, issue 6, pp. 255-261.
+ </li>
+ <li>
+ [S. Cohen et al., 2003]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.5769&rep=rep1&type=pdf">
+ <em>Spectral Bloom Filters</em></a>.
+ In <em>SIGMOD</em> 2003.
+ </li>
+ <li>
+ [B. Chazelle et al., 2004]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.4154&rep=rep1&type=pdf">
+ <em>The Bloomier Filter: an Efficient Data Structure for
+ Static Support Lookup Tables</em></a>.
+ In <em>Symposium on Discrete Algorithms</em> 2004.
+ </li>
+ <li>
+ [C. E. Rothenberg et al., 2010]
+ <a href="http://arxiv.org/pdf/1005.0352">
+ <em>The Deletable Bloom Filter: a New Member of the Bloom Filter Family</em></a>.
+ In <em>IEEE Communications Letters</em> 2010.
+ vol. 14, issue 6, pp. 557-559.
+ </li>
+ <li>
+ [M. Ahmadi et al., 2008]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.148.9754&rep=rep1&type=pdf">
+ <em>A Memory-Optimized Bloom Filter Using an
+ Additional Hashing Function</em></a>.
+ In <em>Global Telecommunications Conference</em> 2008.
+ </li>
</ol>
</div>
+ <h3>Applications</h3>
+ <ol>
+ <li>
+ [M. Särelä et al., 2008]
+ <a href="http://wwwse.inf.tu-dresden.de/zib/publ/doc/jerzak2008bloom.pdf">
+ <em>Bloom Filter Based Routing for Content-Based Publish/Subscribe</em></a>.
+ In <em>Distributed Event-Based Systems</em> 2008.
+ </li>
+ <li>
+ [J. Taylor, 2009]
+ <a href="http://soar.wichita.edu/dspace/bitstream/10057/2312/1/GRASP5_25.pdf">
+ <em>Data Caching in Ad-Hoc Networks Using Bloom Filters</em></a>.
+ In <em>Symposium on Graduate Research and Scholarly Projects</em> 2009.
+ </li>
+ <li>
+ [A. Broder et al., 2004]
+ <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.9672&rep=rep1&type=pdf">
+ <em>Network Applications of Bloom Filters: a Survey</em></a>.
+ In <em>Internet Mathematics</em>, vol. 1, issue 4, pp. 485-509.
+ </li>
+ <li>
+ Computer Science Department of University of North
+ Carolina. (2005, Spring). <em>An Examination of Bloom Filters
+ and Their Applications</em>.
+ Retrieved July 24, 2011, from
+ <a href="http://cs.unc.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf">
+ http://cs.unc.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf>
+ </li>
+ </ol>
+
<hr/>
<div class="spirit-nav">
<a accesskey="p" href="testing.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-07-24 19:42:18 EDT (Sun, 24 Jul 2011)
@@ -127,7 +127,7 @@
</p>
<a name="default_hash"></a>
- <h4>Default Hash Functions</h4>
+ <h3>Default Hash Functions</h3>
<p>
To make the Bloom filter easier to use, the HashFunctions template parameter
has a default value. This way, if the user wishes to use a Bloom filter for
@@ -142,7 +142,7 @@
</div>
<a name="c++0x"></a>
- <h4>C++0x Considerations</h4>
+ <h3>C++0x Considerations</h3>
<p>
Currently, this implementation uses boost::mpl::vector, boost::mpl::size, and boost::mpl::at_c for managing the hash function set. When C++0x is widely implemented, it may be beneficial to implement hash function set management in terms of std::tuple, std::tuple_size, and std::tuple_element. This will have to be investigated.
</p>
@@ -154,7 +154,7 @@
</p>
<a name="future"></a>
- <h4>Future Directions</h4>
+ <h3>Future Directions</h3>
<p>
There are a few planned features that have not yet made it to the Bloom filter package:
</p>
@@ -173,7 +173,6 @@
<ul>
<li><del>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></del></li>
- </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>