You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by gg...@apache.org on 2020/01/26 17:17:01 UTC
[commons-collections] branch master updated: Bloom filter
documentation (#128)
This is an automated email from the ASF dual-hosted git repository.
ggregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git
The following commit(s) were added to refs/heads/master by this push:
new 5639a5d Bloom filter documentation (#128)
5639a5d is described below
commit 5639a5d7903374b922dcb70a9973b76430ec6a8d
Author: Claude Warren <cl...@xenei.com>
AuthorDate: Sun Jan 26 17:16:54 2020 +0000
Bloom filter documentation (#128)
* Added initial bloom filter code. Added changed lang3 dependency from
test to compile in pom.xml
* added tests + made recommended changes.
* Updated documentation
* refactored ProtoBloomFilter added tests.
* Cleand up code and added tests
* Added CountingBloomFilter
* Fixed CountingBloomFilter issues
Fixed checkstyle and bug report issues
* Initial bloom filter collections checkin
* Added unit tests
* fixed test cases
* Extract BloomFilter as an interface
* added missing license info
* fixed Jacoco errors
* fixed names for so build picks up tests
* cleaned up Jacoco report for BloomNestedCollection
* removed unused code
* cleaned up and reformatted
* added javadoc
fixed issue with BloomNestedCollection detecting duplicates in an edge
case.
* fixed candidate testing bug
* Cleand up niggling report issues.
* fixed javadoc errors
* fixed javadoc for java 13 issue
* Second set of fixes.
* "package private for testing" for methods and properties.
* In "Builder":
** Field "hashes" made "final"
* removes some "Serializable" implementations.
* "StandardBloomFilter" made non non "final" fields final and changed
"final protected" to "final private".
* removed transient fields
* made Package name singular
* added javadocs for private and protected fields and methods.
* Occurrences of "bloom" replaced with "Bloom"
* removed checkstyle and findbugs exclusions
* Fixed method and class names
* Documentation updates
* Fixed checkstyle isses
Added BloomFilterConfiguration functions for estimation.
* added .checkstyle to eclipse ignore section.
* renamed test classes to match main class names
* Updated the documentation.
* Implemented requested changes. Part of COLLECTIONS-728
Changed remaining "get" comments to "gets" etc.
Added final where possible and reasonable.
renamed enum Change to CHANGE
fixed missing javadoc links and missed name changes.
fixed ProtoBloomFilter hashCode
renamed CollectionStatistics to BloomCollectionStatistics
renamed CollectionConfiguration to BloomCollectionConfiguration
renamed BloomCollectionStatistics.getTxnCount() to getTransactionCount()
* Added final set of constructors and tests for them.
Cleaned up issues from Gilles Sadowski review
* fixes for Gilles Sadowski issues in BloomCollectionStatistics
* Update javadoc
* renamed match() -> matches() and inverseMatch() -> inverseMatches()
This follows the pattern set with the Object.equals() method name.
* added isFull() method to check if a bloom filter is full.
* Changed gate from StandardBloomFilter to BloomFilter
* renamed BloomCollectionX -> BloomFilterGatedX
specifically:
BloomCollectionConfiguration -> BloomFilterGatedConfiguraiton
BloomCollectionStatistics -> BloomFilterGatedStatistics
* Made the StandardBloomFilter(BitSet) constructor public
* removed extraneous build() methods from ProtoBloomFilter.Factory
* Added Use cases
* Initial cut
* changes for interface
* Changed to Hasher implementation
* Added missing files and removed Shape from some BloomFilter calls
* Added @since 4.5 tags
* fixed javadoc
* fixed PMD errors
* Added tests and fixed sign extension issues
* changed to Byte constant
* made BloomFilter.verify*() non final
* Added remove(Hasher) for completeness
* Replaced private implementation of MurmurHash3 with commons-codec
* fixed typo
* Removed Hasher.Factory added HashFunction interface
* removed Usage.md
* made commons-codec dependency optional
* Improved performance of Iterator.
* renamed instance variable "md" as messageDigest.
* updated javadoc
* renamed Iter to Iterator and removed unused imports
* removed unused imports
* Made instance variables final.
Also fixed MD5 constructor to throw IllegalStateException if MD5 algo
can not be found.
* removed unused imports
* Updated javadoc.
* Added HashFunctionIdentity to replace HashFunctionName
Added test cases, updated java doc.
Renamed function implementations to reflect actual function.
Added comparators for HashFunctionIdentity
* fixed naming issues
* Updated javadoc
* fixed checkstyle issue
* Removed link that was causing problems in java 11+ javadoc
* changed HashFunctionIdentity.getProcess() to getProcessType()
* changed HashFunctionIdentity.getProcess() to getProcessType()
* Added package documentation
* Added BloomFilter interface and removed unnecessary methods
* updated tests and fixed issues
* Moved set operations to separate class and updated tests
* fixed FindBugs, PMD and Checkstyle errors
* fixed javadocs
* Added SetOperations and tests
* Added javadocs indicating optional commons-codec required
* Added another cosine test
* Updated to commons-codec 1.14
* fixed typos
* moved Hasher to o.a.c.c.b.hasher package
* extracted Shape.java and moved to o.a.c.c.b.hasher package
* Added javadoc and removed unused imports in testing code
* Added isEmpty() method to Hasher
* initial documentation
* updated to latest mathjax
* Fixed typographical issues
---
src/site/resources/css/LaTeXML.css | 399 ++++++++++++
src/site/resources/css/references.css | 24 +
src/site/xdoc/bloomFilters.xml | 1137 +++++++++++++++++++++++++++++++++
src/site/xdoc/userguide.xml | 1 +
4 files changed, 1561 insertions(+)
diff --git a/src/site/resources/css/LaTeXML.css b/src/site/resources/css/LaTeXML.css
new file mode 100644
index 0000000..6ba272a
--- /dev/null
+++ b/src/site/resources/css/LaTeXML.css
@@ -0,0 +1,399 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+ /*======================================================================
+ Core CSS for LaTeXML documents converted to (X)HTML */
+/* Generic Page layout */
+.ltx_page_header,
+.ltx_page_footer { font-size:0.8em; }
+.ltx_page_header *[rel~="prev"],
+.ltx_page_footer *[rel~="prev"] { float:left; }
+.ltx_page_header *[rel~="up"],
+.ltx_page_footer *[rel~="up"] { display:block; text-align:center; }
+.ltx_page_header *[rel~="next"],
+.ltx_page_footer *[rel~="next"] { float:right; }
+/* What was I trying for here; need more selective rule!
+.ltx_page_header .ltx_ref,
+.ltx_page_footer .ltx_ref {
+ margin:0 1em; }
+*/
+.ltx_page_header li {
+ padding:0.1em 0.2em 0.1em 1em;}
+
+/* Main content */
+.ltx_page_content { clear:both; }
+.ltx_page_header { border-bottom:1px solid; margin-bottom:5px; }
+.ltx_page_footer { clear:both; border-top:1px solid; margin-top:5px; }
+
+.ltx_page_header:after,
+.ltx_page_footer:after,
+.ltx_page_content:after {
+ content:"."; display:block; height:0; clear:both; visibility:hidden; }
+.ltx_page_footer:before {
+ content:"."; display:block; height:0; clear:both; visibility:hidden; }
+
+.ltx_page_logo { font-size:80%; margin-top: 5px; clear:both; float:right; }
+.ltx_page_logo a { font-variant: small-caps; }
+.ltx_page_logo img { vertical-align:-3px; }
+
+/* if shown */
+.ltx_page_navbar li { white-space:nowrap; display:block; overflow:hidden; }
+/* If ref got turned into span, it's "this section"*/
+.ltx_page_navbar li span.ltx_ref { white-space:normal; overflow:visible; }
+
+/* Ought to be easily removable/overridable? */
+.ltx_pagination.ltx_role_newpage { height:2em; }
+/*======================================================================
+ Document Structure; Titles & Frontmatter */
+
+/* undo bold here to remove the browser's native h# styling,
+ at let all other styles override it (with more specific rules)*/
+.ltx_title { font-size:100%; font-weight:normal; }
+
+/* Hack to simulate run-in! put class="ltx_runin" on a title or tag
+ for it to run-into the following text. */
+.ltx_runin { display:inline; }
+.ltx_runin:after { content:" "; }
+.ltx_runin + .ltx_para,
+.ltx_runin + .ltx_para p,
+.ltx_runin + p { display:inline; }
+
+.ltx_outdent { margin-left: -2em; }
+
+/* .ltx_chapter_title, etc should be in ltx-article.css etc.
+ */
+.ltx_page_main { margin:0px; padding:1em 3em 1em 2em; }
+.ltx_tocentry { list-style-type:none; }
+
+/* support for common author block layouts.*/
+/* add class ltx_authors_1line to get authors in single line
+ with pop-up affiliation, etc. */
+.ltx_authors_1line .ltx_creator,
+.ltx_authors_1line .ltx_author_before,
+.ltx_authors_1line .ltx_author_after { display:inline;}
+.ltx_authors_1line .ltx_author_notes { display:inline-block; }
+.ltx_authors_1line .ltx_author_notes:before { content:"*"; color:blue;}
+.ltx_authors_1line .ltx_author_notes span { display:none; }
+.ltx_authors_1line .ltx_author_notes:hover span {
+ display:block; position:absolute; z-index:10;
+ background:white; text-align:left;
+ border: 1px solid black; border-radius: 0 5px 5px 5px; box-shadow: 5px 5px 10px gray; }
+
+/* add class=ltx_authors_multiline to get authors & affliations on separate lines*/
+.ltx_authors_multiline .ltx_creator,
+.ltx_authors_multiline .ltx_author_before,
+.ltx_authors_multiline .ltx_author_after,
+.ltx_authors_multiline .ltx_author_notes,
+.ltx_authors_multiline .ltx_author_notes .ltx_contact {
+ display:block; }
+
+/*======================================================================
+ Para level */
+.ltx_float {
+ margin: 1ex 3em 1ex 3em; }
+td.ltx_subfigure,
+td.ltx_subtable,
+td.ltx_subfloat { width:50%; }
+/* theorems, figure, tables, floats captions.. */
+/*======================================================================
+ Blocks, Lists, Floats */
+.ltx_p,
+.ltx_quote,
+.ltx_block,
+.ltx_para {
+ display: block; }
+
+/* alignment within blocks */
+.ltx_align_left { text-align:left; }
+.ltx_align_right { text-align:right; }
+.ltx_align_center { text-align:center; }
+.ltx_align_justify { text-align:justify; }
+.ltx_align_top { vertical-align:top; }
+.ltx_align_bottom { vertical-align:bottom; }
+.ltx_align_middle { vertical-align:middle; }
+.ltx_align_baseline { vertical-align:baseline; }
+
+.ltx_align_floatleft { float:left; }
+.ltx_align_floatright { float:right; }
+
+.ltx_td.ltx_align_left, .ltx_th.ltx_align_left,
+.ltx_td.ltx_align_right, .ltx_th.ltx_align_right,
+.ltx_td.ltx_align_center, .ltx_th.ltx_align_center { white-space:nowrap; }
+.ltx_td.ltx_align_left.ltx_wrap, .ltx_th.ltx_align_left.ltx_wrap,
+.ltx_td.ltx_align_right.ltx_wrap, .ltx_th.ltx_align_right.ltx_wrap,
+.ltx_td.ltx_align_center.ltx_wrap, .ltx_th.ltx_align_center.ltx_wrap,
+.ltx_td.ltx_align_justify, .ltx_th.ltx_align_justify { white-space:normal; }
+
+.ltx_tabular .ltx_tabular { width:100%; }
+.ltx_inline-block { display:inline-block; }
+
+/* equations in non-aligned mode (not normally used) */
+.ltx_eqn_div { display:block; width:95%; text-align:center; }
+
+/* equations in aligned mode (aligning tags, etc as well as equations) */
+.ltx_eqn_table { display:table; width:100%; border-collapse:collapse; }
+.ltx_eqn_row { display:table-row; }
+.ltx_eqn_cell { display:table-cell; width:auto; }
+
+/* Padding between column pairs in ams align */
+table.ltx_eqn_align tr.ltx_equation td.ltx_align_left + td.ltx_align_right,
+table.ltx_eqn_align tr.ltx_equation td.ltx_align_left + td.ltx_align_center,
+table.ltx_eqn_align tr.ltx_equation td.ltx_align_center + td.ltx_align_right,
+table.ltx_eqn_align tr.ltx_equation td.ltx_align_center + td.ltx_align_center { padding-left:3em; }
+table.ltx_eqn_eqnarray tr.ltx_eqn_lefteqn + tr td.ltx_align_right { min-width:2em; }
+
+.ltx_eqn_eqno { max-width:0em; overflow:visible; white-space: nowrap; }
+.ltx_eqn_eqno.ltx_align_right .ltx_tag { float:right; }
+
+.ltx_eqn_center_padleft,
+.ltx_eqn_center_padright { width:50%; min-width:2em;}
+.ltx_eqn_left_padleft,
+.ltx_eqn_right_padright { min-width:2em; }
+.ltx_eqn_left_padright,
+.ltx_eqn_right_padleft { width:100%; }
+
+/* Various lists */
+.ltx_itemize,
+.ltx_enumerate,
+.ltx_description {
+ display:block; }
+.ltx_itemize .ltx_item,
+.ltx_enumerate .ltx_item {
+ display: list-item; }
+
+/* Position the tag to look like a normal item bullet. */
+li.ltx_item > .ltx_tag {
+ display:inline-block; margin-left:-1.5em; min-width:1.5em;
+ text-align:right; }
+.ltx_item .ltx_tag + .ltx_para,
+.ltx_item .ltx_tag + .ltx_para .ltx_p { display:inline; }
+
+/* NOTE: Need to try harder to get runin appearance? */
+dl.ltx_description dt { margin-right:0.5em; float:left;
+ font-weight:bold; font-size:95%; }
+dl.ltx_description dd { margin-left:5em; }
+dl.ltx_description dl.ltx_description dd { margin-left:3em; }
+
+/* Theorems */
+.ltx_theorem {margin:1em 0em 1em 0em; }
+.ltx_title_theorem { font-size:100%; }
+
+/* Bibliographies */
+.ltx_bibliography dt { margin-right:0.5em; float:left; }
+.ltx_bibliography dd { margin-left:3em; }
+/*.ltx_biblist { list-style-type:none; }*/
+.ltx_bibitem { list-style-type:none; }
+.ltx_bibitem .ltx_tag { font-weight:bold; margin-left:-2em; width:3em; }
+/*.bibitem-tag + div { display:inline; }*/
+.ltx_bib_title { font-style:italic; }
+.ltx_bib_article .bib-title { font-style:normal !important; }
+.ltx_bib_journal { font-style:italic; }
+.ltx_bib_volume { font-weight:bold; }
+
+/* Indices */
+.ltx_indexlist li { list-style-type:none; }
+.ltx_indexlist { margin-left:1em; padding-left:1em;}
+
+/* Listings */
+.ltx_listing {
+ display:block;
+ margin: 1ex 3em 1ex 0em;
+ overflow-x:auto;
+ text-align: left; }
+.ltx_float .ltx_listing {
+ margin: 0; }
+.ltx_listingline { white-space:nowrap; min-height:1em; }
+.ltx_lst_numbers_left .ltx_listingline .ltx_tag {
+ background-color:transparent;
+ margin-left:-3em; width:2.5em;
+ position:absolute;
+ text-align:right; }
+.ltx_lst_numbers_right .ltx_listingline .ltx_tag {
+ background-color:transparent;
+ width:2.5em;
+ position:absolute; right:3em;
+ text-align:right; }
+/*
+ position:absolute; left:0em;
+ max-width:0em; text-align:right; }
+*/
+.ltx_parbox {text-indent:0em; }
+
+/* NOTE that it is CRITICAL to put position:relative outside & absolute inside!!
+ I wish I understood why!
+ Outer box establishes resulting size, neutralizes any outer positioning, etc;
+ inner establishes position of stuff to be rotated */
+.ltx_transformed_outer {
+ position:relative; bottom:0pt;left:0pt;
+ overflow:visible; }
+.ltx_transformed_inner {
+ display:block;
+ position:absolute;bottom:0pt;left:0pt; }
+.ltx_transformed_inner > .ltx_p {text-indent:0em; margin:0; padding:0; }
+/* If simulating a table (html5), try to get rowspan to work...sorta? */
+span.ltx_rowspan { position:absolute; top:0; bottom:0; }
+
+/* by default, p doesn't indent */
+.ltx_p { text-indent:0em; white-space:normal; }
+/* explicit control of indentation (on ltx_para) */
+.ltx_indent > .ltx_p:first-child { text-indent:2em!important; }
+.ltx_noindent > .ltx_p:first-child { text-indent:0em!important; }
+
+/*======================================================================
+ Columns */
+.ltx_page_column1 {
+ width:44%; float:left; } /* IE uses % of wrong container*/
+.ltx_page_column2 {
+ width:44%; float:right; }
+.ltx_page_columns > .ltx_page_column1 {
+ width:48%; float:left; }
+.ltx_page_columns > .ltx_page_column2 {
+ width:48%; float:right; }
+.ltx_page_columns:after {
+ content:"."; display:block; height:0; clear:both; visibility:hidden; }
+
+/*======================================================================
+ Borders and such */
+.ltx_tabular { display:inline-table; border-collapse:collapse; }
+.ltx_tabular.ltx_centering { display:table; }
+.ltx_thead,
+.ltx_tfoot,
+.ltx_tbody { display:table-row-group; }
+.ltx_tr { display:table-row; }
+.ltx_td,
+.ltx_th { display:table-cell; }
+
+.ltx_framed { border:1px solid black;}
+.ltx_tabular .ltx_td,
+.ltx_tabular .ltx_th { padding:0.1em 0.5em; }
+/* regular lines */
+.ltx_border_t { border-top:1px solid black; }
+.ltx_border_r { border-right:1px solid black; }
+.ltx_border_b { border-bottom:1px solid black; }
+.ltx_border_l { border-left:1px solid black; }
+/* double lines */
+.ltx_border_tt { border-top:3px double black; }
+.ltx_border_rr { border-right:3px double black; }
+.ltx_border_bb { border-bottom:3px double black; }
+.ltx_border_ll { border-left:3px double black; }
+/* Light lines */
+.ltx_border_T { border-top:1px solid gray; }
+.ltx_border_R { border-right:1px solid gray; }
+.ltx_border_B { border-bottom:1px solid gray; }
+.ltx_border_L { border-left:1px solid gray; }
+/* Framing */
+.ltx_framed_rectangle { border-style:solid; border-width:1px; }
+.ltx_framed_top { border-top-style:solid; border-top-width:1px; }
+.ltx_framed_left { border-left-style:solid; border-left-width:1px; }
+.ltx_framed_right { border-right-style:solid; border-right-width:1px; }
+.ltx_framed_bottom,
+.ltx_framed_underline { border-bottom-style:solid; border-bottom-width:1px; }
+.ltx_framed_topbottom { border-top-style:solid; border-top-width:1px;
+ border-bottom-style:solid; border-bottom-width:1px; }
+.ltx_framed_leftright { border-left-style:solid; border-left-width:1px;
+ border-right-style:solid; border-right-width:1px; }
+
+/*======================================================================
+ Misc */
+/* .ltx_verbatim*/
+.ltx_verbatim { text-align:left; }
+/*======================================================================
+ Meta stuff, footnotes */
+.ltx_note_content { display:none; }
+/*right:5%; */
+.ltx_note_content {
+ max-width: 70%; font-size:90%; left:15%;
+ text-align:left;
+ background-color: white;
+ padding: 0.5em 1em 0.5em 1.5em;
+ border: 1px solid black; border-radius: 0 5px 5px 5px; box-shadow: 5px 5px 10px gray; }
+.ltx_note_mark { color:blue; }
+.ltx_note_type { font-weight: bold; }
+.ltx_note { display:inline-block; text-indent:0; } /* So we establish containing block */
+.ltx_note_content .ltx_note_mark { position:absolute; left:0.2em; top:-0.1em; }
+.ltx_note:hover .ltx_note_content,
+.ltx_note .ltx_note_content:hover {
+ display:block; position:absolute; z-index:10; }
+
+.ltx_ERROR { color:red; }
+.ltx_rdf { display:none; }
+.ltx_missing { color:red;}
+.ltx_nounicode { color:red; }
+/*======================================================================
+ SVG (pgf/tikz ?) basics */
+
+/* Stuff appearing in svg:foreignObject */
+.ltx_svg_fog foreignObject { margin:0; padding:0; overflow:visible; }
+.ltx_svg_fog foreignObject > p { margin:0; padding:0; display:block; }
+/*.ltx_svg_fog foreignObject > p { margin:0; padding:0; display:block; white-space:nowrap; }*/
+
+/*======================================================================
+ Low-level Basics */
+/* Note that LaTeX(ML)'s font model doesn't map quite exactly to CSS's */
+/* Font Families => font-family */
+.ltx_font_serif { font-family: serif; }
+.ltx_font_sansserif { font-family: sans-serif; }
+.ltx_font_typewriter { font-family: monospace; }
+/* dingbats should be converted to unicode? */
+/* Math font families handled within math: script, symbol, fraktur, blackboard ? */
+/* Font Series => font-weight */
+.ltx_font_bold { font-weight: bold; }
+.ltx_font_medium { font-weight: normal; }
+/* Font Shapes => font-style or font-variant */
+.ltx_font_italic { font-style: italic; font-variant:normal; }
+.ltx_font_upright { font-style: normal; font-variant:normal; }
+.ltx_font_slanted { font-style: oblique; font-variant:normal; }
+.ltx_font_smallcaps { font-variant: small-caps; font-style:normal; }
+.ltx_font_oldstyle { font-variant: oldstyle-nums; /* experimental css3 ? Doesn't seem to work!*/
+ font-style:normal;
+ -moz-font-feature-settings: "onum";
+ -ms-font-feature-settings: "onum";
+ -webkit-font-feature-settings: "onum";
+ font-variant-numeric: oldstyle-nums; }
+.ltx_font_mathcaligraphic { font-family: "Lucida Calligraphy", "Zapf Chancery","URW Chancery L"; }
+/*
+
+.ltx_font_mathscript { ? }
+*/
+cite { font-style: normal; }
+
+.ltx_red { color:red; }
+/*.ltx_centering { text-align:center; margin:auto; }*/
+/*.ltx_inline-block.ltx_centering,*/
+/* Hmm.... is this right in general? */
+.ltx_centering { display:block; margin:auto; text-align:center; }
+
+/* Dubious stuff */
+.ltx_hflipped {
+ display:inline-block;
+ -moz-transform: scaleX(-1);
+ -o-transform: scaleX(-1);
+ -webkit-transform: scaleX(-1);
+ transform: scaleX(-1);
+ filter: FlipH;
+ -ms-fliter: "FlipH"; }
+.ltx_vflipped {
+ display:inline-block;
+ -moz-transform: scaleY(-1);
+ -o-transform: scaleY(-1);
+ -webkit-transform: scaleY(-1);
+ transform: scaleY(-1);
+ filter: FlipV;
+ -ms-fliter: "FlipV"; }
+
+/* .ltx_phantom handled in xslt */
+
diff --git a/src/site/resources/css/references.css b/src/site/resources/css/references.css
new file mode 100644
index 0000000..6039e17
--- /dev/null
+++ b/src/site/resources/css/references.css
@@ -0,0 +1,24 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+div.references { display: table }
+
+div.references div { display: table-row}
+
+span.refName { float:left; font-weight:bold}
+span.refBody { display:table-cell; padding-left: 1%;}
\ No newline at end of file
diff --git a/src/site/xdoc/bloomFilters.xml b/src/site/xdoc/bloomFilters.xml
new file mode 100644
index 0000000..ce1b9fb
--- /dev/null
+++ b/src/site/xdoc/bloomFilters.xml
@@ -0,0 +1,1137 @@
+<?xml version="1.0"?>
+<!-- Licensed to the Apache Software Foundation (ASF) under one or more contributor
+ license agreements. See the NOTICE file distributed with this work for additional
+ information regarding copyright ownership. The ASF licenses this file to
+ You under the Apache License, Version 2.0 (the "License"); you may not use
+ this file except in compliance with the License. You may obtain a copy of
+ the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required
+ by applicable law or agreed to in writing, software distributed under the
+ License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS
+ OF ANY KIND, either express or implied. See the License for the specific
+ language governing permissions and limitations under the License. -->
+
+<document>
+
+ <properties>
+ <title>Bloom filters</title>
+ <author email="dev@commons.apache.org">Commons Documentation Team</author>
+ </properties>
+
+ <head>
+ <link rel="stylesheet" href="./css/LaTeXML.css" type="text/css" />
+ <link rel="stylesheet" href="./css/references.css"
+ type="text/css" />
+ <script type="text/javascript"
+ src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.6/MathJax.js?config=TeX-AMS-MML_HTMLorMML" />
+ </head>
+
+ <body>
+ <section name='Contents'>
+ <ol>
+ <li>
+ <a href="#S1" title="1 Introducing Bloom filters">
+ Introducing Bloom filters
+ </a>
+ <ol>
+ <li>
+ <a href="#S1.SS1" title="1.1 Understanding Bloom filters">
+ Understanding Bloom filters
+ </a>
+ </li>
+ <li>
+ <a href="#S1.SS2" title="1.2 Defining a Bloom filter">
+ Defining a Bloom filter
+ </a>
+ </li>
+ <li>
+ <a href="#S1.SS3" title="1.3 Constructing a Bloom filter">
+ Constructing a Bloom filter
+ </a>
+ </li>
+ </ol>
+ </li>
+ <li>
+ <a href="#S2" title="2. Exploring the Classes">
+ Exploring the Classes
+ </a>
+ <ol>
+ <li>
+ <a href="#S2.SS1"
+ title="2.1 Exploring the HashFunctionIdentity and HashFunction">
+ Exploring the HashFunctionIdentity and HashFunction
+ </a>
+ </li>
+ <li>
+ <a href="#S2.SS2" title="2.2 Exploring the Shape">
+ Exploring the Shape
+ </a>
+ </li>
+ <li>
+ <a href="#S2.SS3" title="2.3 Exploring the Hasher">
+ Exploring the Hasher
+ </a>
+ </li>
+ <li>
+ <a href="#S2.SS4" title="2.4 Exploring the BloomFilter">
+ Exploring the BloomFilter
+ </a>
+ </li>
+ <li>
+ <a href="#S2.SS5"
+ title="2.5 Why Hasher, Shape and BloomFilter?">
+ Why Hasher, Shape and BloomFilter?
+ </a>
+ </li>
+ <li>
+ <a href="#S2.SS6" title="2.6 Build your own BloomFilter">
+ Build your own BloomFilter
+ </a>
+ </li>
+ </ol>
+ </li>
+ <li>
+ <a href="#S3" title="3 Examples">
+ Examples
+ </a>
+ <ol>
+ <li>
+ <a href="#S3.SS1"
+ title="3.1 How to use a Bloom filter as a gatekeeper">
+ Example: How to use a Bloom filter as a gatekeeper
+ </a>
+ </li>
+ <li>
+ <a href="#S3.SS2" title="3.2 Data sharding">
+ Example: Data sharding
+ </a>
+ </li>
+ <li>
+ <a href="#S3.SS3" title="3.3 Future directions">
+ Future directions
+ </a>
+ </li>
+ </ol>
+ </li>
+ <li>
+ <a href="#S4" title="4 References">
+ References
+ </a>
+ </li>
+ </ol>
+ </section>
+
+
+ <section id="S1" name="1. Introducing Bloom filters">
+
+ <subsection id="S1.SS1" name="1.1 Understanding Bloom filters">
+ <p>
+ Bloom filters were introduced to Apache
+ commons-collections in
+ version 4.5. A Bloom filter:
+ </p>
+ <ul>
+ <li>
+ Is a probabilistic data structure defined by Burton Bloom in
+ 1970 <cite>[<a href='#Bloom'>Bloom</a>]</cite>;
+ </li>
+ <li>
+ Can be considered as a bit vector representing a set of
+ objects;
+ </li>
+ <li>
+ Is constructed by hashing data multiple times;
+ </li>
+ <li>
+ Identifies where things are
+ <b>not</b>
+ ;
+ </li>
+ <li>
+ Will yield false positives but
+ <b>never</b>
+ false negatives.
+ </li>
+ <li>Is typically used where hash table solutions are
+ too
+ memory
+ intensive and false positives can be addressed;
+ for example
+ a gating
+ function to a longer operation (e.g.
+ determine if a
+ database lookup
+ should be made);
+ </li>
+ </ul>
+ </subsection>
+
+ <subsection id="S1.SS2" name="1.2 Defining a Bloom filter">
+
+ <p>Bloom filters are constrained by: the number of
+ elements in the
+ set, the number of hash functions, the number
+ of bits in the
+ vector,
+ and the probability of false positives.
+ </p>
+ <ul>
+ <li>
+ \(p\)
+ - is the probability of false positives,
+ </li>
+ <li>
+ \(n\)
+ - is the number of elements in the set represented by the
+ Bloom
+ filter,
+ </li>
+ <li>
+ \(m\)
+ - is the number of bits, and
+ </li>
+ <li>
+ \(k\)
+ - is the number of hash functions.
+ </li>
+ </ul>
+ <p>
+ Mitzenmacher and Upfal <cite>[<a href='#Mitzenmacher'>Mitzenmacher</a>]</cite>
+ have shown that the relationship between these properties is:
+ \(p =
+ (1- e^{-kn/m})^k\)
+
+ </p>
+
+ <p>
+ Thomas Hurst provides a good calculator <cite>[<a href='#Hurst'>Hurst</a>]</cite>
+ where the interplay between these values can be explored.
+ </p>
+
+ </subsection>
+ <subsection id="S1.SS3" name="1.3 Constructing a Bloom filter">
+
+ <p>
+ A simple Bloom filter is constructed by hashing an object
+ \(k\)
+ times, and using each hash value to turn on a single bit in a
+ bit
+ vector comprising
+ \(m\)
+ bits.
+ </p>
+
+ <div id="algorithm1" class="ltx_float">
+ <div class="ltx_listing ltx_lst_numbers_left ltx_listing">
+ <div class="ltx_listingline">
+ <span class="ltx_text ltx_font_bold">Result:</span>
+ A populated bit vector
+ </div>
+ <div class="ltx_listingline"> byte[][] buffers // the list of buffers to hash
+ </div>
+ <div class="ltx_listingline"> bit[m] bitBuffer;
+ </div>
+ <div class="ltx_listingline">
+ <span class="ltx_text ltx_font_bold">for</span>
+
+ <em class="ltx_emph ltx_font_italic">buffer in buffers</em>
+
+ <span class="ltx_text ltx_font_bold">do</span>
+ </div>
+ <div class="ltx_listingline">
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+
+ <span class="ltx_text ltx_font_bold">for</span>
+
+ <em class="ltx_emph ltx_font_italic">i=1 to k</em>
+
+ <span class="ltx_text ltx_font_bold">do</span>
+ </div>
+ <div class="ltx_listingline">
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+ long h = hash( buffer, i );
+ </div>
+ <div class="ltx_listingline">
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+ int bitIdx = h mod m;
+ </div>
+ <div class="ltx_listingline">
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+ bitBuffer[bitIdx] = 1;
+ </div>
+ <div class="ltx_listingline">
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+
+ </div>
+ <div class="ltx_listingline">
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+ end for
+ </div>
+ <div class="ltx_listingline">
+
+ <span class="ltx_rule"
+ style="width:1px;height:100%;background:black;display:inline-block;"> </span>
+
+ </div>
+ <div class="ltx_listingline"> end for
+ </div>
+ <div class="ltx_listingline" />
+
+ </div>
+ <div>
+ <span class="ltx_tag ltx_tag_float">
+ <span class="ltx_text ltx_font_bold">Algorithm 1</span>
+ </span>
+ How to construct a Bloom filter
+ </div>
+ </div>
+
+
+ <p>Building a bloom filter with the Apache
+ Commons-Collections
+ implementation looks like:
+ </p>
+ <source><![CDATA[
+// select a hash function
+HashFunction hFunc = new Murmur128x86Cyclic();
+// define the shape - 7 items. 1 in 1000 probability of collisions
+Shape shape = new Shape ( hFunc , 7, 1.0/1000);
+// create a hasher.
+DynamicHasher hasher = new DynamicHasher.Builder( hFunc )
+ .with( "banana" ).with( "apple" ).with( "pear" ).build();
+// create the bloom filter
+BloomFilter filter = new BitSetBloomFilter ( hasher , shape ); ]]></source>
+
+
+ <p>This looks more complex than the simple Hadoop Bloom
+ filters.
+ Creating the same filter using the Hadoop library look
+ like:
+ </p>
+ <source><![CDATA[
+//define the filter
+BloomFilter hadoopBloomFilter = new BloomFilter (1 _000 , 7, Hash.MURMUR_HASH );
+// add the fruits
+hadoopBloomFilter.add( new Key( "banana".getBytes() ) );
+hadoopBloomFilter.add( new Key( "apple".getBytes() ) );
+hadoopBloomFilter.add( new Key( "pear".getBytes () ) ); ]]></source>
+
+ <p>
+ However, the Commons Collection Bloom filter library is
+ designed to
+ meet
+ <b>most</b>
+ Bloom filter use cases. Covering the wide variety of use cases
+ means that the library provides more options and therefore
+ appears
+ more complex. Any application that wants a simple,
+ consistent,
+ cross
+ platform Bloom filter with a tested
+ implementation can build
+ it very
+ quickly from the Commons
+ Collections Bloom filter library.
+ </p>
+
+ </subsection>
+ </section>
+ <section id="S2" name="2. Exploring the Classes">
+
+ <p>The Commons Collections Bloom filter library has five (5) major
+ components.
+ </p>
+ <ol>
+ <li>
+ <code>HashFunctionIdentity</code>
+ - An interface that defines a hash function.
+ </li>
+ <li>
+ <code>HashFunction</code>
+ -
+ An interface that extends
+ <code>HashFunctionIdentity</code>
+ to include a the hash function implementation. The hash
+ function
+ converts a
+ <code>byte[]</code>
+ into a
+ <code>long</code>
+ value using a seed.
+ </li>
+ <li>
+ <code>Hasher</code>
+ - A class that, when provided with a
+ <code>Shape</code>
+ , converts one
+ or more
+ <code>byte[]</code>
+ into an
+ <code>iterator<int></code>
+ representing
+ the bits that are enabled in the Bloom filter.
+ </li>
+ <li>
+ <code>Shape</code>
+ - A class that describes the
+ shape of the Bloom filter. The shape is
+ defined by:
+ <ul>
+ <li>
+ <code>HashFunctionIdentity</code>
+ </li>
+ <li>
+ The probability of false positives (
+ \(p\)
+ )
+ </li>
+ <li>
+ The number of elements in the set represented by the Bloom filter
+ (
+ \(n\)
+ )
+ </li>
+ <li>
+ The number of bits (
+ \(m\)
+ )
+ </li>
+ <li>
+ The number of hash functions (
+ \(k\)
+ )
+ </li>
+ </ul>
+ </li>
+ <li>
+ <code>BloomFilter</code>
+ - An interface that defines the standard functions that a Bloom
+ filter must
+ provide. Implementations generally take a
+ <code>Hasher</code>
+ and a
+ <code>Shape</code>
+ and converts the
+ <code>iterator<int></code>
+ from the
+ <code>Hasher</code>
+ and preserves them in an internal representation.
+ </li>
+ </ol>
+ <subsection id="S2.SS1"
+ name="2.1 Exploring the HashFunctionIdentity
+ and HashFunction">
+
+ <p>
+ The
+ <code>HashFunctionIdentity</code>
+ is an interface that defines three (3) basic attributes of a
+ <code>HashFunction</code>
+ :
+ </p>
+
+ <ul>
+ <li>
+ The common hash function
+ name. This is a value like
+ <b>MD5</b>
+ or
+ <b>Murmur3-128-x86</b>
+ </li>
+ <li>
+ The signedness of the calculation. When a
+ <code>byte[]</code>
+ is interpreted as a numerical value is it assumed to be signed or
+ unsigned?
+ </li>
+ <li>
+ The process type. In a traditional Bloom filter
+ calculation the
+ hash function is called multiple times with different seeds.
+ This
+ technique is called iterative hashing. However Kirsch and
+ Mitzenmacher <cite>[<a href='#kirsch'>kirsch</a>]</cite>
+ have shown that it is possible to more
+ quickly generate the
+ necessary values by utilizing two (2) values from
+ the
+ hashing. This
+ is called cyclic hashing.
+ </li>
+ </ul>
+
+ <p>
+ The
+ <code>HashFunctionIdentity</code>
+ is used in situations
+ where the attributes of the
+ <code>HashFunction</code>
+ are required but
+ the implementation is not. For example, a Bloom
+ filter need only know
+ what
+ the attributes of the
+ <code>HashFunction</code>
+ that generated the bits
+ was, it does not require the implementation.
+ </p>
+
+ <p>
+ The
+ <code>HashFunctionIdentity</code>
+ also has a signature created
+ by hashing the string produced by:
+ <code>String.format( "%s-%s-%s", getName(),
+ getSignedness(),getProcess() ).getBytes( "UTF-8" )
+ </code>
+ with a seed of
+ 0 (zero). The signature is used in quick comparison
+ checks to ensure
+ function
+ compatibility.
+ </p>
+
+ <p>
+ The
+ <code>HashFunction</code>
+ is an interface that extends
+ <code>HashFunctionIdentity</code>
+ with an method to access the hash function implementation.
+ <code>HashFunction</code>
+ implementations are often used where the
+ <code>HashFunctionIdentity</code>
+ is required as they are the only provided implementations of
+ <code>HashFunctionIdentity</code>
+ .
+ </p>
+
+ <p>
+ <code>HashFunction</code>
+ implementations include:
+ </p>
+ <ul>
+ <li>MD5Cyclic
+ - MD5 hash used in a cyclic manner.
+ </li>
+ <li>Murmur128x86Cyclic
+ - Murmur3 128-bit x86 hash implementation
+ used in a cyclic manner.
+ </li>
+ <li>Murmur32x86Iterative - Murmur3 32-bit x86 hash implementation
+ used in an iterative manner.
+ </li>
+ <li>ObjectsHashIterative - Java
+ Objects hash used in an iterative
+ manner.
+ </li>
+ </ul>
+
+ <p>
+ Additional
+ <code>HashFunction</code>
+ implementations
+ can be created to support the hashing strategies
+ often found in
+ bioinformatics
+ where k-mer sequences are indexed into
+ Bloom filters. In some cases the
+ data
+ about the k-mer sequence is
+ used as the seed value for the hash.
+ </p>
+
+
+ </subsection>
+
+ <subsection id="S2.SS2" name="2.2 Exploring the Shape">
+
+ <p>
+ As noted earlier the
+ <code>Shape</code>
+ describes the shape of the resulting Bloom filter. The constructor
+ for
+ <code>Shape</code>
+ always takes a
+ <code>HashFunctionIdentity</code>
+ as well
+ as many of the other Shape properties necessary to solve
+ \(p = (1- e^{-kn/m})^k\). These combinations are:
+ </p>
+
+ <ul>
+ <li>
+ The probability of collisions (
+ \(p\)
+ ), the
+ number of bits (
+ \(m\)
+ ), and the number of hash functions (
+ \(k\)
+ ).
+ </li>
+ <li>
+ The number of elements (
+ \(n\)
+ ), and
+ the probability of collisions (
+ \(p\)
+ ).
+ </li>
+ <li>
+ The number of elements (
+ \(n\)
+ ), number of bits (
+ \(m\)
+ ), and
+ number of hash functions (
+ \(k\)
+ ).
+ </li>
+ </ul>
+ </subsection>
+
+ <subsection id="S2.SS3" name="2.3 Exploring the Hasher">
+
+ <p>
+ The
+ <code>Hasher</code>
+ converts converts one or more
+ <code>byte[]</code>
+ into an
+ <code>iterator<int></code>
+ representing the bits that
+ are enabled in the Bloom filter. The bits
+ indexes are in the range [0,
+ \(m\)
+ -1]. The Hasher is, in a sense, a primitive Bloom filter. There are
+ two implementations of Hasher provided:
+ </p>
+ <ul>
+ <li>DynamicHasher - calls the HashFunction as needed to generate
+ the list of bits.
+ </li>
+ <li>StaticHasher - contains a list of bits that were enabled
+ for a
+ specific Shape and simply replays them. This method is faster
+ than
+ the Dynamic when the Hasher is reused but can only be used for
+ filters with
+ the same Shape as the Hasher.
+ </li>
+ </ul>
+
+ <p>
+ Other implementations of
+ <code>Hasher</code>
+ are possible. Consider
+ the
+ <code>Hasher</code>
+ as the class that converts one or more
+ <code>byte[]</code>
+ into Bloom filters of any shape.
+ </p>
+
+ </subsection>
+
+ <subsection id="S2.SS4"
+ name="2.4 Exploring the BloomFilter">
+
+ <p>
+ The
+ <code>BloomFilter</code>
+ is an interface that describes the functionality
+ of the Bloom
+ filter. Along with the
+ <code>AbstractBloomFilter</code>
+ there
+ are three (3) concrete implementations of
+ <code>BloomFilter</code>
+ provided:
+ </p>
+
+ <ul>
+ <li>
+ <code>BitSetBloomFilter</code>
+ - Stores the enabled bits in a
+ <code>BitSet</code>
+ object.
+ </li>
+ <li>
+ <code>HasherBloomFilter</code>
+ - Uses the
+ <code>Hasher</code>
+ implementation as the storage for the bits. This is not efficient
+ but often convenient if few Bloom filter operations are required.
+ </li>
+ <li>
+ <code>CountingBloomFilter</code>
+ - Uses a sparse list (
+ <code>HashMap</code>
+ ) of counts for the enabled bits. CountingBloomFilters
+ are an
+ extension to the normal Bloom filter and enable removal of
+ Bloom
+ filters from the set.
+ </li>
+ </ul>
+
+ </subsection>
+
+ <subsection id="S2.SS5"
+ name="2.5 Why Hasher, Shape and BloomFilter?">
+
+ <p>
+ Other libraries tend to merge the functionality
+ of the
+ <code>Hasher</code>
+ ,
+ <code>Shape</code>
+ , and
+ <code>BloomFilter</code>
+ into one or two classes. By separating the responsibility we have
+ developed classes that focus on a single task. This permits a wider
+ range
+ of uses for the classes, for example:
+ </p>
+
+ <ul>
+ <li>
+ It
+ becomes possible to create client/server style applications
+ where the
+ client
+ creates a
+ <code>Hasher</code>
+ , sends it across the wire, and the server
+ then builds Bloom
+ filters of various
+ <code>Shape</code>
+ depending on the
+ requested functionality.
+ </li>
+ <li>
+ The library can support
+ Bloom filters that represent the enabled
+ bits in different ways in
+ order
+ to support specific functionality.
+ For example some applications
+ utilize
+ Bloom filters that are very
+ large (large
+ \(m\)
+ value) but have few bits
+ enabled (low
+ \(t\)
+ and
+ \(n\)
+ values). When storing a large number of these
+ it becomes important
+ to have bit vector compression. However, for
+ Bloom filters
+ with a
+ higher number of enabled bits the compression is just excess
+ overhead.
+ Applications can swap out the
+ <code>BloomFilter</code>
+ implementation without
+ impacting the
+ <code>Hasher</code>
+ or
+ <code>Shape</code>
+ selections.
+ </li>
+
+ <li>The library can support implementations of attenuated,
+ spectral
+ and other exotic Bloom filter varieties.
+ </li>
+ </ul>
+
+ </subsection>
+
+ <subsection id="S2.SS6"
+ name="2.6 Build your own BloomFilter">
+
+ <p>
+ The
+ <code>AbstractBloomFilter</code>
+ requires
+ implementation of four methods:
+ </p>
+
+ <ul>
+ <li>getBits()
+ - Get the enabled bits as an array of long values.
+ </li>
+
+ <li>getHasher() - Creates a StaticHasher that returns the indexes
+ of the enabled
+ bits and contains the shame Shape as the Bloom
+ filter.
+ </li>
+
+ <li>merge(BloomFilter) - Merges enabled bits from the other Bloom
+ filter into
+ this Bloom filter.
+ </li>
+
+ <li>merge(Hasher) - Enables
+ the bits specified by the Hasher in this
+ Bloom filter.
+ </li>
+ </ul>
+
+ <p>
+ Other methods in
+ <code>AbstractBloomFilter</code>
+ should be overridden
+ to take advantage of the bit encoding the new
+ implementation
+ provides.
+ </p>
+
+ </subsection>
+ </section>
+
+ <section id="S3" name="3 Examples">
+
+ <subsection id="S3.SS1"
+ name="3.1 How to use a Bloom filter as a gatekeeper">
+ <p>
+ A ”gatekeeper” is a Bloom filter that determines if a longer
+ running
+ method should be executed. In this example we create a Bloom
+ filter from
+ a list of bad IDs. We then check a candidate ID against
+ the Bloom
+ filter.
+ If the ID is in the Bloom filter we make the
+ expensive call to a
+ remote server
+ to verify the ID. For purposes of
+ illustration
+ <code>server.getBlackList()</code>
+ returns a list of IDs as
+ <code>Strings</code>
+ , and
+ <code>server.checkBlackList(
+ String id )
+ </code>
+ verifies that the ID is on the black list.
+ </p>
+
+
+ <source><![CDATA[
+/* setup environment */
+// select the hash function
+HashFunction hFunc = new Murmur128x86Cyclic();
+// 10000 elements, 1/million probability of collision
+Shape shape = new Shape( hFunc , 10000, 1.0/1000000);
+
+/* build the gatekeeper */
+BloomFilter gateKeeper = new BitSetBloomFilter( shape );
+for ( String id : server.getBlackList() ) {
+ DynamicHasher hasher = new DynamicHasher.Builder( hFunc ).with( id ).build();
+ gateKeeper.merge( hasher );
+}
+
+/* use the gatekeeper */
+String id = // perhaps entered by user during login
+DynamicHasher hasher = new DynamicHasher.Builder( hFunc ).with( id ).build();
+boolean inBlackList = gatekeeper.contains( hasher );
+if ( inBlackList )
+{
+ /* it might be in the blacklist, so execute the server call to find out. */
+ inBlackList = server.checkBlackList( id );
+}
+// inBlackList is now true if the ID is in the black list, false otherwise.
+ ]]></source>
+
+
+
+
+ </subsection>
+
+ <subsection id="S3.SS2" name="3.2 Data sharding">
+
+ <p>In this example we create a Bloom filter for
+ each data item we are
+ going to save. When the data is inserted in the
+ storage
+ each
+ gatekeeper Bloom filter is checked to see which is ”closest” to
+ the
+ filter being inserted and the object is inserted in the associated
+ container.
+ When searching for data each gatekeeper Bloom filter is
+ checked for the
+ presence
+ of the data Bloom filter if it is in the
+ gatekeeper then the
+ associated container
+ is searched for the object.
+ </p>
+
+
+ <source><![CDATA[
+/* setup environment */
+
+// Set some limits
+int MAX_SHARD_SIZE = 100000;
+
+// select the hash function
+HashFunction hFunc = new Murmur128x86Cyclic();
+
+// 100000 elements, 1/million probability of collision
+Shape shape = new Shape( hFunc , MAX_SHARD_SIZE , 1.0/1000000);
+
+// create the sharding container
+Map < CountingBloomFilter , Map < String , T >> shards = new HashMap <>();
+
+// populate the minimum shards (5)
+for ( int i =0; i <5; i ++) {
+ shards.put( new CountingBloomFilter( shape ), new HashMap < String , T >>() );
+}
+
+
+/* insert a data object */
+
+T data = // get the data object.
+DynamicHasher hasher = new DynamicHasher.Builder( hFunc ).with( data.getId() ).build();
+BloomFilter dataBloom = new BitSetBloomFilter( hasher , shape );
+int distance = Integer.MAX_VALUE ;
+BloomFilter collectionFilter = null
+for ( BloomFilter candidate : shards.keySet() ) {
+ if ( SetOperations.hammingDistance( candidate , dataBloom ) < distance ) {
+ distance = SetOperations.hammingDistance( candidate , dataBloom );
+ collectionFilter = candidate ;
+ }
+}
+if ( collectionFilter == null ) {
+ // no available collection so create one.
+ collectionFilter = new CountingBloomFilter( shape );
+ shards.put( collectionFilter , new HashMap < String , T >() );
+}
+Map < String , T > collection = shards.get( collectionFilter );
+if ( collection.size() >= MAX_SHARD_SIZE ) {
+ // no space in collection so create a new one.
+ collectionFilter = new CountingBloomFilter( shape );
+ collection = new HashMap < String , T >();
+ shards.put( collectionFilter , collection );
+}
+collectionFilter.merge( dataBloom );
+collections.put( data.getId(), data );
+
+
+/* search for a data object */
+
+T result = null ;
+String id = // get the data ID.
+DynamicHasher hasher = new DynamicHasher.Builder( hFunc ).with( id ).build();
+BloomFilter dataBloom = new BitSetBloomFilter( hasher , shape );
+for ( Map.Entry < BloomFilter , Collection < T >> entry : shards ) {
+ if ( shard.key().contains( dataBloom )) {
+ T candidate = shard.value().get( id );
+ if ( candidate != null ) {
+ result = candidate ;
+ }
+ }
+}
+// result is either null or contains the desired value.
+ ]]></source>
+ </subsection>
+ <subsection id="S3.SS3" name="3.3 Future directions">
+
+ <p>
+ The separation and definition of the
+ <code>HashFunctionIdentity</code>
+ ,
+ <code>HashFunction</code>
+ , and
+ <code>Hasher</code>
+ classes as well as the development of the Cyclic hash function,
+ means that it is possible to construct hashers that can be sent
+ across the
+ wire. This opens up the possibility of sending query
+ requests without
+ exposing
+ the values or properties being queried and
+ may provide the ability to
+ query
+ encrypted data. <cite>[<a href='#Bellovin'>Bellovin</a>,
+ <a href='#Goh'>Goh</a>,
+ <a href='#Tajima'>Tajima</a>,
+ <a href='#Warren1'>Warren1</a>]</cite>
+ </p>
+
+ <p>
+ Implementations of multidimensional
+ Bloom filters <cite>[<a href='#Crainiceanu'>Crainiceanu</a>]</cite>
+ (AKA Bloom filter
+ indexes) may also be enhanced as the Hasher is not
+ bound to a shape. So
+ multidimensional
+ filters can us a Bloom filter
+ of a different Shape from the ones being
+ stored
+ to reduce the number
+ of filters it actually checks for. <cite>[<a href='#Warren2'>Warren2</a>]</cite>
+ </p>
+
+ <p>Implementations of attenuated,
+ spectral and other exotic Bloom
+ filter varieties is possible using the
+ commons-collection
+ library.
+ </p>
+ </subsection>
+ </section>
+ <section id="S4" name="4 References">
+ <div class="references">
+
+ <div id="Bellovin">
+ <span class="refName">[Bellovin]</span>
+ <span class="refBody">
+ Steven M Bellovin and William R Cheswick”. Privacy-Enchanced
+ Searched
+ Using Encrypted Bloom Filters”. 2004. url:
+ <a
+ href="https://mice.cs.columbia.edu/getTechreport.php?techreportID=483">https://mice.cs.columbia.edu/getTechreport.php?techreportID=483
+ </a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+
+ <div id="Bloom">
+ <span class="refName">[Bloom]</span>
+ <span class="refBody">
+ Burton H. Bloom. “Space/Time Trade-offs in Hash
+ Coding with
+ Allowable
+ Errors”. In: Communications of the ACM 13.7
+ (July 1970), pp. 422–426.
+ </span>
+ </div>
+
+ <div id="Crainiceanu">
+ <span class="refName">[Crainiceanu]</span>
+ <span class="refBody">
+ Adina Crainiceanu and Daniel Lemire. Bloofi: Multidimensional
+ Bloom
+ Filters. Accessed on 11-Jan-2020. 2016. url:
+ <a href="https://arxiv.org/pdf/1501.01941.pdf">https://arxiv.org/pdf/1501.01941.pdf</a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+ <div id="Goh">
+ <span class="refName">[Goh]</span>
+ <span class="refBody">
+ Eu-Jin Goh. Secure Indexes. 2004. url:
+ <a
+ href="https://crypto.stanford.edu/~eujin/papers/secureindex/secureindex.pdf">https://crypto.stanford.edu/~eujin/papers/secureindex/secureindex.pdf
+ </a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+
+ <div id="Hurst">
+ <span class="refName">[Hurst]</span>
+ <span class="refBody">
+ Thomas Hurst. Bloom filter calculator. 2019.
+ url:
+ <a href="https://hur.st/bloomfilter/">https://hur.st/bloomfilter/</a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+
+ <div id="Kirsch">
+ <span class="refName">[Kirsch]</span>
+ <span class="refBody">
+ Adam Kirsch and Michael Mitzenmacher. Building a Better Bloom
+ Filter.
+ 2008. url:
+ <a
+ href="https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf">https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf
+ </a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+
+ <div id="Mitzenmacher">
+ <span class="refName">[Mitzenmacher]</span>
+ <span class="refBody">
+ Michael Mitzenmacher and Eli Upfal. Probability
+ and computing:
+ Randomized algorithms and probabilistic analysis.
+ Cambridge, Cambridgeshire,
+ UK: Cambridge University Press, 2005,
+ pp. 109–111, 308. isbn:
+ 9780521835404.
+ </span>
+ </div>
+
+ <div id="Tajima">
+ <span class="refName">[Tajima]</span>
+ <span class="refBody">
+ Arisa Tajima, Hiroki Sato, and Hayato Yamana. Privacy-Preserving
+ Join
+ Processing over outsourced private datasets with Fully
+ Homomorphic En-
+ cryption and Bloom Filters. 2018. url:
+ <a href="https://db-event.jpn.org/deim2018/data/papers/201.pdf">https://db-event.jpn.org/deim2018/data/papers/201.pdf
+ </a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+
+ <div id="Warren1">
+ <span class="refName">[Warren1]</span>
+ <span class="refBody">
+ Claude N. Warren Jr.
+ Bloom Encrypted Index. 2019. url:
+ <a href="https://github.com/Claudenw/BloomEncryptedIndex">
+ https://github.com/Claudenw/BloomEncryptedIndex
+ </a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+
+ <div id="Warren2">
+ <span class="refName">[Warren2]</span>
+ <span class="refBody">
+ Claude N. Warren Jr.
+ Multidimentional Bloom Filter Implementations.
+ 2019. url:
+ <a href="https://github.com/Claudenw/MultidimentionalBloom">https://github.com/Claudenw/MultidimentionalBloom</a>
+ (Accessed 26 Jan 2020).
+ </span>
+ </div>
+ </div>
+ </section>
+
+ </body>
+</document>
\ No newline at end of file
diff --git a/src/site/xdoc/userguide.xml b/src/site/xdoc/userguide.xml
index 3861b1e..c705f2d 100644
--- a/src/site/xdoc/userguide.xml
+++ b/src/site/xdoc/userguide.xml
@@ -40,6 +40,7 @@ This document highlights some key features to get you started.
</ul>
</li>
<li><a href='#Bags'>Bags</a></li>
+ <li><a href="bloomFilters.html">Bloom filters</a></li>
</ul>
<subsection name='Note On Synchronization'>
<p>