Complete the implementation of Bloom Filter Index as an another indexing strategy for tuples stored in StorageBlock
diff --git a/parser/ParseIndexProperties.hpp b/parser/ParseIndexProperties.hpp
index 45639de..0acca62 100644
--- a/parser/ParseIndexProperties.hpp
+++ b/parser/ParseIndexProperties.hpp
@@ -187,8 +187,7 @@
    * @brief Constructor.
    **/
   BloomFilterIndexProperties()
-      : IndexProperties(new IndexSubBlockDescription(),
-                        InvalidIndexType::kUnimplemented) {
+      : IndexProperties(new IndexSubBlockDescription()) {
     index_sub_block_description_->set_sub_block_type(IndexSubBlockDescription::BLOOM_FILTER);
 
     // Initialize the valid_property_map_ for this index with appropriate type for each property.
diff --git a/query_optimizer/tests/execution_generator/Index.test b/query_optimizer/tests/execution_generator/Index.test
index 77a81d5..2dd71f4 100644
--- a/query_optimizer/tests/execution_generator/Index.test
+++ b/query_optimizer/tests/execution_generator/Index.test
@@ -45,11 +45,13 @@
 +-----------+-----------+
 ==
 # Bloom filter index is not currently implemented.
-CREATE INDEX bloomIndex ON test(int_col) USING BLOOMFILTER
+CREATE INDEX idx4 ON foo3(col1, col2) USING BLOOMFILTER;
+SELECT * FROM foo3;
 --
-ERROR: Bloom Filter index is not yet implemented (1 : 48)
-...INDEX bloomIndex ON test(int_col) USING BLOOMFILTER
-                                           ^
++-----------+-----------+
+|col1       |col2       |
++-----------+-----------+
++-----------+-----------+
 ==
 # SMA Index creation is not supported using CREATE INDEX.
 CREATE INDEX smaIndex ON test USING SMA
diff --git a/query_optimizer/tests/logical_generator/Index.test b/query_optimizer/tests/logical_generator/Index.test
index 4136255..5a38567 100644
--- a/query_optimizer/tests/logical_generator/Index.test
+++ b/query_optimizer/tests/logical_generator/Index.test
@@ -36,10 +36,23 @@
 # Bloom filter index is not currently implemented.
 CREATE INDEX bloomIndex ON test(int_col) USING BLOOMFILTER
 --
-ERROR: Bloom Filter index is not yet implemented (1 : 48)
-...INDEX bloomIndex ON test(int_col) USING BLOOMFILTER
-                                           ^
+TopLevelPlan
++-plan=CreateIndex[index_name=bloomIndex,
+| serialized_index_description=sub_block_type: BLOOM_FILTER
+]
+| +-relation=TableReference[relation_name=Test,relation_alias=test]
+| | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | +-AttributeReference[id=5,name=vchar_col,relation=test,type=VarChar(20) NULL]
+| +-index_attributes=
+|   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
 ==
+
 # SMA Index creation is not supported using CREATE INDEX
 CREATE INDEX smaIndex ON test USING SMA
 --
diff --git a/query_optimizer/tests/physical_generator/Index.test b/query_optimizer/tests/physical_generator/Index.test
index 5b1cf00..59f514d 100644
--- a/query_optimizer/tests/physical_generator/Index.test
+++ b/query_optimizer/tests/physical_generator/Index.test
@@ -53,10 +53,40 @@
 # Bloom filter index is not currently implemented.
 CREATE INDEX bloomIndex ON test(int_col) USING BLOOMFILTER
 --
-ERROR: Bloom Filter index is not yet implemented (1 : 48)
-...INDEX bloomIndex ON test(int_col) USING BLOOMFILTER
-                                           ^
+[Optimized Logical Plan]
+TopLevelPlan
++-plan=CreateIndex[index_name=bloomIndex,
+| serialized_index_description=sub_block_type: BLOOM_FILTER
+]
+| +-relation=TableReference[relation_name=Test,relation_alias=test]
+| | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | +-AttributeReference[id=5,name=vchar_col,relation=test,type=VarChar(20) NULL]
+| +-index_attributes=
+|   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+[Physical Plan]
+TopLevelPlan
++-plan=CreateIndex[index_name=bloomIndex,
+| serialized_index_description=sub_block_type: BLOOM_FILTER
+]
+| +-relation=TableReference[relation=Test,alias=test]
+| | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | +-AttributeReference[id=5,name=vchar_col,relation=test,type=VarChar(20) NULL]
+| +-index_attributes=
+|   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
++-output_attributes=
+  +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
 ==
+
 # SMA Index creation is not supported using CREATE INDEX
 CREATE INDEX smaIndex ON test USING SMA
 --
diff --git a/query_optimizer/tests/resolver/Index.test b/query_optimizer/tests/resolver/Index.test
index 43dc4af..869f1e3 100644
--- a/query_optimizer/tests/resolver/Index.test
+++ b/query_optimizer/tests/resolver/Index.test
@@ -62,21 +62,44 @@
   +-AttributeReference[id=5,name=vchar_col,relation=test,type=VarChar(20) NULL]
 ==
 
-# Creating random index type will fail
-CREATE INDEX bloomIndex ON test USING RANDOM;
---
-ERROR: syntax error (1 : 39)
-CREATE INDEX bloomIndex ON test USING RANDOM;
-                                      ^
-==
-
 # Bloom filter index is not yet implemented
 CREATE INDEX bloomIndex ON test USING BLOOMFILTER;
 --
-ERROR: Bloom Filter index is not yet implemented (1 : 39)
-CREATE INDEX bloomIndex ON test USING BLOOMFILTER;
-                                      ^
+TopLevelPlan
++-plan=CreateIndex[index_name=bloomIndex,
+| serialized_index_description=sub_block_type: BLOOM_FILTER
+]
+| +-relation=TableReference[relation_name=Test,relation_alias=test]
+| | +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+| | +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+| | +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+| | +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+| | +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+| | +-AttributeReference[id=5,name=vchar_col,relation=test,type=VarChar(20) NULL]
+| +-index_attributes=
+|   +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+|   +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+|   +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+|   +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+|   +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+|   +-AttributeReference[id=5,name=vchar_col,relation=test,type=VarChar(20) NULL]
++-output_attributes=
+  +-AttributeReference[id=0,name=int_col,relation=test,type=Int NULL]
+  +-AttributeReference[id=1,name=long_col,relation=test,type=Long]
+  +-AttributeReference[id=2,name=float_col,relation=test,type=Float]
+  +-AttributeReference[id=3,name=double_col,relation=test,type=Double NULL]
+  +-AttributeReference[id=4,name=char_col,relation=test,type=Char(20)]
+  +-AttributeReference[id=5,name=vchar_col,relation=test,type=VarChar(20) NULL]
 ==
+
+# Creating random index type will fail
+CREATE INDEX randomIndex ON test USING RANDOM;
+--
+ERROR: syntax error (1 : 40)
+CREATE INDEX randomIndex ON test USING RANDOM;
+                                       ^
+==
+
 # SMA Index creation is not supported using CREATE INDEX
 CREATE INDEX smaIndex ON test USING SMA
 --
diff --git a/storage/BloomFilterIndexSubBlock.cpp b/storage/BloomFilterIndexSubBlock.cpp
new file mode 100644
index 0000000..e806217
--- /dev/null
+++ b/storage/BloomFilterIndexSubBlock.cpp
@@ -0,0 +1,279 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   Licensed 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.
+ **/
+
+#include "storage/BloomFilterIndexSubBlock.hpp"
+
+#include <cstdint>
+
+#include "catalog/CatalogAttribute.hpp"
+#include "catalog/CatalogRelationSchema.hpp"
+#include "catalog/CatalogTypedefs.hpp"
+#include "expressions/predicate/ComparisonPredicate.hpp"
+#include "expressions/predicate/PredicateCost.hpp"
+#include "expressions/scalar/Scalar.hpp"
+#include "expressions/scalar/ScalarAttribute.hpp"
+#include "expressions/scalar/ScalarLiteral.hpp"
+#include "storage/StorageBlockLayout.pb.h"
+#include "storage/StorageConstants.hpp"
+#include "storage/SubBlockTypeRegistry.hpp"
+#include "storage/TupleIdSequence.hpp"
+#include "storage/TupleStorageSubBlock.hpp"
+#include "types/TypedValue.hpp"
+#include "types/operations/comparisons/Comparison.hpp"
+#include "types/operations/comparisons/ComparisonID.hpp"
+#include "utility/BloomFilter.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+QUICKSTEP_REGISTER_INDEX(BloomFilterIndexSubBlock, BLOOM_FILTER);
+
+BloomFilterIndexSubBlock::BloomFilterIndexSubBlock(const TupleStorageSubBlock &tuple_store,
+                                                   const IndexSubBlockDescription &description,
+                                                   const bool is_new_block,
+                                                   void *sub_block_memory,
+                                                   const std::size_t sub_block_memory_size)
+    : IndexSubBlock(tuple_store,
+                    description,
+                    is_new_block,
+                    sub_block_memory,
+                    sub_block_memory_size),
+      is_initialized_(false),
+      is_consistent_(false),
+      random_seed_(kBloomFilterSeed),
+      bit_array_size_in_bytes_(description.GetExtension(
+                                   BloomFilterIndexSubBlockDescription::bloom_filter_size)) {
+  CHECK(DescriptionIsValid(relation_, description_))
+      << "Attempted to construct an BloomFilterIndexSubBlock from an invalid description.";
+
+  // Store the attribute ids that are being indexed.
+  indexed_attribute_ids_.reserve(description.indexed_attribute_ids_size());
+  for (int i = 0; i < description.indexed_attribute_ids_size(); ++i) {
+    indexed_attribute_ids_.push_back(description.indexed_attribute_ids(i));
+  }
+
+  // Make the bit_array_ point to sub_block_memory.
+  bit_array_.reset(static_cast<std::uint8_t*>(sub_block_memory));
+
+  bool is_bloom_filter_initialized = !is_new_block;
+  const std::uint32_t salt_count = description.GetExtension(BloomFilterIndexSubBlockDescription::number_of_hashes);
+
+  // Initialize the bloom_filter_ data structure to operate on bit_array.
+  bloom_filter_.reset(new BloomFilter(random_seed_,
+                                      salt_count,
+                                      bit_array_size_in_bytes_,
+                                      bit_array_.get(),
+                                      is_bloom_filter_initialized));
+  is_initialized_ = true;
+  is_consistent_ = true;
+}
+
+BloomFilterIndexSubBlock::~BloomFilterIndexSubBlock() {
+  bit_array_.release();  // De-allocation of bit_array_ is handled by StorageBlock.
+}
+
+bool BloomFilterIndexSubBlock::DescriptionIsValid(const CatalogRelationSchema &relation,
+                                         const IndexSubBlockDescription &description) {
+  if (!description.IsInitialized()) {
+    return false;
+  }
+
+  if (description.sub_block_type() != IndexSubBlockDescription::BLOOM_FILTER) {
+    return false;
+  }
+
+  // Check that all the specified index attributes are valid.
+  for (int i = 0; i < description.indexed_attribute_ids_size(); ++i) {
+    const attribute_id indexed_attribute_id = description.indexed_attribute_ids(i);
+    if (!relation.hasAttributeWithId(indexed_attribute_id)) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+std::size_t BloomFilterIndexSubBlock::EstimateBytesPerTuple(const CatalogRelationSchema &relation,
+                                                            const IndexSubBlockDescription &description) {
+  DCHECK(DescriptionIsValid(relation, description));
+  // Note: Returning zero here causes EstimteBytesPerBlock() to be invoked for size computation.
+  return kZeroSize;
+}
+
+std::size_t BloomFilterIndexSubBlock::EstimateBytesPerBlock(const CatalogRelationSchema &relation,
+                                                            const IndexSubBlockDescription &description) {
+  // Note: This function is only invoked when EstimateBytesPerTuple() returns zero.
+  DCHECK(DescriptionIsValid(relation, description));
+  return description.GetExtension(BloomFilterIndexSubBlockDescription::bloom_filter_size);
+}
+
+bool BloomFilterIndexSubBlock::addEntry(const tuple_id tuple) {
+  DCHECK(is_initialized_);
+  if (!is_consistent_) {
+    return false;
+  }
+  if (!tuple_store_.hasTupleWithID(tuple)) {
+    return false;
+  }
+  for (std::size_t i = 0; i < indexed_attribute_ids_.size(); ++i) {
+    const attribute_id indexed_attribute_id = indexed_attribute_ids_[i];
+    const TypedValue tuple_value = tuple_store_.getAttributeValueTyped(tuple, indexed_attribute_id);
+    const std::uint8_t *data = static_cast<const std::uint8_t*>(tuple_value.getDataPtr());
+    const std::size_t data_size = tuple_value.getDataSize();
+    if (!tuple_value.isNull()) {
+      bloom_filter_->insert(data, data_size);
+    }
+  }
+  return true;
+}
+
+bool BloomFilterIndexSubBlock::bulkAddEntries(const TupleIdSequence &tuples) {
+  DCHECK(is_initialized_);
+  if (!is_consistent_) {
+    return false;
+  }
+  bool didAllSucceed = true;
+  for (const tuple_id &tuple : tuples) {
+    didAllSucceed = didAllSucceed && addEntry(tuple);
+  }
+  return didAllSucceed;
+}
+
+void BloomFilterIndexSubBlock::removeEntry(const tuple_id tuple) {
+  is_consistent_ = false;
+}
+
+void BloomFilterIndexSubBlock::bulkRemoveEntries(const TupleIdSequence &tuples) {
+  is_consistent_ = false;
+}
+
+predicate_cost_t BloomFilterIndexSubBlock::estimatePredicateEvaluationCost(
+    const ComparisonPredicate &predicate) const {
+  DCHECK(is_initialized_);
+  BloomFilterSelectivity selectivity = getSelectivityForPredicate(predicate);
+  // Note: A Bloomfilter index is only useful when it gives a zero selectivity
+  //       in which case a block can be skipped entirely.
+  if (selectivity == BloomFilterSelectivity::kSelectivityNone) {
+    // Return minimum cost so that this block can be skipped altogether.
+    return predicate_cost::kConstantTime;
+  } else {
+    // Return maximum cost because this is as worse as doing a full scan of the block.
+    return predicate_cost::kInfinite;
+  }
+}
+
+TupleIdSequence* BloomFilterIndexSubBlock::getMatchesForPredicate(
+    const ComparisonPredicate &predicate,
+    const TupleIdSequence *filter) const {
+  DCHECK(is_initialized_);
+  if (filter != nullptr) {
+    LOG(FATAL) << "BloomFilterIndex does not support filter evaluation with predicate.";
+  }
+  BloomFilterSelectivity selectivity = getSelectivityForPredicate(predicate);
+  if (selectivity == BloomFilterSelectivity::kSelectivityNone) {
+    // This path is invoked when there is a BloomFilter miss (true negative)
+    // and a BloomFilter index allows to skip this block entirely.
+    // A new tuple ID sequence is initialized to false for all values.
+    return new TupleIdSequence(tuple_store_.numTuples());
+  } else if (selectivity == BloomFilterSelectivity::kSelectivityAll) {
+    // This path is invoked when there is a BloomFilter hit (possibly false positive)
+    // and a BloomFilter index does not provide much information.
+    // Note: If estimatePredicateEvaluationCost() is used by optimizer to evaluate
+    //       the cost of using BloomFilter index for a BloomFilter hit,
+    //       getMatchesForPredicate() will not be called in the first place itself
+    //       and this path will never be taken.
+    TupleIdSequence* tuple_sequence = new TupleIdSequence(tuple_store_.numTuples());
+    // Set all existing tuples to true, selected.
+    if (tuple_store_.isPacked()) {
+      tuple_sequence->setRange(0, tuple_store_.numTuples(), true);
+    } else {
+      for (tuple_id tid = 0; tid <= tuple_store_.getMaxTupleID(); ++tid) {
+        if (tuple_store_.hasTupleWithID(tid)) {
+          tuple_sequence->set(tid, true);
+        }
+      }
+    }
+    return tuple_sequence;
+  } else {
+    LOG(FATAL) << "BloomFilterIndex should never have been called.";
+    return nullptr;
+  }
+}
+
+BloomFilterIndexSubBlock::BloomFilterSelectivity
+    BloomFilterIndexSubBlock::getSelectivityForPredicate(const ComparisonPredicate &predicate) const {
+  DCHECK(is_initialized_);
+  if (!is_consistent_) {
+    return BloomFilterSelectivity::kSelectivityUnknown;
+  }
+  // Bloom filter index can be currently only used to evaluate
+  // equality matching comparison predicates with static values as the right operand.
+  if (predicate.getComparison().getComparisonID() == ComparisonID::kEqual
+      && predicate.getRightOperand().hasStaticValue()) {
+    const ScalarAttribute *left_operand = static_cast<const ScalarAttribute*>(&predicate.getLeftOperand());
+    const attribute_id attr_id_checked = left_operand->getAttribute().getID();
+
+    // Check if the specified attribute in the predicate is actually indexed or not.
+    bool is_attribute_indexed = false;
+    for (const attribute_id &attr_id_expected : indexed_attribute_ids_) {
+      if (attr_id_expected == attr_id_checked) {
+        is_attribute_indexed = true;
+        break;
+      }
+    }
+    if (!is_attribute_indexed) {
+      // Specified attribute not indexed, this index provides no useful information.
+      return BloomFilterSelectivity::kSelectivityUnknown;
+    }
+
+    const ScalarLiteral *right_operand = static_cast<const ScalarLiteral*>(&predicate.getRightOperand());
+    const std::uint8_t *test_data = static_cast<const std::uint8_t*>(right_operand->getStaticValue().getDataPtr());
+    const std::size_t test_data_size = right_operand->getStaticValue().getDataSize();
+    bool is_contained = bloom_filter_->contains(test_data, test_data_size);
+
+    if (is_contained) {
+      // Bloom filter hit. Can be a false positive, a scan is required here.
+      return BloomFilterSelectivity::kSelectivityAll;
+    } else {
+      // Bloom filter miss. Definitely a true negative. Selectivity is zero.
+      return BloomFilterSelectivity::kSelectivityNone;
+    }
+  }
+  return BloomFilterSelectivity::kSelectivityUnknown;
+}
+
+bool BloomFilterIndexSubBlock::rebuild() {
+  DCHECK(is_initialized_);
+  bloom_filter_->reset();
+  bool didSucceed = true;
+  if (tuple_store_.isPacked()) {
+    for (tuple_id tid = 0; didSucceed && tid <= tuple_store_.getMaxTupleID(); ++tid) {
+      didSucceed = addEntry(tid);
+    }
+  } else {
+    for (tuple_id tid = 0; didSucceed && tid <= tuple_store_.getMaxTupleID(); ++tid) {
+      if (tuple_store_.hasTupleWithID(tid)) {
+        didSucceed = addEntry(tid);
+      }
+    }
+  }
+  is_consistent_ = true;
+  return didSucceed;
+}
+
+}  // namespace quickstep
diff --git a/storage/BloomFilterIndexSubBlock.hpp b/storage/BloomFilterIndexSubBlock.hpp
new file mode 100644
index 0000000..4925673
--- /dev/null
+++ b/storage/BloomFilterIndexSubBlock.hpp
@@ -0,0 +1,197 @@
+/**
+*   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+*     University of Wisconsin—Madison.
+*
+*   Licensed 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.
+**/
+
+#ifndef QUICKSTEP_STORAGE_BLOOM_FILTER_INDEX_SUB_BLOCK_HPP_
+#define QUICKSTEP_STORAGE_BLOOM_FILTER_INDEX_SUB_BLOCK_HPP_
+
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <vector>
+
+#include "expressions/predicate/PredicateCost.hpp"
+#include "storage/IndexSubBlock.hpp"
+#include "storage/StorageBlockInfo.hpp"
+#include "storage/SubBlockTypeRegistryMacros.hpp"
+#include "utility/BloomFilter.hpp"
+#include "utility/Macros.hpp"
+
+namespace quickstep {
+
+class CatalogRelationSchema;
+class ComparisonPredicate;
+class IndexSubBlockDescription;
+class TupleIdSequence;
+class TupleStorageSubBlock;
+
+QUICKSTEP_DECLARE_SUB_BLOCK_TYPE_REGISTERED(BloomFilterIndexSubBlock);
+
+/** \addtogroup Storage
+*  @{
+*/
+
+/**
+* @brief An IndexSubBlock which implements a Bloom Filter index.
+* @note This IndexSubBlock supports both fixed-length attributes, and the
+*          variable length attributes.
+**/
+class BloomFilterIndexSubBlock : public IndexSubBlock {
+ public:
+  /**
+   * @brief An enum describing the various selecitivity factors provided by
+   *        a BloomFilter index.
+   * @note A kSelectivityNone will correspond to a BloomFilter miss (true negative),
+   *       when the data is certainly guaranteed to be not present in the StorageBlock.
+   *       A kSelectivityAll, kSelectivityNone will correspond to a BloomFilter hit
+   *       when the data may or may not be present in the StorageBlock.
+   **/
+  enum class BloomFilterSelectivity {
+    kSelectivityUnknown = 0,
+    kSelectivityAll,
+    kSelectivityNone
+  };
+
+  /**
+   * @brief A random seed to initialize the bloom filter hash functions.
+   **/
+  static const std::uint64_t kBloomFilterSeed = 0xA5A5A5A55A5A5A5AULL;
+
+  BloomFilterIndexSubBlock(const TupleStorageSubBlock &tuple_store,
+                           const IndexSubBlockDescription &description,
+                           const bool new_block,
+                           void *sub_block_memory,
+                           const std::size_t sub_block_memory_size);
+
+  ~BloomFilterIndexSubBlock() override;
+
+  /**
+  * @brief Determine whether an IndexSubBlockDescription is valid for this
+  *        type of IndexSubBlock.
+  *
+  * @param relation The relation an index described by description would
+  *        belong to.
+  * @param description A description of the parameters for this type of
+  *        IndexSubBlock, which will be checked for validity.
+  * @return Whether description is well-formed and valid for this type of
+  *         IndexSubBlock belonging to relation (i.e. whether an IndexSubBlock
+  *         of this type, belonging to relation, can be constructed according
+  *         to description).
+  **/
+  static bool DescriptionIsValid(const CatalogRelationSchema &relation,
+                                const IndexSubBlockDescription &description);
+
+  /**
+  * @brief Estimate the average number of bytes (including any applicable
+  *        overhead) used to index a single tuple in this type of
+  *        IndexSubBlock. Used by StorageBlockLayout::finalize() to divide
+  *        block memory amongst sub-blocks.
+  * @warning description must be valid. DescriptionIsValid() should be called
+  *          first if necessary.
+  *
+  * @param relation The relation tuples belong to.
+  * @param description A description of the parameters for this type of
+  *        IndexSubBlock.
+  * @return The average/ammortized number of bytes used to index a single
+  *         tuple of relation in an IndexSubBlock of this type described by
+  *         description.
+  **/
+  static std::size_t EstimateBytesPerTuple(const CatalogRelationSchema &relation,
+                                          const IndexSubBlockDescription &description);
+
+  /**
+   * @brief Estimate the total number of bytes (including any applicable
+   *        overhead) occupied by this IndexSubBlock within the StorageBlock.
+   *        This function is to be used by those indicies whose occupied size
+   *        in the block does not depend on the number of tuples being indexed.
+   * @warning description must be valid. DescriptionIsValid() should be called
+   *          first if necessary.
+   * @note This function will be invoked by StorageBlockLayout::finalize()
+   *       if and only when EstimateBytesPerTuple() returns a zero size.
+   *
+   * @param relation The relation tuples belong to.
+   * @param description A description of the parameters for this type of
+   *        IndexSubBlock.
+   * @return The total number of bytes occupied by this IndexSubBlock within
+   *         the StorageBlock.
+   **/
+  static std::size_t EstimateBytesPerBlock(const CatalogRelationSchema &relation,
+                                           const IndexSubBlockDescription &description);
+
+  IndexSubBlockType getIndexSubBlockType() const override {
+    return kBloomFilter;
+  }
+
+  bool supportsAdHocAdd() const override {
+    return true;
+  }
+
+  bool supportsAdHocRemove() const override {
+    return false;
+  }
+
+  bool addEntry(const tuple_id tuple) override;
+
+  bool bulkAddEntries(const TupleIdSequence &tuples) override;
+
+  void removeEntry(const tuple_id tuple) override;
+
+  void bulkRemoveEntries(const TupleIdSequence &tuples) override;
+
+  predicate_cost_t estimatePredicateEvaluationCost(
+     const ComparisonPredicate &predicate) const override;
+
+  /**
+  * @note Currently this version only supports predicates with
+  *       equality comparison of a static literal value with a non-composite key.
+  **/
+  TupleIdSequence* getMatchesForPredicate(const ComparisonPredicate &predicate,
+                                          const TupleIdSequence *filter) const override;
+
+  bool rebuild() override;
+
+  /**
+   * @brief Get the selectivity provided by the index for a given predicate.
+   *        There are only two selectivity levels returned by this function-
+   *        either a zero(none) selectivity for bloom filter miss
+   *        or a one(all) selectivity for bloom filter hit.
+   *        A none selectivity predicate will return no tuples, whereas
+   *        an all selectivity predicate will possibly return all tuples.
+   *
+   * @param predicate The comparison predicate to evaluate selectivity for.
+   * @return An enum describing the selectivity factor.
+   **/
+  BloomFilterSelectivity getSelectivityForPredicate(const ComparisonPredicate &predicate) const;
+
+ private:
+  bool is_initialized_;
+  bool is_consistent_;
+  const std::uint64_t random_seed_;
+  const std::uint64_t bit_array_size_in_bytes_;
+  std::vector<attribute_id> indexed_attribute_ids_;
+  std::unique_ptr<unsigned char> bit_array_;
+  std::unique_ptr<BloomFilter> bloom_filter_;
+
+  friend class BloomFilterIndexSubBlockTest;
+
+  DISALLOW_COPY_AND_ASSIGN(BloomFilterIndexSubBlock);
+};
+
+/** @} */
+
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_STORAGE_BLOOM_FILTER_INDEX_SUB_BLOCK_HPP_
diff --git a/storage/CMakeLists.txt b/storage/CMakeLists.txt
index af56381..37cfc3d 100644
--- a/storage/CMakeLists.txt
+++ b/storage/CMakeLists.txt
@@ -137,6 +137,7 @@
 add_library(quickstep_storage_BasicColumnStoreValueAccessor
             ../empty_src.cpp
             BasicColumnStoreValueAccessor.hpp)
+add_library(quickstep_storage_BloomFilterIndexSubBlock BloomFilterIndexSubBlock.cpp BloomFilterIndexSubBlock.hpp)
 add_library(quickstep_storage_ColumnStoreUtil ColumnStoreUtil.cpp ColumnStoreUtil.hpp)
 add_library(quickstep_storage_CompressedBlockBuilder CompressedBlockBuilder.cpp CompressedBlockBuilder.hpp)
 add_library(quickstep_storage_CompressedColumnStoreTupleStorageSubBlock
@@ -293,6 +294,28 @@
                       quickstep_utility_BitVector
                       quickstep_utility_Macros
                       quickstep_utility_PtrVector)
+target_link_libraries(quickstep_storage_BloomFilterIndexSubBlock
+                      quickstep_catalog_CatalogAttribute
+                      quickstep_catalog_CatalogRelationSchema
+                      quickstep_catalog_CatalogTypedefs
+                      quickstep_expressions_predicate_ComparisonPredicate
+                      quickstep_expressions_predicate_PredicateCost
+                      quickstep_expressions_scalar_Scalar
+                      quickstep_expressions_scalar_ScalarAttribute
+                      quickstep_expressions_scalar_ScalarLiteral
+                      quickstep_storage_IndexSubBlock
+                      quickstep_storage_StorageBlockInfo
+                      quickstep_storage_StorageBlockLayout_proto
+                      quickstep_storage_StorageConstants
+                      quickstep_storage_SubBlockTypeRegistry
+                      quickstep_storage_SubBlockTypeRegistryMacros
+                      quickstep_storage_TupleIdSequence
+                      quickstep_storage_TupleStorageSubBlock
+                      quickstep_types_TypedValue
+                      quickstep_types_operations_comparisons_Comparison
+                      quickstep_types_operations_comparisons_ComparisonID
+                      quickstep_utility_BloomFilter
+                      quickstep_utility_Macros)
 target_link_libraries(quickstep_storage_ColumnStoreUtil
                       quickstep_catalog_CatalogAttribute
                       quickstep_catalog_CatalogRelationSchema
@@ -659,6 +682,7 @@
                       quickstep_storage_IndexSubBlock
                       quickstep_storage_StorageBlockInfo
                       quickstep_storage_StorageBlockLayout_proto
+                      quickstep_storage_StorageConstants
                       quickstep_storage_SubBlockTypeRegistry
                       quickstep_storage_SubBlockTypeRegistryMacros
                       quickstep_storage_TupleIdSequence
@@ -743,6 +767,7 @@
                       quickstep_expressions_predicate_Predicate
                       quickstep_expressions_scalar_Scalar
                       quickstep_storage_BasicColumnStoreTupleStorageSubBlock
+                      quickstep_storage_BloomFilterIndexSubBlock
                       quickstep_storage_CSBTreeIndexSubBlock
                       quickstep_storage_CompressedColumnStoreTupleStorageSubBlock
                       quickstep_storage_CompressedPackedRowStoreTupleStorageSubBlock
@@ -819,6 +844,7 @@
                         ${LIBNUMA_LIBRARY})
 endif()
 target_link_libraries(quickstep_storage_SubBlockTypeRegistry
+                      glog
                       quickstep_storage_StorageBlockLayout_proto
                       quickstep_utility_Macros)
 target_link_libraries(quickstep_storage_SubBlocksReference
@@ -869,6 +895,7 @@
                       quickstep_storage_AggregationOperationState_proto
                       quickstep_storage_BasicColumnStoreTupleStorageSubBlock
                       quickstep_storage_BasicColumnStoreValueAccessor
+                      quickstep_storage_BloomFilterIndexSubBlock
                       quickstep_storage_CSBTreeIndexSubBlock
                       quickstep_storage_ColumnStoreUtil
                       quickstep_storage_CompressedBlockBuilder
@@ -1034,6 +1061,39 @@
                       ${LIBS})
 add_test(BasicColumnStoreTupleStorageSubBlock_unittest BasicColumnStoreTupleStorageSubBlock_unittest)
 
+add_executable(BloomFilterIndexSubBlock_unittest "${CMAKE_CURRENT_SOURCE_DIR}/tests/BloomFilterIndexSubBlock_unittest.cpp")
+target_link_libraries(BloomFilterIndexSubBlock_unittest
+                      gtest
+                      gtest_main
+                      glog
+                      quickstep_catalog_CatalogAttribute
+                      quickstep_catalog_CatalogRelation
+                      quickstep_catalog_CatalogTypedefs
+                      quickstep_expressions_predicate_ComparisonPredicate
+                      quickstep_expressions_predicate_PredicateCost
+                      quickstep_expressions_scalar_ScalarAttribute
+                      quickstep_expressions_scalar_ScalarLiteral
+                      quickstep_storage_BloomFilterIndexSubBlock
+                      quickstep_storage_StorageBlockInfo
+                      quickstep_storage_StorageBlockLayout_proto
+                      quickstep_storage_TupleIdSequence
+                      quickstep_storage_TupleStorageSubBlock
+                      quickstep_types_CharType
+                      quickstep_types_DoubleType
+                      quickstep_types_FloatType
+                      quickstep_types_LongType
+                      quickstep_types_TypeFactory
+                      quickstep_types_TypeID
+                      quickstep_types_TypedValue
+                      quickstep_types_VarCharType
+                      quickstep_types_containers_Tuple
+                      quickstep_types_operations_comparisons_Comparison
+                      quickstep_types_operations_comparisons_ComparisonFactory
+                      quickstep_types_operations_comparisons_ComparisonID
+                      quickstep_utility_ScopedBuffer
+                      ${LIBS})
+add_test(BloomFilterIndexSubBlock_unittest BloomFilterIndexSubBlock_unittest)
+
 add_executable(CompressedColumnStoreTupleStorageSubBlock_unittest "${CMAKE_CURRENT_SOURCE_DIR}/tests/CompressedColumnStoreTupleStorageSubBlock_unittest.cpp")
 target_link_libraries(CompressedColumnStoreTupleStorageSubBlock_unittest
                       gtest
diff --git a/storage/CSBTreeIndexSubBlock.cpp b/storage/CSBTreeIndexSubBlock.cpp
index e1f835b..8535398 100644
--- a/storage/CSBTreeIndexSubBlock.cpp
+++ b/storage/CSBTreeIndexSubBlock.cpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015-2016 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -353,6 +355,12 @@
   return (5 * key_length) >> 1;
 }
 
+std::size_t CSBTreeIndexSubBlock::EstimateBytesPerBlock(
+    const CatalogRelationSchema &relation,
+    const IndexSubBlockDescription &description) {
+  return kZeroSize;
+}
+
 bool CSBTreeIndexSubBlock::addEntry(const tuple_id tuple) {
   DEBUG_ASSERT(initialized_);
   DEBUG_ASSERT(tuple_store_.hasTupleWithID(tuple));
diff --git a/storage/CSBTreeIndexSubBlock.hpp b/storage/CSBTreeIndexSubBlock.hpp
index f70b7e7..24e2ab5 100644
--- a/storage/CSBTreeIndexSubBlock.hpp
+++ b/storage/CSBTreeIndexSubBlock.hpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015-2016 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -160,6 +162,25 @@
   static std::size_t EstimateBytesPerTuple(const CatalogRelationSchema &relation,
                                            const IndexSubBlockDescription &description);
 
+  /**
+   * @brief Estimate the total number of bytes (including any applicable
+   *        overhead) occupied by this IndexSubBlock within the StorageBlock.
+   *        This function is to be used by those indicies whose occupied size
+   *        in the block does not depend on the number of tuples being indexed.
+   * @warning description must be valid. DescriptionIsValid() should be called
+   *          first if necessary.
+   * @note This function will be invoked by StorageBlockLayout::finalize()
+   *       if and only when EstimateBytesPerTuple() returns a zero size.
+   *
+   * @param relation The relation tuples belong to.
+   * @param description A description of the parameters for this type of
+   *        IndexSubBlock.
+   * @return The total number of bytes occupied by this IndexSubBlock within
+   *         the StorageBlock.
+   **/
+  static std::size_t EstimateBytesPerBlock(const CatalogRelationSchema &relation,
+                                            const IndexSubBlockDescription &description);
+
   IndexSubBlockType getIndexSubBlockType() const override {
     return kCSBTree;
   }
diff --git a/storage/SMAIndexSubBlock.cpp b/storage/SMAIndexSubBlock.cpp
index bd31f2f..2a0e4f9 100644
--- a/storage/SMAIndexSubBlock.cpp
+++ b/storage/SMAIndexSubBlock.cpp
@@ -1,5 +1,7 @@
 /**
  *   Copyright 2016 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -32,6 +34,7 @@
 #include "expressions/scalar/Scalar.hpp"
 #include "expressions/scalar/ScalarAttribute.hpp"
 #include "storage/StorageBlockLayout.pb.h"
+#include "storage/StorageConstants.hpp"
 #include "storage/SubBlockTypeRegistry.hpp"
 #include "storage/TupleIdSequence.hpp"
 #include "storage/TupleStorageSubBlock.hpp"
@@ -488,6 +491,12 @@
   return 1;
 }
 
+std::size_t SMAIndexSubBlock::EstimateBytesPerBlock(
+    const CatalogRelationSchema &relation,
+    const IndexSubBlockDescription &description) {
+  return kZeroSize;
+}
+
 bool SMAIndexSubBlock::bulkAddEntries(const TupleIdSequence &tuples) {
   DCHECK(initialized_);
   if (header_->index_consistent) {
diff --git a/storage/SMAIndexSubBlock.hpp b/storage/SMAIndexSubBlock.hpp
index 35abbe4..71ca75b 100644
--- a/storage/SMAIndexSubBlock.hpp
+++ b/storage/SMAIndexSubBlock.hpp
@@ -1,5 +1,7 @@
 /**
  *   Copyright 2016 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -241,6 +243,24 @@
    **/
   static std::size_t EstimateBytesPerTuple(const CatalogRelationSchema &relation,
                                            const IndexSubBlockDescription &description);
+  /**
+   * @brief Estimate the total number of bytes (including any applicable
+   *        overhead) occupied by this IndexSubBlock within the StorageBlock.
+   *        This function is to be used by those indicies whose occupied size
+   *        in the block does not depend on the number of tuples being indexed.
+   * @warning description must be valid. DescriptionIsValid() should be called
+   *          first if necessary.
+   * @note This function will be invoked by StorageBlockLayout::finalize()
+   *       if and only when EstimateBytesPerTuple() returns a zero size.
+   *
+   * @param relation The relation tuples belong to.
+   * @param description A description of the parameters for this type of
+   *        IndexSubBlock.
+   * @return The total number of bytes occupied by this IndexSubBlock within
+   *         the StorageBlock.
+   **/
+  static std::size_t EstimateBytesPerBlock(const CatalogRelationSchema &relation,
+                                             const IndexSubBlockDescription &description);
 
   /**
    * @return The sub block type.
diff --git a/storage/StorageBlock.cpp b/storage/StorageBlock.cpp
index e9ddb70..2850c9c 100644
--- a/storage/StorageBlock.cpp
+++ b/storage/StorageBlock.cpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015-2016 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -30,6 +32,7 @@
 #include "expressions/predicate/Predicate.hpp"
 #include "expressions/scalar/Scalar.hpp"
 #include "storage/BasicColumnStoreTupleStorageSubBlock.hpp"
+#include "storage/BloomFilterIndexSubBlock.hpp"
 #include "storage/CSBTreeIndexSubBlock.hpp"
 #include "storage/CompressedColumnStoreTupleStorageSubBlock.hpp"
 #include "storage/CompressedPackedRowStoreTupleStorageSubBlock.hpp"
@@ -1018,6 +1021,12 @@
     const std::size_t sub_block_memory_size) {
   DEBUG_ASSERT(description.IsInitialized());
   switch (description.sub_block_type()) {
+    case IndexSubBlockDescription::BLOOM_FILTER:
+      return new BloomFilterIndexSubBlock(tuple_store,
+                                          description,
+                                          new_block,
+                                          sub_block_memory,
+                                          sub_block_memory_size);
     case IndexSubBlockDescription::CSB_TREE:
       return new CSBTreeIndexSubBlock(tuple_store,
                                       description,
diff --git a/storage/StorageBlockLayout.cpp b/storage/StorageBlockLayout.cpp
index 509843c..e28fc55 100644
--- a/storage/StorageBlockLayout.cpp
+++ b/storage/StorageBlockLayout.cpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -114,7 +116,15 @@
   for (int index_num = 0;
        index_num < layout_description_.index_description_size();
        ++index_num) {
-    size_t index_size = (sub_block_space * index_size_factors[index_num]) / estimated_bytes_per_tuple_;
+    size_t index_size = 0;
+    if (index_size_factors[index_num] != kZeroSize) {
+      // Estimated size to be consumed was specified per tuple.
+      index_size = (sub_block_space * index_size_factors[index_num]) / estimated_bytes_per_tuple_;
+    } else {
+      // Some indices define total size per block, instead of defining size per tuple.
+      const IndexSubBlockDescription &index_description = layout_description_.index_description(index_num);
+      index_size = SubBlockTypeRegistry::EstimateBytesPerBlockForIndex(relation_, index_description);
+    }
     block_header_.set_index_size(index_num, index_size);
     allocated_sub_block_space += index_size;
   }
diff --git a/storage/StorageConstants.hpp b/storage/StorageConstants.hpp
index 29a08e4..43996c6 100644
--- a/storage/StorageConstants.hpp
+++ b/storage/StorageConstants.hpp
@@ -93,6 +93,10 @@
 // buckets.
 const double kFixedSizeLinearOpenAddressingHashTableOverflowFactor = 0.0625f;
 
+// A constant that replaces the usage of zero as a magic number
+// to indicate zero-sized blocks or sub-blocks.
+const std::size_t kZeroSize = 0;
+
 /** @} */
 
 }  // namespace quickstep
diff --git a/storage/SubBlockTypeRegistry.cpp b/storage/SubBlockTypeRegistry.cpp
index c2293fe..35ee502 100644
--- a/storage/SubBlockTypeRegistry.cpp
+++ b/storage/SubBlockTypeRegistry.cpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -22,6 +24,8 @@
 #include "storage/StorageBlockLayout.pb.h"
 #include "utility/Macros.hpp"
 
+#include "glog/logging.h"
+
 namespace quickstep {
 
 bool SubBlockTypeRegistry::LayoutDescriptionIsValid(
@@ -106,4 +110,17 @@
   return (*it->second)(relation, description);
 }
 
+std::size_t SubBlockTypeRegistry::EstimateBytesPerBlockForIndex(const CatalogRelationSchema &relation,
+                                                                const IndexSubBlockDescription &description) {
+  DCHECK(description.IsInitialized());
+
+  std::unordered_map<IndexTypeIntegral,
+  IndexEstimateBytesPerBlockFunction>::const_iterator
+  it = Instance()->index_estimate_bytes_per_block_functions_.find(
+      static_cast<IndexTypeIntegral>(description.sub_block_type()));
+  DCHECK(it != Instance()->index_estimate_bytes_per_block_functions_.end());
+
+  return (*it->second)(relation, description);
+}
+
 }  // namespace quickstep
diff --git a/storage/SubBlockTypeRegistry.hpp b/storage/SubBlockTypeRegistry.hpp
index c0e8011..a223e7c 100644
--- a/storage/SubBlockTypeRegistry.hpp
+++ b/storage/SubBlockTypeRegistry.hpp
@@ -1,6 +1,8 @@
 /**
  *   Copyright 2011-2015 Quickstep Technologies LLC.
  *   Copyright 2015 Pivotal Software, Inc.
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
  *
  *   Licensed under the Apache License, Version 2.0 (the "License");
  *   you may not use this file except in compliance with the License.
@@ -54,7 +56,7 @@
  *        QUICKSTEP_DECLARE_SUB_BLOCK_TYPE_REGISTERED() macro in the quickstep
  *        namespace like so:
  *        QUICKSTEP_DECLARE_SUB_BLOCK_TYPE_REGISTERED(PackedRowStoreTupleStorageSubBlock);
- * 
+ *
  * Registration of IndexSubBlock implementations works the same way, except the
  * first macro used should be QUICKSTEP_REGISTER_INDEX() instead of
  * QUICKSTEP_REGISTER_TUPLE_STORE().
@@ -92,6 +94,10 @@
       const CatalogRelationSchema&,
       const IndexSubBlockDescription&);
 
+  typedef std::size_t (*IndexEstimateBytesPerBlockFunction)(
+      const CatalogRelationSchema&,
+      const IndexSubBlockDescription&);
+
   static bool RegisterTupleStoreDescriptionIsValidFunction(
       const TupleStorageSubBlockDescription::TupleStorageSubBlockType sub_block_type,
       TupleStoreDescriptionIsValidFunction function) {
@@ -124,6 +130,14 @@
     return true;
   }
 
+  static bool RegisterIndexEstimateBytesPerBlockFunction(
+      const IndexSubBlockDescription::IndexSubBlockType sub_block_type,
+      IndexEstimateBytesPerBlockFunction function) {
+    Instance()->index_estimate_bytes_per_block_functions_[
+      static_cast<IndexTypeIntegral>(sub_block_type)] = function;
+    return true;
+  }
+
   static bool LayoutDescriptionIsValid(
       const CatalogRelationSchema &relation,
       const StorageBlockLayoutDescription &description);
@@ -136,6 +150,10 @@
       const CatalogRelationSchema &relation,
       const IndexSubBlockDescription &description);
 
+  static std::size_t EstimateBytesPerBlockForIndex(
+      const CatalogRelationSchema &relation,
+      const IndexSubBlockDescription &description);
+
  private:
   std::unordered_map<TupleStoreTypeIntegral,
                      TupleStoreDescriptionIsValidFunction>
@@ -153,6 +171,10 @@
                      IndexEstimateBytesPerTupleFunction>
       index_estimate_bytes_per_tuple_functions_;
 
+  std::unordered_map<IndexTypeIntegral,
+                     IndexEstimateBytesPerTupleFunction>
+      index_estimate_bytes_per_block_functions_;
+
   SubBlockTypeRegistry() {
   }
 
@@ -184,19 +206,23 @@
 }  /* namespace registry */                                                                \
 using registry::classname##_registered
 
-
 #define QUICKSTEP_REGISTER_INDEX(classname, proto_enum_case)                          \
 namespace registry {                                                                  \
   static const bool classname##_desc_registered                                       \
       = quickstep::SubBlockTypeRegistry::RegisterIndexDescriptionIsValidFunction(     \
           IndexSubBlockDescription::proto_enum_case,                                  \
           &classname::DescriptionIsValid);                                            \
-  static const bool classname##_size_registered                                       \
+  static const bool classname##_size_per_tuple_registered                             \
       = quickstep::SubBlockTypeRegistry::RegisterIndexEstimateBytesPerTupleFunction(  \
           IndexSubBlockDescription::proto_enum_case,                                  \
           &classname::EstimateBytesPerTuple);                                         \
+  static const bool classname##_size_per_block_registered                             \
+      = quickstep::SubBlockTypeRegistry::RegisterIndexEstimateBytesPerBlockFunction(  \
+          IndexSubBlockDescription::proto_enum_case,                                  \
+          &classname::EstimateBytesPerBlock);                                         \
   const bool classname##_registered                                                   \
-      = classname##_desc_registered && classname##_size_registered;                   \
+      = classname##_desc_registered && classname##_size_per_tuple_registered          \
+          && classname##_size_per_block_registered;                                   \
   bool classname##_check_registered() { return classname##_registered; }              \
 }  /* namespace registry */                                                           \
 using registry::classname##_registered
diff --git a/storage/tests/BloomFilterIndexSubBlock_unittest.cpp b/storage/tests/BloomFilterIndexSubBlock_unittest.cpp
new file mode 100644
index 0000000..a9feae4
--- /dev/null
+++ b/storage/tests/BloomFilterIndexSubBlock_unittest.cpp
@@ -0,0 +1,443 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   Licensed 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.
+ **/
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <memory>
+#include <sstream>
+#include <string>
+#include <vector>
+
+#include "catalog/CatalogAttribute.hpp"
+#include "catalog/CatalogRelation.hpp"
+#include "catalog/CatalogTypedefs.hpp"
+#include "expressions/predicate/ComparisonPredicate.hpp"
+#include "expressions/predicate/PredicateCost.hpp"
+#include "expressions/scalar/ScalarAttribute.hpp"
+#include "expressions/scalar/ScalarLiteral.hpp"
+#include "storage/BloomFilterIndexSubBlock.hpp"
+#include "storage/StorageBlockInfo.hpp"
+#include "storage/StorageBlockLayout.pb.h"
+#include "storage/TupleIdSequence.hpp"
+#include "storage/tests/MockTupleStorageSubBlock.hpp"
+#include "types/CharType.hpp"
+#include "types/DoubleType.hpp"
+#include "types/FloatType.hpp"
+#include "types/LongType.hpp"
+#include "types/TypeFactory.hpp"
+#include "types/TypeID.hpp"
+#include "types/TypedValue.hpp"
+#include "types/VarCharType.hpp"
+#include "types/containers/Tuple.hpp"
+#include "types/operations/comparisons/Comparison.hpp"
+#include "types/operations/comparisons/ComparisonFactory.hpp"
+#include "types/operations/comparisons/ComparisonID.hpp"
+#include "utility/ScopedBuffer.hpp"
+
+#include "glog/logging.h"
+#include "gtest/gtest.h"
+
+using std::int64_t;
+using std::ostringstream;
+using std::size_t;
+using std::string;
+using std::vector;
+
+namespace quickstep {
+
+class BloomFilterIndexSubBlockTest : public ::testing::Test {
+ protected:
+  static const size_t kIndexSubBlockSize = 0x100000;  // 100 KB
+  static const int64_t kLongAttrNullValue = -55555;
+  static const char kCharAttrNullValue[];
+
+  virtual void SetUp() {
+    // Create a sample relation with a variety of attribute types.
+    relation_.reset(new CatalogRelation(NULL, "TestRelation"));
+
+    CatalogAttribute *long_attr = new CatalogAttribute(relation_.get(),
+                                                       "long_attr",
+                                                       TypeFactory::GetType(kLong, false));
+    ASSERT_EQ(0, relation_->addAttribute(long_attr));
+
+    CatalogAttribute *nullable_long_attr = new CatalogAttribute(relation_.get(),
+                                                                "nullable_long_attr",
+                                                                TypeFactory::GetType(kLong, true));
+    ASSERT_EQ(1, relation_->addAttribute(nullable_long_attr));
+
+    CatalogAttribute *float_attr = new CatalogAttribute(relation_.get(),
+                                                        "float_attr",
+                                                        TypeFactory::GetType(kFloat, false));
+    ASSERT_EQ(2, relation_->addAttribute(float_attr));
+
+    CatalogAttribute *char_attr = new CatalogAttribute(relation_.get(),
+                                                       "char_attr",
+                                                       TypeFactory::GetType(kChar, 4, false));
+    ASSERT_EQ(3, relation_->addAttribute(char_attr));
+
+    CatalogAttribute *nullable_char_attr = new CatalogAttribute(relation_.get(),
+                                                                "nullable_char_attr",
+                                                                TypeFactory::GetType(kChar, 4, true));
+    ASSERT_EQ(4, relation_->addAttribute(nullable_char_attr));
+
+    CatalogAttribute *big_char_attr = new CatalogAttribute(relation_.get(),
+                                                           "big_char_attr",
+                                                           TypeFactory::GetType(kChar, 80, false));
+    ASSERT_EQ(5, relation_->addAttribute(big_char_attr));
+
+    CatalogAttribute *varchar_attr = new CatalogAttribute(relation_.get(),
+                                                          "varchar_attr",
+                                                          TypeFactory::GetType(kVarChar, 8, false));
+    ASSERT_EQ(6, relation_->addAttribute(varchar_attr));
+
+    // Create a MockTupleStorageSubBlock to hold tuples for testing.
+    tuple_store_.reset(new MockTupleStorageSubBlock(*relation_));
+
+    index_memory_.reset();
+    index_description_.reset();
+    index_.reset();
+  }
+
+  void createIndex(const vector<attribute_id> &indexed_attrs, const size_t index_memory_size) {
+    // Make the IndexSubBlockDescription.
+    index_description_.reset(new IndexSubBlockDescription());
+    index_description_->set_sub_block_type(IndexSubBlockDescription::BLOOM_FILTER);
+    for (std::size_t i = 0; i < indexed_attrs.size(); ++i) {
+      index_description_->add_indexed_attribute_ids(indexed_attrs[i]);
+    }
+    index_memory_.reset(index_memory_size);
+    index_.reset(new BloomFilterIndexSubBlock(*tuple_store_,
+                                              *index_description_,
+                                              true,
+                                              index_memory_.get(),
+                                              index_memory_size));
+  }
+
+  // Insert a tuple with the specified attribute values into tuple_store_.
+  tuple_id insertTupleInTupleStore(const int64_t long_val,
+                                   const int64_t nullable_long_val,
+                                   const float float_val,
+                                   const string &char_val,
+                                   const string &nullable_char_val,
+                                   const string &big_char_val,
+                                   const string &varchar_val) {
+    std::vector<TypedValue> attrs;
+
+    attrs.emplace_back(LongType::InstanceNonNullable().makeValue(&long_val));
+
+    if (nullable_long_val == kLongAttrNullValue) {
+      attrs.emplace_back(LongType::InstanceNullable().makeNullValue());
+    } else {
+      attrs.emplace_back(LongType::InstanceNullable().makeValue(&nullable_long_val));
+    }
+
+    attrs.emplace_back(FloatType::InstanceNonNullable().makeValue(&float_val));
+
+    attrs.emplace_back(CharType::InstanceNonNullable(4).makeValue(
+        char_val.c_str(),
+        char_val.size() >= 4 ? 4 : char_val.size() + 1).ensureNotReference());
+
+    if (nullable_char_val == kCharAttrNullValue) {
+      attrs.emplace_back(CharType::InstanceNullable(4).makeNullValue());
+    } else {
+      attrs.emplace_back(CharType::InstanceNonNullable(4).makeValue(
+          nullable_char_val.c_str(),
+          nullable_char_val.size() >= 4 ? 4 : nullable_char_val.size() + 1).ensureNotReference());
+    }
+
+    attrs.emplace_back(CharType::InstanceNonNullable(80).makeValue(
+        big_char_val.c_str(),
+        big_char_val.size() >= 80 ? 80 : big_char_val.size() + 1).ensureNotReference());
+
+    TypedValue varchar_typed_value
+        = VarCharType::InstanceNonNullable(varchar_val.size()).makeValue(
+            varchar_val.c_str(),
+            varchar_val.size() + 1);
+    // Test strings are sometimes longer than 8 characters, so truncate if
+    // needed.
+    varchar_typed_value = VarCharType::InstanceNonNullable(8).coerceValue(
+        varchar_typed_value,
+        VarCharType::InstanceNonNullable(varchar_val.size()));
+    varchar_typed_value.ensureNotReference();
+    attrs.emplace_back(std::move(varchar_typed_value));
+
+    // MockTupleStorageSubBlock takes ownership of new tuple passed in with
+    // addTupleMock() method.
+    return tuple_store_->addTupleMock(new Tuple(std::move(attrs)));
+  }
+
+  // Generate a sample tuple based on 'base_value' and insert in into
+  // tuple_store_. The sample tuple will have long_attr equal to 'base_value',
+  // float_attr equal to 0.25 * base_value, and each of char_attr,
+  // big_char_attr, and varchar_attr equal to the string representation of
+  // 'base_value' with 'string_suffix' appended on to it. If 'generate_nulls'
+  // is true, then both nullable_long_attr and nullable_char_attr will be NULL,
+  // otherwise nullable_long_attr will be equal to 'base_value' and
+  // nullable_char_attr will be equal to the other string values. Returns the
+  // tuple_id of the inserted tuple.
+  tuple_id generateAndInsertTuple(const int64_t base_value,
+                                  const bool generate_nulls,
+                                  const string &string_suffix) {
+    ostringstream string_value_buffer;
+    string_value_buffer << base_value << string_suffix;
+    if (generate_nulls) {
+      return insertTupleInTupleStore(base_value,
+                                     kLongAttrNullValue,
+                                     0.25 * base_value,
+                                     string_value_buffer.str(),
+                                     kCharAttrNullValue,
+                                     string_value_buffer.str(),
+                                     string_value_buffer.str());
+    } else {
+      return insertTupleInTupleStore(base_value,
+                                     base_value,
+                                     0.25 * base_value,
+                                     string_value_buffer.str(),
+                                     string_value_buffer.str(),
+                                     string_value_buffer.str(),
+                                     string_value_buffer.str());
+    }
+  }
+
+  // Create a ComparisonPredicate of the form "attribute comp literal".
+  template <typename AttributeType>
+  ComparisonPredicate* generateNumericComparisonPredicate(
+      const ComparisonID comp,
+      const attribute_id attribute,
+      const typename AttributeType::cpptype literal) {
+    ScalarAttribute *scalar_attribute = new ScalarAttribute(*relation_->getAttributeById(attribute));
+    ScalarLiteral *scalar_literal
+        = new ScalarLiteral(AttributeType::InstanceNonNullable().makeValue(&literal),
+                            AttributeType::InstanceNonNullable());
+    return new ComparisonPredicate(ComparisonFactory::GetComparison(comp), scalar_attribute, scalar_literal);
+  }
+
+  ComparisonPredicate* generateStringComparisonPredicate(
+      const ComparisonID comp,
+      const attribute_id attribute,
+      const string &literal) {
+    ScalarAttribute *scalar_attribute = new ScalarAttribute(*relation_->getAttributeById(attribute));
+    ScalarLiteral *scalar_literal = new ScalarLiteral(
+        VarCharType::InstanceNonNullable(literal.size()).makeValue(
+            literal.c_str(),
+            literal.size() + 1).ensureNotReference(),
+        VarCharType::InstanceNonNullable(literal.size()));
+    return new ComparisonPredicate(ComparisonFactory::GetComparison(comp), scalar_attribute, scalar_literal);
+  }
+
+  bool requiresRebuild() const {
+    CHECK(index_) << "Bloom Filter index not yet built!";
+    return !index_->is_consistent_;
+  }
+
+  std::unique_ptr<CatalogRelation> relation_;
+  std::unique_ptr<MockTupleStorageSubBlock> tuple_store_;
+  ScopedBuffer index_memory_;
+  std::unique_ptr<IndexSubBlockDescription> index_description_;
+  std::unique_ptr<BloomFilterIndexSubBlock> index_;
+};
+
+const char BloomFilterIndexSubBlockTest::kCharAttrNullValue[] = "_NULLSTRING";
+
+TEST_F(BloomFilterIndexSubBlockTest, DescriptionIsValidTest) {
+  std::unique_ptr<IndexSubBlockDescription> index_description_;
+  // valid_attrs contains attribute ids which should register as
+  // a valid DescriptionIsValid.
+  vector<attribute_id> valid_attrs({ 0, 1, 2, 3, 4, 5, 6 });
+  // Try to create an index on each of the attributes. Make sure that each
+  // of the attributes which can be indexed on is marked valid.
+  for (const CatalogAttribute &attr : *relation_) {
+    index_description_.reset(new IndexSubBlockDescription());
+    index_description_->set_sub_block_type(IndexSubBlockDescription::BLOOM_FILTER);
+    index_description_->add_indexed_attribute_ids(attr.getID());
+    if (std::find(valid_attrs.begin(), valid_attrs.end(), attr.getID()) != valid_attrs.end()) {
+      EXPECT_TRUE(BloomFilterIndexSubBlock::DescriptionIsValid(*relation_, *index_description_))
+          << "Expected attribute " << attr.getID() << " to be valid.";
+    } else {
+      EXPECT_FALSE(BloomFilterIndexSubBlock::DescriptionIsValid(*relation_, *index_description_))
+          << "Expected attribute " << attr.getID() << " to be invalid.";
+    }
+  }
+}
+
+TEST_F(BloomFilterIndexSubBlockTest, TestConstructor) {
+  // This test checks the correctness of the index's constructor and destructor.
+  createIndex({0, 1, 2}, kIndexSubBlockSize);
+
+  EXPECT_FALSE(requiresRebuild());
+
+  // Reset will invoke the destructor for the index.
+  index_.reset(nullptr);
+
+  // Creating a block on the same memory should cause the index to retrieve
+  // the previously written values.
+  index_.reset(new BloomFilterIndexSubBlock(*tuple_store_,
+                                            *index_description_,
+                                            false,
+                                            index_memory_.get(),
+                                            kIndexSubBlockSize));
+  EXPECT_FALSE(requiresRebuild());
+}
+
+TEST_F(BloomFilterIndexSubBlockTest, TestRebuild) {
+  // This test checks whether the index is rebuilt correctly
+  // after the index is marked inconsistent.
+  const attribute_id indexed_attr = 0;
+  createIndex({ indexed_attr }, kIndexSubBlockSize);
+  EXPECT_FALSE(requiresRebuild());
+
+  // Insert 1000 tuples in the index.
+  const std::size_t num_tuples = 1000;
+  for (std::size_t i = 0; i < num_tuples; ++i) {
+    generateAndInsertTuple(i, false, "suffix");
+  }
+
+  // Deleting a tuple should mark the index as inconsistent.
+  const tuple_id tuple_to_remove = 100;
+  index_->removeEntry(tuple_to_remove);
+  EXPECT_TRUE(requiresRebuild());
+
+  // Rebuilding the index should mark it consistent.
+  index_->rebuild();
+  EXPECT_FALSE(requiresRebuild());
+}
+
+TEST_F(BloomFilterIndexSubBlockTest, TestGetSelectivity) {
+  // This test checks the following conditions on selectivity:
+  // 1. Selectivity for an inconsistent index should be kSelectivityUnknown,
+  // 2. Selectivity for a false positive should be kSelectivityAll,
+  // 3. Selectivity for a true negative should be kSelectivityNone.
+  const attribute_id indexed_attr = 0;
+  createIndex({ indexed_attr }, kIndexSubBlockSize);
+  EXPECT_FALSE(requiresRebuild());
+
+  const uint64_t indexed_value = 999;
+  const uint64_t non_indexed_value = 9999;
+
+  std::unique_ptr<ComparisonPredicate> indexed_predicate(
+      generateNumericComparisonPredicate<LongType>(
+          ComparisonID::kEqual, indexed_attr, indexed_value));
+
+  std::unique_ptr<ComparisonPredicate> non_indexed_predicate(
+      generateNumericComparisonPredicate<LongType>(
+          ComparisonID::kEqual, indexed_attr, non_indexed_value));
+
+  generateAndInsertTuple(indexed_value, false, "suffix");
+  // Until the tuple is inserted into index, expect the selectivity to be none.
+  EXPECT_EQ(BloomFilterIndexSubBlock::BloomFilterSelectivity::kSelectivityNone,
+            index_->getSelectivityForPredicate(*indexed_predicate));
+
+  index_->addEntry(0);
+  // Once the tuple is inserted into index, expect the selectivity to be all.
+  EXPECT_EQ(BloomFilterIndexSubBlock::BloomFilterSelectivity::kSelectivityAll,
+            index_->getSelectivityForPredicate(*indexed_predicate));
+  // A non-indexed value should not be present in the index.
+  EXPECT_EQ(BloomFilterIndexSubBlock::BloomFilterSelectivity::kSelectivityNone,
+            index_->getSelectivityForPredicate(*non_indexed_predicate));
+
+  index_->removeEntry(0);
+  // Removing an entry makes the index inconsistent and selectivity unknown.
+  EXPECT_EQ(BloomFilterIndexSubBlock::BloomFilterSelectivity::kSelectivityUnknown,
+            index_->getSelectivityForPredicate(*indexed_predicate));
+
+  index_->rebuild();
+  // Once rebuilt, the index is consistent again.
+  EXPECT_EQ(BloomFilterIndexSubBlock::BloomFilterSelectivity::kSelectivityNone,
+            index_->getSelectivityForPredicate(*indexed_predicate));
+}
+
+TEST_F(BloomFilterIndexSubBlockTest, TestEvaluatePredicateCost) {
+  // This test checks the following conditions:
+  // 1. Predicate cost for an inconsistent index should be infinite (maximum),
+  // 2. Predicate cost for false positives should be infinite (maximum),
+  // 3. Predicate cost for true negatives should be constant (minimum).
+  const attribute_id indexed_attr = 0;
+  createIndex({ indexed_attr }, kIndexSubBlockSize);
+  EXPECT_FALSE(requiresRebuild());
+
+  const uint64_t indexed_value = 999;
+  const uint64_t non_indexed_value = 9999;
+
+  std::unique_ptr<ComparisonPredicate> indexed_predicate(
+      generateNumericComparisonPredicate<LongType>(
+          ComparisonID::kEqual, indexed_attr, indexed_value));
+
+  std::unique_ptr<ComparisonPredicate> non_indexed_predicate(
+      generateNumericComparisonPredicate<LongType>(
+          ComparisonID::kEqual, indexed_attr, non_indexed_value));
+
+  generateAndInsertTuple(indexed_value, false, "suffix");
+  // Until the tuple is inserted into index, expect the predicate cost to be constant.
+  EXPECT_EQ(predicate_cost::kConstantTime,
+            index_->estimatePredicateEvaluationCost(*indexed_predicate));
+
+  index_->addEntry(0);
+  // Once the tuple is inserted into index, expect the predicate cost to be infinite.
+  EXPECT_EQ(predicate_cost::kInfinite,
+            index_->estimatePredicateEvaluationCost(*indexed_predicate));
+  // A non-indexed value should not be present in the index.
+  EXPECT_EQ(predicate_cost::kConstantTime,
+            index_->estimatePredicateEvaluationCost(*non_indexed_predicate));
+
+  index_->removeEntry(0);
+  // Removing an entry makes the index inconsistent and predicate cost infinite.
+  EXPECT_EQ(predicate_cost::kInfinite,
+            index_->estimatePredicateEvaluationCost(*indexed_predicate));
+
+  index_->rebuild();
+  // Once rebuilt, the index is consistent again.
+  EXPECT_EQ(predicate_cost::kConstantTime,
+            index_->estimatePredicateEvaluationCost(*indexed_predicate));
+}
+
+TEST_F(BloomFilterIndexSubBlockTest, TestGetMatchesForPredicate) {
+  // This test checks the following conditions:
+  // 1. All tuples are returned for a predicate with false positive match,
+  // 2. No tuples are returned for a predicate with true negative match.
+  const attribute_id indexed_attr = 0;
+  createIndex({ indexed_attr }, kIndexSubBlockSize);
+  EXPECT_FALSE(requiresRebuild());
+
+  const uint64_t indexed_value = 999;
+  const uint64_t non_indexed_value = 9999;
+
+  std::unique_ptr<ComparisonPredicate> indexed_predicate(
+      generateNumericComparisonPredicate<LongType>(
+          ComparisonID::kEqual, indexed_attr, indexed_value));
+
+  std::unique_ptr<ComparisonPredicate> non_indexed_predicate(
+      generateNumericComparisonPredicate<LongType>(
+          ComparisonID::kEqual, indexed_attr, non_indexed_value));
+
+  generateAndInsertTuple(indexed_value, false, "suffix");
+  index_->addEntry(0);
+
+  std::unique_ptr<TupleIdSequence> result;
+  // Expect all tuples to be returned.
+  result.reset(index_->getMatchesForPredicate(*indexed_predicate, nullptr));
+  EXPECT_EQ(static_cast<std::size_t>(tuple_store_->getMaxTupleID() + 1), result->length());
+  EXPECT_EQ(static_cast<std::size_t>(tuple_store_->getMaxTupleID() + 1), result->numTuples());
+
+  // Expect no tuples to be returned.
+  result.reset(index_->getMatchesForPredicate(*non_indexed_predicate, nullptr));
+  EXPECT_EQ(static_cast<std::size_t>(tuple_store_->getMaxTupleID() + 1), result->length());
+  EXPECT_EQ(static_cast<std::size_t>(0), result->numTuples());
+}
+
+}  // namespace quickstep
diff --git a/utility/BloomFilter.hpp b/utility/BloomFilter.hpp
new file mode 100644
index 0000000..1d4fdc7
--- /dev/null
+++ b/utility/BloomFilter.hpp
@@ -0,0 +1,237 @@
+/**
+*   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+*     University of Wisconsin—Madison.
+*
+*   Licensed 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.
+*
+*   The hashing function used by the simple Bloom Filter implementation below
+*   is a slightly modified version of the original hashing function, which was
+*   written by Arash Partow and placed in public domain. The Quickstep team
+*   hereby disclaims the credits to this part of the code.
+**/
+
+#ifndef QUICKSTEP_UTILITY_BLOOM_FILTER_HPP
+#define QUICKSTEP_UTILITY_BLOOM_FILTER_HPP
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+/** \addtogroup Utility
+ *  @{
+ */
+
+/**
+ * @brief A simple Bloom Filter implementation with basic primitives
+ *        based on Partow's Bloom Filter implementation.
+ **/
+class BloomFilter {
+ public:
+  static const uint32_t kNumBitsPerByte = 8;
+
+  /**
+   * @brief Constructor.
+   * @note The ownership of the bit array lies with the caller.
+   *
+   * @param random_seed A random_seed that generates unique hash functions.
+   * @param hash_fn_count The number of hash functions used by this bloom filter.
+   * @param bit_array_size_in_bytes Size of the bit array.
+   * @param bit_array A pointer to the memory region that is used to store bit array.
+   * @param is_initialized A boolean that indicates whether to zero-out the region
+   *                       before use or not.
+   **/
+  BloomFilter(const std::uint64_t random_seed,
+              const std::size_t hash_fn_count,
+              const std::uint64_t bit_array_size_in_bytes,
+              std::uint8_t *bit_array,
+              const bool is_initialized)
+      : hash_fn_count_(hash_fn_count),
+        random_seed_(random_seed) {
+    array_size_ = bit_array_size_in_bytes * kNumBitsPerByte;
+    array_size_in_bytes_ = bit_array_size_in_bytes;
+    bit_array_  = bit_array;  // Owned by the calling method.
+    if (!is_initialized) {
+      reset();
+    }
+    generate_unique_hash_fn();
+  }
+
+  /**
+   * @brief Zeros out the contents of the bit array.
+   **/
+  inline void reset() {
+    // Initialize the bit_array with all zeros.
+    std::fill_n(bit_array_, array_size_in_bytes_, 0x00);
+    inserted_element_count_ = 0;
+  }
+
+  /**
+   * @brief Inserts a given value into the bloom filter.
+   *
+   * @param key_begin A pointer to the value being inserted.
+   * @param length Size of the value being inserted in bytes.
+   */
+  inline void insert(const std::uint8_t *key_begin, const std::size_t &length) {
+    std::size_t bit_index = 0;
+    std::size_t bit = 0;
+    for (std::size_t i = 0; i < hash_fn_count_; ++i) {
+      compute_indices(hash_ap(key_begin, length, hash_fn_[i]), &bit_index, &bit);
+      bit_array_[bit_index / kNumBitsPerByte] |= (1 << bit);
+    }
+    ++inserted_element_count_;
+  }
+
+  /**
+   * @brief Test membership of a given value in the bloom filter.
+   *        If true is returned, then a value may or may not be present in the bloom filter.
+   *        If false is returned, a value is certainly not present in the bloom filter.
+   *
+   * @param key_begin A pointer to the value being tested for membership.
+   * @param length Size of the value being inserted in bytes.
+   */
+  inline bool contains(const std::uint8_t *key_begin, const std::size_t length) const {
+    std::size_t bit_index = 0;
+    std::size_t bit = 0;
+    for (std::size_t i = 0; i < hash_fn_count_; ++i) {
+      compute_indices(hash_ap(key_begin, length, hash_fn_[i]), &bit_index, &bit);
+      if ((bit_array_[bit_index / kNumBitsPerByte] & (1 << bit)) != (1 << bit)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * @brief Return the number of elements currently inserted into bloom filter.
+   *
+   * @return The number of elements inserted into bloom filter.
+   **/
+  inline std::size_t element_count() const {
+    return inserted_element_count_;
+  }
+
+ protected:
+  inline void compute_indices(const std::uint32_t &hash, std::size_t *bit_index, std::size_t *bit) const {
+    *bit_index = hash % array_size_;
+    *bit = *bit_index % kNumBitsPerByte;
+  }
+
+  void generate_unique_hash_fn() {
+    hash_fn_.reserve(hash_fn_count_);
+    const std::uint32_t predef_hash_fn_count = 128;
+    static const std::uint32_t predef_hash_fn[predef_hash_fn_count] = {
+       0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC,
+       0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B,
+       0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66,
+       0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA,
+       0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99,
+       0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33,
+       0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5,
+       0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000,
+       0xB823D5EB, 0xC1191CDF, 0xF623AEB3, 0xDB58499F,
+       0xC8D42E70, 0xB173F616, 0xA91A5967, 0xDA427D63,
+       0xB1E8A2EA, 0xF6C0D155, 0x4909FEA3, 0xA68CC6A7,
+       0xC395E782, 0xA26057EB, 0x0CD5DA28, 0x467C5492,
+       0xF15E6982, 0x61C6FAD3, 0x9615E352, 0x6E9E355A,
+       0x689B563E, 0x0C9831A8, 0x6753C18B, 0xA622689B,
+       0x8CA63C47, 0x42CC2884, 0x8E89919B, 0x6EDBD7D3,
+       0x15B6796C, 0x1D6FDFE4, 0x63FF9092, 0xE7401432,
+       0xEFFE9412, 0xAEAEDF79, 0x9F245A31, 0x83C136FC,
+       0xC3DA4A8C, 0xA5112C8C, 0x5271F491, 0x9A948DAB,
+       0xCEE59A8D, 0xB5F525AB, 0x59D13217, 0x24E7C331,
+       0x697C2103, 0x84B0A460, 0x86156DA9, 0xAEF2AC68,
+       0x23243DA5, 0x3F649643, 0x5FA495A8, 0x67710DF8,
+       0x9A6C499E, 0xDCFB0227, 0x46A43433, 0x1832B07A,
+       0xC46AFF3C, 0xB9C8FFF0, 0xC9500467, 0x34431BDF,
+       0xB652432B, 0xE367F12B, 0x427F4C1B, 0x224C006E,
+       0x2E7E5A89, 0x96F99AA5, 0x0BEB452A, 0x2FD87C39,
+       0x74B2E1FB, 0x222EFD24, 0xF357F60C, 0x440FCB1E,
+       0x8BBE030F, 0x6704DC29, 0x1144D12F, 0x948B1355,
+       0x6D8FD7E9, 0x1C11A014, 0xADD1592F, 0xFB3C712E,
+       0xFC77642F, 0xF9C4CE8C, 0x31312FB9, 0x08B0DD79,
+       0x318FA6E7, 0xC040D23D, 0xC0589AA7, 0x0CA5C075,
+       0xF874B172, 0x0CF914D5, 0x784D3280, 0x4E8CFEBC,
+       0xC569F575, 0xCDB2A091, 0x2CC016B4, 0x5C5F4421
+    };
+    if (hash_fn_count_ <= predef_hash_fn_count) {
+      std::copy(predef_hash_fn, predef_hash_fn + hash_fn_count_, hash_fn_.begin());
+      for (std::uint32_t i = 0; i < hash_fn_.size(); ++i) {
+        hash_fn_[i] = hash_fn_[i] * hash_fn_[(i + 3) % hash_fn_count_] + static_cast<std::uint32_t>(random_seed_);
+      }
+    } else {
+      LOG(FATAL) << "Requested number of hash functions is too large.";
+    }
+  }
+
+  inline std::uint32_t hash_ap(const std::uint8_t *begin, std::size_t remaining_length, std::uint32_t hash) const {
+    const std::uint8_t *itr = begin;
+    std::uint32_t loop = 0;
+    while (remaining_length >= 8) {
+      const std::uint32_t &i1 = *(reinterpret_cast<const std::uint32_t*>(itr)); itr += sizeof(std::uint32_t);
+      const std::uint32_t &i2 = *(reinterpret_cast<const std::uint32_t*>(itr)); itr += sizeof(std::uint32_t);
+      hash ^= (hash <<  7) ^  i1 * (hash >> 3) ^ (~((hash << 11) + (i2 ^ (hash >> 5))));
+      remaining_length -= 8;
+    }
+    if (remaining_length) {
+      if (remaining_length >= 4) {
+        const std::uint32_t &i = *(reinterpret_cast<const std::uint32_t*>(itr));
+        if (loop & 0x01) {
+          hash ^= (hash <<  7) ^  i * (hash >> 3);
+        } else {
+          hash ^= (~((hash << 11) + (i ^ (hash >> 5))));
+        }
+        ++loop;
+        remaining_length -= 4;
+        itr += sizeof(std::uint32_t);
+      }
+      if (remaining_length >= 2) {
+        const std::uint16_t &i = *(reinterpret_cast<const std::uint16_t*>(itr));
+        if (loop & 0x01) {
+          hash ^= (hash <<  7) ^  i * (hash >> 3);
+        } else {
+          hash ^= (~((hash << 11) + (i ^ (hash >> 5))));
+        }
+        ++loop;
+        remaining_length -= 2;
+        itr += sizeof(std::uint16_t);
+      }
+      if (remaining_length) {
+        hash += ((*itr) ^ (hash * 0xA5A5A5A5)) + loop;
+      }
+    }
+    return hash;
+  }
+
+ private:
+  std::vector<std::uint32_t> hash_fn_;
+  std::uint8_t *bit_array_;
+  const std::uint32_t hash_fn_count_;
+  std::uint64_t array_size_;
+  std::uint64_t array_size_in_bytes_;
+  std::uint32_t inserted_element_count_;
+  const std::uint64_t random_seed_;
+
+  DISALLOW_COPY_AND_ASSIGN(BloomFilter);
+};
+
+/** @} */
+
+}  // namespace quickstep
+
+#endif  // QUICKSTEP_UTILITY_BLOOM_FILTER_HPP
diff --git a/utility/CMakeLists.txt b/utility/CMakeLists.txt
index 5906d5a..30f01ef 100644
--- a/utility/CMakeLists.txt
+++ b/utility/CMakeLists.txt
@@ -154,6 +154,7 @@
 add_library(quickstep_utility_Alignment ../empty_src.cpp Alignment.hpp)
 add_library(quickstep_utility_BitManipulation ../empty_src.cpp BitManipulation.hpp)
 add_library(quickstep_utility_BitVector ../empty_src.cpp BitVector.hpp)
+add_library(quickstep_utility_BloomFilter ../empty_src.cpp BloomFilter.hpp)
 add_library(quickstep_utility_CalculateInstalledMemory CalculateInstalledMemory.cpp CalculateInstalledMemory.hpp)
 add_library(quickstep_utility_Cast ../empty_src.cpp Cast.hpp)
 add_library(quickstep_utility_CheckSnprintf ../empty_src.cpp CheckSnprintf.hpp)
@@ -199,6 +200,9 @@
                       glog
                       quickstep_utility_BitManipulation
                       quickstep_utility_Macros)
+target_link_libraries(quickstep_utility_BloomFilter
+                      glog
+                      quickstep_utility_Macros)
 target_link_libraries(quickstep_utility_CalculateInstalledMemory
                       glog)
 target_link_libraries(quickstep_utility_CheckSnprintf
@@ -263,6 +267,7 @@
                       quickstep_utility_Alignment
                       quickstep_utility_BitManipulation
                       quickstep_utility_BitVector
+                      quickstep_utility_BloomFilter
                       quickstep_utility_CalculateInstalledMemory
                       quickstep_utility_Cast
                       quickstep_utility_CheckSnprintf
@@ -298,6 +303,14 @@
                       ${LIBS})
 add_test(BitVector_unittest BitVector_unittest)
 
+add_executable(BloomFilter_unittest "${CMAKE_CURRENT_SOURCE_DIR}/tests/BloomFilter_unittest.cpp")
+target_link_libraries(BloomFilter_unittest
+                      gtest
+                      gtest_main
+                      quickstep_utility_BloomFilter
+                      ${LIBS})
+add_test(BloomFilter_unittest BloomFilter_unittest)
+
 add_executable(CalculateInstalledMemory_unittest "${CMAKE_CURRENT_SOURCE_DIR}/tests/CalculateInstalledMemory_unittest.cpp")
 target_link_libraries(CalculateInstalledMemory_unittest
                       gtest
diff --git a/utility/tests/BloomFilter_unittest.cpp b/utility/tests/BloomFilter_unittest.cpp
new file mode 100644
index 0000000..4d8beae
--- /dev/null
+++ b/utility/tests/BloomFilter_unittest.cpp
@@ -0,0 +1,90 @@
+/**
+ *   Copyright 2016, Quickstep Research Group, Computer Sciences Department,
+ *     University of Wisconsin—Madison.
+ *
+ *   Licensed 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.
+ **/
+
+#include <cstdint>
+#include <memory>
+#include <vector>
+
+#include "utility/BloomFilter.hpp"
+
+#include "gtest/gtest.h"
+
+
+namespace quickstep {
+
+class BloomFilterTest : public ::testing::Test {
+ public:
+  static const std::uint64_t kBloomFilterSeed = 0xA5A5A5A55A5A5A5AULL;
+  static const std::uint32_t kNumberOfHashFunctions = 20;
+  static const std::uint32_t kBloomFilterSize = 100000;  // in bytes.
+};
+
+TEST_F(BloomFilterTest, BloomFilterInsertTest) {
+  // This test inserts an element into a known bloom filter size
+  // with given number of hash functions and initial seed,
+  // and tests whether the expected bits are set or not.
+  std::unique_ptr<std::uint8_t> bit_array;
+  std::unique_ptr<BloomFilter> bloom_filter;
+
+  const std::uint32_t num_hashes = 2;
+  const std::uint32_t bloom_filter_size = 1;
+
+  bit_array.reset(new std::uint8_t[bloom_filter_size]);
+  bloom_filter.reset(new BloomFilter(kBloomFilterSeed,
+                                     num_hashes,
+                                     bloom_filter_size,
+                                     bit_array.get(),
+                                     false));
+
+  const std::uint8_t data = 7u;
+  const std::uint8_t expected_bit_array = 136u;
+  bloom_filter->insert(&data, 1);
+  EXPECT_EQ(*bit_array, expected_bit_array);
+}
+
+TEST_F(BloomFilterTest, BloomFilterContainsTest) {
+  std::unique_ptr<std::uint8_t> bit_array;
+  std::unique_ptr<BloomFilter> bloom_filter;
+
+  bit_array.reset(new std::uint8_t[kBloomFilterSize]);
+  bloom_filter.reset(new BloomFilter(kBloomFilterSeed,
+                                     kNumberOfHashFunctions,
+                                     kBloomFilterSize,
+                                     bit_array.get(),
+                                     false));
+
+  // Insert a set of values in the bloom filter.
+  const std::uint32_t data[] = { 4, 60, 100, 9999 };
+  const std::vector<std::uint32_t> data_vector(data, data + sizeof(data) / sizeof(data[0]));
+  for (const std::uint32_t &value : data_vector) {
+    bloom_filter->insert(reinterpret_cast<const uint8_t*>(&value), sizeof(std::uint32_t));
+  }
+
+  // Test the values, which were inserted, are present in the bloom filter.
+  for (const std::uint32_t &value : data_vector) {
+    EXPECT_TRUE(bloom_filter->contains(reinterpret_cast<const uint8_t*>(&value), sizeof(std::uint32_t)));
+  }
+
+  // Test the values, which were not inserted in the bloom filter, are not present.
+  const std::uint32_t missing[] = { 5, 99, 999, 11111 };
+  const std::vector<std::uint32_t> missing_vector(missing, missing + sizeof(missing) / sizeof(missing[0]));
+  for (const std::uint32_t &value : missing_vector) {
+    EXPECT_FALSE(bloom_filter->contains(reinterpret_cast<const uint8_t*>(&value), sizeof(std::uint32_t)));
+  }
+}
+
+}  // namespace quickstep