messif.pivotselection
Class IncrementalPivotChooser

java.lang.Object
  extended by messif.pivotselection.AbstractPivotChooser
      extended by messif.pivotselection.IncrementalPivotChooser
All Implemented Interfaces:
java.io.Serializable, BucketFilter, BucketFilterAfterAdd, BucketFilterAfterRemove

public class IncrementalPivotChooser
extends AbstractPivotChooser
implements java.io.Serializable, BucketFilterAfterAdd, BucketFilterAfterRemove

Incremental selection of pivots. This pivot chooser is based on the technique called Incremental selection proposed as best in 'Pivot Selection Techniques for Proximity Searching in Metric Spaces` by Benjamin Bustos, Gonzalo Navarro, Edgar Chavez in 2001.

See Also:
Serialized Form

Field Summary
static float BUCKETCHANGE_THRESHOLD_TO_RESELECT
          Reselect sample set when the percentage of the bucket changes (with respect to its occupation) exceeds this constant.
static int SAMPLE_PIVOT_SIZE
          Size of the candidate set of pivots from which the best pivot is picked.
static int SAMPLE_SET_SIZE
          Size of the sample set used to verify the goodness of candidate pivots (used to estimate mu_d)
 
Fields inherited from class messif.pivotselection.AbstractPivotChooser
counterBucketReadBuckets, counterObjectDistComp, counterPivotDistComp, counterPivotReadBuckets, preselectedPivots, sampleProviders
 
Constructor Summary
IncrementalPivotChooser()
          Creates a new instance of IncrementalPivotChooser
 
Method Summary
 void addPivot(LocalAbstractObject newPivot)
          This method appends a new pivot to the currently existing list.
 void filterAfterAdd(LocalAbstractObject object, LocalBucket bucket)
          Filter object after its insertion into a bucket.
 void filterAfterRemove(LocalAbstractObject object, LocalBucket bucket)
          Filter object after its removal from a bucket.
protected  void selectPivot(int pivots, AbstractObjectIterator<? extends LocalAbstractObject> objectIter)
          Selects new pivots.
 
Methods inherited from class messif.pivotselection.AbstractPivotChooser
clear, deregisterSampleProvider, getLastPivot, getNextPivot, getPivot, getPivot, iterator, registerSampleProvider, removeLastPivot, selectPivot, selectPivot, size
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

SAMPLE_SET_SIZE

public static int SAMPLE_SET_SIZE
Size of the sample set used to verify the goodness of candidate pivots (used to estimate mu_d)


SAMPLE_PIVOT_SIZE

public static int SAMPLE_PIVOT_SIZE
Size of the candidate set of pivots from which the best pivot is picked.


BUCKETCHANGE_THRESHOLD_TO_RESELECT

public static float BUCKETCHANGE_THRESHOLD_TO_RESELECT
Reselect sample set when the percentage of the bucket changes (with respect to its occupation) exceeds this constant. By default 20% of the bucket occupation is the threshold. The lower number the more frequent sample sets are reselected.

Constructor Detail

IncrementalPivotChooser

public IncrementalPivotChooser()
Creates a new instance of IncrementalPivotChooser

Method Detail

filterAfterAdd

public void filterAfterAdd(LocalAbstractObject object,
                           LocalBucket bucket)
Description copied from interface: BucketFilterAfterAdd
Filter object after its insertion into a bucket.

Specified by:
filterAfterAdd in interface BucketFilterAfterAdd
Parameters:
object - the inserted object
bucket - bucket, where the object is stored

filterAfterRemove

public void filterAfterRemove(LocalAbstractObject object,
                              LocalBucket bucket)
Description copied from interface: BucketFilterAfterRemove
Filter object after its removal from a bucket.

Specified by:
filterAfterRemove in interface BucketFilterAfterRemove
Parameters:
object - the removed object
bucket - bucket, where the object has been stored

selectPivot

protected void selectPivot(int pivots,
                           AbstractObjectIterator<? extends LocalAbstractObject> objectIter)
Selects new pivots. Implementation of the incremental pivot selection algorithm. This method is not intended to be called directly. It is automatically called from getPivot(int). This pivot selection technique depends on previously selected pivots. The AbstractObjectList with such the pivots can be passed in getPivot(position,addInfo) in addInfo parameter (preferable way) or directly set using setAdditionalInfo() method. If the list of pivots is not passed it is assumed that no pivots were selected. Statistics are maintained automatically.

Specified by:
selectPivot in class AbstractPivotChooser
Parameters:
pivots - number of pivots to generate
objectIter - Iterator over the sample set of objects to choose new pivots from

addPivot

public void addPivot(LocalAbstractObject newPivot)
This method appends a new pivot to the currently existing list.

Overrides:
addPivot in class AbstractPivotChooser
Parameters:
newPivot - The pivot added to the preselected list