|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.hadoop.hbase.util.DynamicByteBloomFilter
public class DynamicByteBloomFilter
Implements a dynamic Bloom filter, as defined in the INFOCOM 2006 paper.
A dynamic Bloom filter (DBF) makes use of a s * m
bit matrix but
each of the s
rows is a standard Bloom filter. The creation
process of a DBF is iterative. At the start, the DBF is a 1 * m
bit matrix, i.e., it is composed of a single standard Bloom filter.
It assumes that nr
elements are recorded in the
initial bit vector, where nr <= n
(n
is
the cardinality of the set A
to record in the filter).
As the size of A
grows during the execution of the application,
several keys must be inserted in the DBF. When inserting a key into the DBF,
one must first get an active Bloom filter in the matrix. A Bloom filter is
active when the number of recorded keys, nr
, is
strictly less than the current cardinality of A
, n
.
If an active Bloom filter is found, the key is inserted and
nr
is incremented by one. On the other hand, if there
is no active Bloom filter, a new one is created (i.e., a new row is added to
the matrix) according to the current size of A
and the element
is added in this new Bloom filter and the nr
value of
this new Bloom filter is set to one. A given key is said to belong to the
DBF if the k
positions are set to one in one of the matrix rows.
Originally created by European Commission One-Lab Project 034819.
A Bloom filter
,
Theory and Network Applications of Dynamic Bloom FiltersField Summary | |
---|---|
protected int |
curKeys
The number of keys recorded in the current Bloom filter. |
protected float |
errorRate
The maximum false positive rate per bloom |
protected int |
hashType
Hash type |
protected int |
keyInterval
Maximum number of keys in a dynamic Bloom filter row. |
protected ByteBloomFilter[] |
matrix
The matrix of Bloom filters (contains bloom data only during writes). |
protected int |
readMatrixSize
expected size of bloom filter matrix (used during reads) |
static int |
VERSION
Current file format version |
Constructor Summary | |
---|---|
DynamicByteBloomFilter(ByteBuffer meta)
Normal read constructor. |
|
DynamicByteBloomFilter(int keyInterval,
float errorRate,
int hashType)
Normal write constructor. |
Method Summary | |
---|---|
void |
add(byte[] buf)
Add the specified binary to the bloom filter. |
void |
add(byte[] buf,
int offset,
int len)
Add the specified binary to the bloom filter. |
void |
allocBloom()
Allocate memory for the bloom filter data. |
void |
compactBloom()
Compact the bloom before writing metadata & data to disk |
boolean |
contains(byte[] buf,
ByteBuffer theBloom)
Check if the specified key is contained in the bloom filter. |
boolean |
contains(byte[] buf,
int offset,
int length,
ByteBuffer theBloom)
Check if the specified key is contained in the bloom filter. |
int |
getByteSize()
|
org.apache.hadoop.io.Writable |
getDataWriter()
Get a writable interface into bloom filter data (actual bloom). |
int |
getKeyCount()
|
int |
getMaxKeys()
|
org.apache.hadoop.io.Writable |
getMetaWriter()
Get a writable interface into bloom filter meta data. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public static final int VERSION
protected final int keyInterval
protected final float errorRate
protected final int hashType
protected int curKeys
protected int readMatrixSize
protected ByteBloomFilter[] matrix
Constructor Detail |
---|
public DynamicByteBloomFilter(ByteBuffer meta) throws IllegalArgumentException
meta
- stored bloom meta data
IllegalArgumentException
- meta data is invalidpublic DynamicByteBloomFilter(int keyInterval, float errorRate, int hashType) throws IllegalArgumentException
errorRate
- hashType
- type of the hashing function (see org.apache.hadoop.util.hash.Hash
).keyInterval
- Maximum number of keys to record per Bloom filter row.
IllegalArgumentException
- The input parameters were invalidMethod Detail |
---|
public void allocBloom()
BloomFilter
allocBloom
in interface BloomFilter
public void add(byte[] buf, int offset, int len)
BloomFilter
add
in interface BloomFilter
buf
- data to be added to the bloomoffset
- offset into the data to be addedlen
- length of the data to be addedpublic void add(byte[] buf)
BloomFilter
add
in interface BloomFilter
buf
- data to be added to the bloompublic boolean contains(byte[] buf, ByteBuffer theBloom)
BloomFilter
contains
in interface BloomFilter
buf
- data to check for existence oftheBloom
- bloom filter data to search
public boolean contains(byte[] buf, int offset, int length, ByteBuffer theBloom)
BloomFilter
contains
in interface BloomFilter
buf
- data to check for existence ofoffset
- offset into the datalength
- length of the datatheBloom
- bloom filter data to search
public int getKeyCount()
getKeyCount
in interface BloomFilter
public int getMaxKeys()
getMaxKeys
in interface BloomFilter
public int getByteSize()
getByteSize
in interface BloomFilter
public void compactBloom()
BloomFilter
compactBloom
in interface BloomFilter
public org.apache.hadoop.io.Writable getMetaWriter()
BloomFilter
getMetaWriter
in interface BloomFilter
public org.apache.hadoop.io.Writable getDataWriter()
BloomFilter
getDataWriter
in interface BloomFilter
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |