com.bigdata.btree

Class TestBloomFilter

java.lang.Object

junit.framework.Assert

junit.framework.TestCase

junit.framework.TestCase2

com.bigdata.btree.TestBloomFilter

All Implemented Interfaces:

junit.framework.Test

public class TestBloomFilter
extends TestCase2

Test suite for bloom filter functionality.

Version:

$Id$

Author:

Bryan Thompson

See Also:

BloomFilter

Nested Class Summary

Nested classes/interfaces inherited from class junit.framework.TestCase2

TestCase2.MyProperties, TestCase2.RandomType

Field Summary

Fields inherited from class junit.framework.TestCase2

_randomType, log

Constructor Summary

Constructors

Constructor and Description
TestBloomFilter()
TestBloomFilter(String name)

Method Summary

Methods

Modifier and Type	Method and Description
void	test_ctor_correctRejection() Correct rejection tests.
void	test_ctor() Simple constructor tests
void	test_errorRate() Test that a bloom filter constructed for a given #of keys and maximum error rate respects that maximum error rate in practice.
void	test_errorRateCurve() Generates a table showing the #of index entries that would produce a given error rate for a filter with a specific configuration (target error rate of .02 at 1 million index entries).
void	test_serialization() Test suite for (de-)serialization of the BloomFilter.
void	test_spaceCurve() This is not really a unit test.

Methods inherited from class junit.framework.TestCase2

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEqualsWithinUlps, assertSameArray, assertSameArray, assertSameBigDecimal, assertSameBigDecimal, assertSameBigInteger, assertSameBigInteger, assertSameIterator, assertSameIterator, assertSameIteratorAnyOrder, assertSameIteratorAnyOrder, assertSameValue, assertSameValue, assertZeroUlps, assertZeroUlps, fail, getInnerCause, getNormalInt, getProjectBuildPath, getProperties, getRandomObject, getRandomObject, getRandomOrder, getRandomString, getTestInputStream, getTestResource, getTestResource, getUlps, getUlps, isDEBUG, isDEBUG, isINFO, isINFO, isInnerCause, logProperties

Methods inherited from class junit.framework.TestCase

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, countTestCases, createResult, fail, fail, failNotEquals, failNotSame, failSame, format, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

TestBloomFilter

public TestBloomFilter()

TestBloomFilter

public TestBloomFilter(String name)

Parameters:

name -

Method Detail

test_ctor

public void test_ctor()

Simple constructor tests

test_ctor_correctRejection

public void test_ctor_correctRejection()

Correct rejection tests.

test_errorRate

public void test_errorRate()

Test that a bloom filter constructed for a given #of keys and maximum error rate respects that maximum error rate in practice.

test_spaceCurve

public void test_spaceCurve()

This is not really a unit test. Instead it plots a curve of the space requirements of the filter (bitLength) against the target error rate and filter capacity.

Note: The table has spans within each column where the same bit length is computed. This is because the #of hash functions is discrete. Each time we increase the #of hash functions the table moves to a new bit length value in a given column.

test_errorRateCurve

public void test_errorRateCurve()

Generates a table showing the #of index entries that would produce a given error rate for a filter with a specific configuration (target error rate of .02 at 1 million index entries). The code uses the given filter and runs through error rates between .02 and .20 by increments of .01 showing the #of index entries for which that would be the expected error rate.

You can verify the computation by examining certain entries in the table generated by test_spaceCurve(). The filter as configured for this test has a bit length of 8,656,171. If you look at the expected error rate for a bloom filter of 2 million index entries of the same bit length you will see that it lies somewhere in 0.13 - 0.24 (this table has discrete regions, see the javadoc for test_spaceCurve()). If you examine the output of this test, you will see that an error rate of 0.18 is predicated when the #of index entries is on the order of 2 million (2,008,182). The relevant cells are highlighted in the worksheet.

See Also:

src/worksheet/architecture/bloomfilter.xls, BloomFilter#getEntryCountForErrorRate(double)

test_serialization

public void test_serialization()

Test suite for (de-)serialization of the BloomFilter.