net.obsearch.pivots.bustos
Class AbstractIncrementalBustosNavarroChavez<O extends OB>

java.lang.Object
  net.obsearch.pivots.AbstractIncrementalPivotSelector<O>
      net.obsearch.pivots.bustos.AbstractIncrementalBustosNavarroChavez<O>

Direct Known Subclasses:

IncrementalBustosNavarroChavezByte, IncrementalBustosNavarroChavezDouble, IncrementalBustosNavarroChavezFloat, IncrementalBustosNavarroChavezInt, IncrementalBustosNavarroChavezLong, IncrementalBustosNavarroChavezShort

public abstract class AbstractIncrementalBustosNavarroChavez<O extends OB>
extends AbstractIncrementalPivotSelector<O>

IncrementalBustosNavarroChavez implements the pivot selection described here: Pivot Selection Techniques for Proximity Searching in Metric Spaces (2001) Benjamin Bustos, Gonzalo Navarro, Edgar Chavez The idea was also suggested by Zezula et all in their book "Similarity Search: The Metric Space Approach"

Author:

Arnoldo Jose Muller Molina

Field Summary

Fields inherited from class net.obsearch.pivots.AbstractIncrementalPivotSelector

pivotable, r

Constructor Summary

protected

AbstractIncrementalBustosNavarroChavez(Pivotable<O> pivotable, int l, int m) Receives the object that accepts pivots as possible candidates.

Method Summary

protected abstract double	calculateMedian(long[] pivots, long[] x, long[] y, Index<O> index) Calculates the median of L-inf(x[i], y[i]) based on pivots
PivotResult	generatePivots(int pivotCount, cern.colt.list.LongArrayList elements, Index<O> index)
protected abstract void	resetCache(int l) Resets the internal cache.
protected abstract boolean	validatePivots(long[] pivots, long id, Index<O> index) Validates that the lower layers have been processing everything fine.

Methods inherited from class net.obsearch.pivots.AbstractIncrementalPivotSelector

enableAcceptRepeated, generatePivots, getObject, mapId, max, select, selectO, selectUnique

Methods inherited from class java.lang.Object

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

Constructor Detail

AbstractIncrementalBustosNavarroChavez

protected AbstractIncrementalBustosNavarroChavez(Pivotable<O> pivotable,
                                                 int l,
                                                 int m)

Receives the object that accepts pivots as possible candidates. Selects l pairs of objects to compare which set of pivots is better, and selects m possible pivot candidates from the data set.

Parameters:

pivotable -

l -

m -

Method Detail

resetCache

protected abstract void resetCache(int l)

Resets the internal cache.

generatePivots

public PivotResult generatePivots(int pivotCount,
                                  cern.colt.list.LongArrayList elements,
                                  Index<O> index)
                           throws OBException,
                                  IllegalAccessException,
                                  InstantiationException,
                                  OBStorageException,
                                  PivotsUnavailableException

Specified by:

generatePivots in class AbstractIncrementalPivotSelector<O extends OB>

Throws:

OBException

IllegalAccessException

InstantiationException

OBStorageException

PivotsUnavailableException

validatePivots

protected abstract boolean validatePivots(long[] pivots,
                                          long id,
                                          Index<O> index)
                                   throws com.sleepycat.je.DatabaseException,
                                          IllegalIdException,
                                          IllegalAccessException,
                                          InstantiationException,
                                          OBException

Validates that the lower layers have been processing everything fine.

Parameters:

pivots - the pivots that were selected

id - Id of the object

index - Index from which we will load objects.

Throws:

com.sleepycat.je.DatabaseException

IllegalIdException

IllegalAccessException

InstantiationException

OBException

calculateMedian

protected abstract double calculateMedian(long[] pivots,
                                          long[] x,
                                          long[] y,
                                          Index<O> index)
                                   throws com.sleepycat.je.DatabaseException,
                                          IllegalIdException,
                                          IllegalAccessException,
                                          InstantiationException,
                                          OBException

Calculates the median of L-inf(x[i], y[i]) based on pivots

Parameters:

pivots - The pivots used to map the space

x - The left part of the pair

y - The right part of the pair.

index - The underlying index (used to extract the objects and calculate the distances)

Throws:

com.sleepycat.je.DatabaseException

IllegalIdException

IllegalAccessException

InstantiationException

OBException