org.ajmm.obsearch.index
Class AbstractExtendedPyramidIndex<O extends OB>

java.lang.Object
  org.ajmm.obsearch.index.AbstractPivotIndex<O>
      org.ajmm.obsearch.index.AbstractExtendedPyramidIndex<O>

Type Parameters:

O - The type of object to be stored in the Index.

All Implemented Interfaces:

Index<O>

Direct Known Subclasses:

AbstractPPTree, ExtendedPyramidIndexShort

public abstract class AbstractExtendedPyramidIndex<O extends OB>
extends AbstractPivotIndex<O>

This Index uses the extended pyramid technique and SMAP to store arbitrary objects.

Since:

0.7

Author:

Arnoldo Jose Muller Molina

Field Summary

protected com.sleepycat.je.Database	cDB The database where the pyramid values are stored.
protected static int	HHIGH Used to access the second item of a two item array.
protected static int	HLOW Used to access the first item of a two item array.
protected static int	MAX Used to access the second item of a two item array.
protected static int	MIN Used to access the first item of a two item array.
protected float[]	mp Median points of the extended pyramid technique.

Fields inherited from class org.ajmm.obsearch.index.AbstractPivotIndex

aDB, bDB, cache, CACHE_SIZE, databaseEnvironment, databaseEnvironmentCreation, id, ID_SIZE_BYTES, kDB, pivots, pivotsBytes, pivotsCount, pivotSelector, type

Fields inherited from interface org.ajmm.obsearch.Index

SPORE_FILENAME

Constructor Summary

AbstractExtendedPyramidIndex(java.io.File databaseDirectory, short pivots, PivotSelector<O> pivotSelector, java.lang.Class<O> type)
Constructs an extended pyramid index.

Method Summary

protected void	calculateIndexParameters() Calculates the pyramid's median values.
protected void	centerQuery(float[][] q) Queries are aligned to the center of the space.
protected void	closeC() Closes database C.
protected void	copyQuery(float[][] src, float[][] dest) Copies the contents of query src into dest.
protected cern.colt.list.FloatArrayList[]	createFloatHolders(int size)
protected hep.aida.bin.QuantileBin1D[]	createMedianHolders(long size) Creates pivotsCount QuantileBin1D objects that will be used to calculate the medians of the data.
protected float	extendedPyramidNormalization(float norm, int i) Normalizes a value in the given dimension.
protected abstract float[]	extractTuple(com.sleepycat.bind.tuple.TupleInput in) Extracts the tuple values from in and returns a normalized vector with values ranging from 1 to 0.
protected float[]	generateMinArray(float[][] query) Receives a query and returns a new array generated of calculating min() to each of the elements
protected float	heightOfPoint(float[] tuple, int pyramidNumber) For the given point and the pyramid number we return the height of that point.
protected void	initC() This method will be called by the super class.
protected boolean	intersect(float[][] q, int p, float[] minArray, float[] lowHighResult) Returns true if the given query (min[] and max[]) intersects pyramid p.
int	pyramidOfPoint(float[] tuple) Calculates the pyramid # for the given point.
protected int	pyramidOfPointAux(float[] tuple) For the given tuple, returns the pyramid # for the tuple.
float	pyramidValue(float[] tuple) Returns the pyramid value for the given tuple.
int	totalBoxes() Returns the total number of boxes this index can hold.
protected void	updateFloatHolder(float[] tuple, cern.colt.list.FloatArrayList[] medianHolder)
protected void	updateMedianHolder(float[] tuple, hep.aida.bin.QuantileBin1D[] medianHolder) Updates each median holder with the given float tuple.

Methods inherited from class org.ajmm.obsearch.index.AbstractPivotIndex

assertFrozen, close, createDefaultDatabaseConfig, createPivotsArray, databaseSize, delete, deleteAux, distance, emptyPivotsArray, freeze, getMaxId, getObject, getPivots, getPivotsCount, initCache, initializeAfterSerialization, insert, insertA, insertFromBtoC, insertFrozen, insertInB, insertInDatabase, insertObjectInDatabase, insertUnFrozen, instantiateObject, isFrozen, loadPivots, prepareFreeze, readObject, relocateInitialize, returnSelf, stats, storePivots, toXML, writeSporeFile

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.ajmm.obsearch.Index

exists, getBox

Field Detail

MIN

protected static final int MIN

Used to access the first item of a two item array.

See Also:

Constant Field Values

MAX

protected static final int MAX

Used to access the second item of a two item array.

See Also:

Constant Field Values

HLOW

protected static final int HLOW

Used to access the first item of a two item array. (Used for queries)

See Also:

Constant Field Values

HHIGH

protected static final int HHIGH

Used to access the second item of a two item array. (Used for queries)

See Also:

Constant Field Values

mp

protected float[] mp

Median points of the extended pyramid technique.

cDB

protected transient com.sleepycat.je.Database cDB

The database where the pyramid values are stored.

Constructor Detail

AbstractExtendedPyramidIndex

public AbstractExtendedPyramidIndex(java.io.File databaseDirectory,
                                    short pivots,
                                    PivotSelector<O> pivotSelector,
                                    java.lang.Class<O> type)
                             throws com.sleepycat.je.DatabaseException,
                                    java.io.IOException

Constructs an extended pyramid index.

Parameters:

databaseDirectory - the database directory

pivots - how many pivots will be used

