Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.archive.crawler.util
Class BloomUriUniqFilter

    java.lang.Object
      org.archive.crawler.util.SetBasedUriUniqFilter
          org.archive.crawler.util.BloomUriUniqFilter

All Implemented Interfaces:
  java.io.Serializable, UriUniqFilter

    public class BloomUriUniqFilter

extends SetBasedUriUniqFilter
implements java.io.Serializable

A MG4J BloomFilter-based implementation of an AlreadySeen list. This implementation performs adequately without blowing out the heap through to very large numbers of URIs. See AlreadySeen. It is inherent to Bloom filters that as they get 'saturated', their false-positive rate rises. The default parameters used by this class attempt to maintain a 1-in-4 million (1 in 2^22) false-positive chance through 125 million unique inserts, which creates a filter structure about 495MB in size. You may use the following system properties to tune the size and false-positive rate of the bloom filter structure used by this class: org.archive.crawler.util.BloomUriUniqFilter.expected-size (default 125000000) org.archive.crawler.util.BloomUriUniqFilter.hash-count (default 22) The resulting filter will take up approximately... 1.44 * expected-size * hash-count / 8 ...bytes. The default size is very close to the maximum practical size of the Bloom filter implementation, BloomFilter32bitSplit, created in the initialize() method, due to integer arithmetic limits. If you need a larger filter, you should edit the initialize method to intantiate a BloomFilter64bit instead.

Version:
  $Date: 2006-09-22 18:39:39 +0000 (Fri, 22 Sep 2006) $, $Revision: 4647 $
Author:
  gojomo
See Also:
  Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from interface org.archive.crawler.datamodel.UriUniqFilter
`UriUniqFilter.HasUriReceiver`

Field Summary
`(package private) BloomFilter` | `bloom`
`protected int` | `expected_n`
`protected static java.lang.String` | `EXPECTED_SIZE_KEY`
`protected static java.lang.String` | `HASH_COUNT_KEY`

Fields inherited from class org.archive.crawler.util.SetBasedUriUniqFilter
`duplicateCount, duplicatesAtLastSample, profileLog, receiver`

Constructor Summary
`BloomUriUniqFilter()` Default constructor
`BloomUriUniqFilter(int n, int d)` Constructor.

Method Summary
`void` | `forget(java.lang.String canonical, CandidateURI item)` Forget item was seen
`protected void` | `initialize(int n, int d)` Initializer shared by constructors.
`protected boolean` | `setAdd(java.lang.CharSequence uri)`
`protected long` | `setCount()`
`protected boolean` | `setRemove(java.lang.CharSequence uri)`

Methods inherited from class org.archive.crawler.util.SetBasedUriUniqFilter
`add, addForce, addNow, close, count, note, pending, profileLog, requestFlush, setDestination, setProfileLog`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### bloom

    BloomFilter bloom

### expected_n

    protected int expected_n

### EXPECTED_SIZE_KEY

    protected static final java.lang.String EXPECTED_SIZE_KEY

See Also:
  Constant Field Values

### HASH_COUNT_KEY

    protected static final java.lang.String HASH_COUNT_KEY

See Also:
  Constant Field Values

Constructor Detail

### BloomUriUniqFilter

    public BloomUriUniqFilter()

  Default constructor

### BloomUriUniqFilter

    public BloomUriUniqFilter(int n,
                              int d)

  Constructor.

  Parameters:
    `n` - the expected number of elements.
    `d` - the number of hash functions; if the filter adds not more than `n` elements, false positives will happen with probability 2-d.

Method Detail

### initialize

    protected void initialize(int n,
                              int d)

  Initializer shared by constructors.

  Parameters:
    `n` - the expected number of elements.
    `d` - the number of hash functions; if the filter adds not more than `n` elements, false positives will happen with probability 2-d.

### forget

    public void forget(java.lang.String canonical,
                       CandidateURI item)

  Description copied from interface: `UriUniqFilter`
  Forget item was seen

  Specified by:
    `forget` in interface `UriUniqFilter`
  Overrides:
    `forget` in class `SetBasedUriUniqFilter`
  Parameters:
    `canonical` - Usually a canonicalized version of an `URI`. This is the key used doing lookups, forgets and insertions on the already included list.
    `item` - item to add.

### setAdd

    protected boolean setAdd(java.lang.CharSequence uri)

  Specified by:
    `setAdd` in class `SetBasedUriUniqFilter`

### setCount

    protected long setCount()

  Specified by:
    `setCount` in class `SetBasedUriUniqFilter`

### setRemove

    protected boolean setRemove(java.lang.CharSequence uri)

  Specified by:
    `setRemove` in class `SetBasedUriUniqFilter`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2003-2008 Internet Archive. All Rights Reserved.