|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r72440 - sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html
From: cpp.cabrera_at_[hidden]
Date: 2011-06-06 16:27:46
Author: alejandro
Date: 2011-06-06 16:27:45 EDT (Mon, 06 Jun 2011)
New Revision: 72440
URL: http://svn.boost.org/trac/boost/changeset/72440
Log:
Design solidified. Achieved table-free page layout! Initial content added: introduction. Needs 5 more sections.
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html | 67 +++++++++++++++++++++++++++++++--------
1 files changed, 52 insertions(+), 15 deletions(-)
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/index.html 2011-06-06 16:27:45 EDT (Mon, 06 Jun 2011)
@@ -7,51 +7,88 @@
<title>Boost.BloomFilter</title>
<style type="text/css">
- .toc ul, .toc li {padding:0; margin:0; list-style:none;}
+ .toc ul, .toc li {padding: 0em; list-style:none;}
.toc ul {margin: 0em 0em 0em 0em;}
+ .toc p {font-weight: bold;}
.copyright {font-style: italic;}
+
+ header {
+ height: 94px;
+ position: relative;
+ font-family: sans;
+ }
+
+ header img {
+ float: left;
+ position: absolute; top: 4px; left: 4px;
+ }
+
+ header p {
+ float: right;
+ text-align: right;
+ width: 75em;
+ padding-top: 1.5em;
+ }
+
+ header p a {
+ font-size: 1.1em;
+ padding-right: 7%;
+ }
+
</style>
</head>
<body>
<header>
<img src="../../../../../boost.png" width=277 height=86 alt="Boost C++ Libraries"/>
+ <p>
+ Home
+ Libraries
+ People
+ FAQ
+ More
+ </p>
</header>
<hr>
-
- <div class="spirit-nav">
- <img src="../../../../../doc/src/images/prev.png"/>
- <img src="../../../../../doc/src/images/up.png"/>
- <img src="../../../../../doc/src/images/home.png"/>
- <img src="../../../../../doc/src/images/next.png"/>
- </div>
<h2 class="title">Boost.BloomFilter</h2>
<h3 class="author">Alejandro Cabrera</h3>
<div class="toc">
+ <p>Table of Contents</p>
<ul>
<li>Introduction</li>
- <li>Tutorial</li>
- <li>Design</li>
- <li>Miscellaneous</li>
- <li>Bibliography</li>
+ <li>Tutorial</li>
+ <li>Design</li>
+ <li>Miscellaneous</li>
+ <li>Reference</li>
+ <li>Bibliography</li>
</ul>
</div>
<p>
<h2 name="introduction">Introduction</h2>
- <p>Some stuff...</p>
+ <p>
+ A Bloom filter is a probabilistic data structures that allows the compact representation of a set of elements. Bloom filters are used where an application can gain a performance advantage by avoiding an expensive lookup. For example, one might use a Bloom filter to ask whether a file may be stored on the network. If the Bloom filter returns false, the network lookup can be skipped. A few known applications of Bloom filters:
<ul>
- <li>Some features...</li>
+ <li>Google BigTable: check whether particular rows/columns exist - improves query performance</li>
+ <li>Google Chrome: speed up Safe Browsing mode.
+ <li>Squid Web Proxy Cache: cache digests, e.g., whether particular URLs are in the cache.</li>
</ul>
- <p>Some more details...</p>
+ </p>
+ <p>
+ Internally, a Bloom filter stores its elements using a bit set with all bits initially set to 0. When an element is to be inserted into the Bloom filter, it is passed to a series of hash functions. The indices generated by the hash functions are all set to 1. When the Bloom filter is queried for an element's set membership, the element is passed through that same set of hash functions. If all the positions given by the hash functions are set to 1, then the element is reported to be in the set.
+ </p>
+ <p>
+ A powerful property of a Bloom filter is that it is capable of representing the universe of items in a given set without generating any false negatives - if the element is in the Bloom filter, the Bloom filter will never report that the element is not contained within. However, a Bloom filter may report false positives, with a given probability based on the interaction between the number of bits the Bloom filter uses for element storage, the number of bits set, and the number of hash functions used.
+ </p>
</p>
<hr>
<footer>
+
<p>
Last revised: <time datetime=2011-06-06>June 6, 2011</time>.
</p>
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