pivotSelector - The pivot selector that will be used by this index.

type - The class of the object O that will be used.

Throws:

com.sleepycat.je.DatabaseException - If a database error occurs.

java.io.IOException - If a serialization issue occurs.

Method Detail

initC

protected final void initC()
                    throws com.sleepycat.je.DatabaseException

This method will be called by the super class. Initializes the C database(s).

Specified by:

initC in class AbstractPivotIndex<O extends OB>

Throws:

com.sleepycat.je.DatabaseException - If a database error occurs.

calculateIndexParameters

protected void calculateIndexParameters()
                                 throws com.sleepycat.je.DatabaseException,
                                        java.lang.IllegalAccessException,
                                        java.lang.InstantiationException,
                                        OutOfRangeException,
                                        OBException

Calculates the pyramid's median values. We basically have to get the median from each dimension and use the median to approximate the center of the data Using Colt's QuantileBin1D to extract the median. It allows an approximate but memory friendly processing! :)

Specified by:

calculateIndexParameters in class AbstractPivotIndex<O extends OB>

Throws:

com.sleepycat.je.DatabaseException - If a database error occurs.

java.lang.IllegalAccessException - If there is a problem when instantiating objects O

java.lang.InstantiationException - If there is a problem when instantiating objects O

OutOfRangeException - If the distance of any object to any other object exceeds the range defined by the user.

OBException - User generated exception

extractTuple

protected abstract float[] extractTuple(com.sleepycat.bind.tuple.TupleInput in)
                                 throws OutOfRangeException

Extracts the tuple values from in and returns a normalized vector with values ranging from 1 to 0. Note that this is first level normalization. The extended pyramid technique algorithm performs another normalization on top of this one.

Parameters:

in - Extracts a tuple from the given byte stream.

Returns:

A float tuple (the input of the pyramid technique)

Throws:

OutOfRangeException - If the distance of any object to any other object exceeds the range defined by the user.

updateMedianHolder

protected final void updateMedianHolder(float[] tuple,
                                        hep.aida.bin.QuantileBin1D[] medianHolder)

Updates each median holder with the given float tuple.

Parameters:

tuple - TupleInput of floats

medianHolder - an array of QuantileBin1D objects used to find an approximate median.

updateFloatHolder

protected final void updateFloatHolder(float[] tuple,
                                       cern.colt.list.FloatArrayList[] medianHolder)

createMedianHolders

protected final hep.aida.bin.QuantileBin1D[] createMedianHolders(long size)

Creates pivotsCount QuantileBin1D objects that will be used to calculate the medians of the data.

Parameters:

size - the size of the data to be processed

Returns:

an array of QuantileBin1D objects

createFloatHolders

protected final cern.colt.list.FloatArrayList[] createFloatHolders(int size)

extendedPyramidNormalization

protected final float extendedPyramidNormalization(float norm,
                                                   int i)

Normalizes a value in the given dimension. The value must have been converted into a float [0,1] before using this method

Parameters:

norm - Normalizes the value in the given dimension

i - Dimension to use.

Returns:

Normalized version of the value.

heightOfPoint

protected final float heightOfPoint(float[] tuple,
                                    int pyramidNumber)

For the given point and the pyramid number we return the height of that point.

Parameters:

tuple - tuple to be processed

pyramidNumber - which pyramid number will be processed.

Returns:

height of the point

pyramidValue

public final float pyramidValue(float[] tuple)

Returns the pyramid value for the given tuple.

Parameters:

Normalized - tuple (first pass)

Returns:

The pyramid value for the given tuple.

pyramidOfPoint

public final int pyramidOfPoint(float[] tuple)

Calculates the pyramid # for the given point.

Parameters:

tuple - Normalized tuple (first pass)

Returns:

The pyramid # for the given tuple

pyramidOfPointAux

protected final int pyramidOfPointAux(float[] tuple)

For the given tuple, returns the pyramid # for the tuple.

Parameters:

tuple - Normalized tuple (first pass)

Returns:

pyramid # for the given tuple

intersect

protected final boolean intersect(float[][] q,
                                  int p,
                                  float[] minArray,
                                  float[] lowHighResult)

Returns true if the given query (min[] and max[]) intersects pyramid p. It also modifies lowHighResult so that we can perform the range accordingly.

Parameters:

q - A query rectangle.

p - The pyramid number

lowHighResult - Where the lowHighResult will be stored.

Returns:

True if rectangle q intersects pyramid p

generateMinArray

protected final float[] generateMinArray(float[][] query)

Receives a query and returns a new array generated of calculating min() to each of the elements

Parameters:

query -

Returns:

The array of the min(qj) for each element of the query

totalBoxes

public int totalBoxes()

Description copied from interface: Index

Returns the total number of boxes this index can hold.

Returns:

The total number of boxes served by this index.

centerQuery

protected final void centerQuery(float[][] q)

Queries are aligned to the center of the space. Aligns the given query to the center of the space.

Parameters:

q - query.

closeC

protected final void closeC()
                     throws com.sleepycat.je.DatabaseException

Closes database C.

Specified by:

closeC in class AbstractPivotIndex<O extends OB>

Throws:

com.sleepycat.je.DatabaseException - If something goes wrong with the DB

copyQuery

protected final void copyQuery(float[][] src,
                               float[][] dest)

Copies the contents of query src into dest.

Parameters:

src - source

dest - destination