net.obsearch.index.sorter
Class AbstractBucketSorter<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>,P extends Projection<P,CP>,CP>

java.lang.Object
  net.obsearch.index.AbstractOBIndex<O>
      net.obsearch.index.pivot.AbstractPivotOBIndex<O>
          net.obsearch.index.bucket.AbstractBucketIndex<O,B,Q,BC>
              net.obsearch.index.sorter.AbstractBucketSorter<O,B,Q,BC,P,CP>

All Implemented Interfaces:

Index<O>

Direct Known Subclasses:

AbstractDistPerm, AbstractSketch64

public abstract class AbstractBucketSorter<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>,P extends Projection<P,CP>,CP>
extends AbstractBucketIndex<O,B,Q,BC>

Nested Class Summary

Nested classes/interfaces inherited from class net.obsearch.index.bucket.AbstractBucketIndex

AbstractBucketIndex.BucketIterator

Field Summary

protected OBCacheByteArray<BC>	bucketCache Cache used for storing buckets
protected int	bucketPivotCount Pivot count for each bucket.
protected hep.aida.bin.StaticBin1D[]	kEstimators Estimators for k ranges.
protected List<CP>	projections We keep here the projections.
protected OBStoreLong	projectionStorage We keep the projection list
protected int[]	userK K configuration that will be used by the user.

Fields inherited from class net.obsearch.index.bucket.AbstractBucketIndex

Buckets

Fields inherited from class net.obsearch.index.pivot.AbstractPivotOBIndex

intrinsicDimensionalityPairs, pivots, pivotSelector

Fields inherited from class net.obsearch.index.AbstractOBIndex

A, fact, isFrozen, stats, type

Fields inherited from interface net.obsearch.Index

ID_SIZE

Constructor Summary

AbstractBucketSorter()

AbstractBucketSorter(Class type, IncrementalPivotSelector pivotSelector, int pivotCount, int bucketPivotCount)

Method Summary

void	bucketStats()
protected abstract CP	bytesToCompactRepresentation(byte[] data)
protected void	calculateEstimators() Calculate the estimators.
void	close() Closes the database.
protected abstract byte[]	compactRepresentationToBytes(CP cp)
int	estimateK(int queryK) Estimate the k needed for a k-nn query.
protected void	freezeDefault()
byte[]	getAddress(B bucket) Gets the byte address of the given object
List<O>	getAllObjects() Returns a list of all the objects of this index.
protected BC	getBucketContainer(byte[] id)
int	getBucketPivotCount()
protected abstract int	getCPSize() Return the compact representation size
double	getExpectedEP()
protected abstract AbstractOBQuery<O>	getKQuery(O object, int k) Returns a k query for the given object.
int[]	getMaxK()
protected abstract Class<CP>	getPInstance()
protected abstract P	getProjection(B b)
void	init(OBStoreFactory fact) Initialize the index.
protected void	initByteArrayBuckets() Initializes the bucket byte array storage.
protected void	initCache() Initializes the object cache AbstractOBIndex.aCache.
protected OperationStatus	insertBucket(B b, O object) Stores the given bucket b into the AbstractBucketIndex.Buckets storage device.
protected OperationStatus	insertBucketBulk(B b, O object) Stores the given bucket b into the AbstractBucketIndex.Buckets storage device.
protected void	loadMasks() Load the masks from the storage device into memory.
protected void	maxKEstimation() Sort all masks, and then start the search until the CompoundError is less than some threshold.
protected abstract void	maxKEstimationAux(O object) Estimate ks for the given query object and the given list of objects.
protected String	printEstimation(int i)
protected List<P>	searchBuckets(P query, int maxF) Search the f closest buckets to the given query.
void	setExpectedError(double ep) Set the expected NN error
void	setKAlpha(float kAlpha) For a query k we take the kEstimators[k] estimation and return the value kEstimators[k].mean() + (kEstimators[k].stdDev() * kAlpha) This method sets kAlpha.
void	setMaxK(int[] maxK) Set the k values used by this index.
void	setSampleSize(int size) Set the sample size of the estimation
protected abstract void	updateDistance(P query, CP proj, FixedPriorityQueue<P> queue) Calculates the distance between a query and some projection

Methods inherited from class net.obsearch.index.bucket.AbstractBucketIndex

debug, deleteAux, exists, getBucket, getBuckets, getObjectFreeze, idMap, insertAux, insertAuxBulk, instantiateBucketContainer, iterateBuckets, primitiveDataTypeSize

Methods inherited from class net.obsearch.index.pivot.AbstractPivotOBIndex

calculateIntrinsicDimensionality, createPivotsArray, freeze, getObjects, getPivotCount, selectPivots

Methods inherited from class net.obsearch.index.AbstractOBIndex

assertFrozen, bytesToObject, bytesToObject, clearACache, databaseSize, delete, distance, emptyPivotsArray, findAux, getBox, getObject, getStats, getType, initStorageDevices, insert, insert, insertBulk, insertBulk, intrinsicDimensionality, isFrozen, isPreFreeze, isPreFreezeCheck, loadObject, loadPivots, objectToByteBuffer, objectToBytes, resetStats, serializePivots, setFixedRecord, setFixedRecord, setIdAutoGeneration, setPreFreeze, setPreFreezeCheck, totalBoxes

Methods inherited from class java.lang.Object

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

Field Detail

kEstimators

protected hep.aida.bin.StaticBin1D[] kEstimators

Estimators for k ranges. This object tells us the amount of buckets we should read for a given k query to match a certain value of error.

userK

protected int[] userK

K configuration that will be used by the user.

projectionStorage

protected transient OBStoreLong projectionStorage

We keep the projection list

projections

protected transient List<CP> projections

We keep here the projections.

bucketCache

protected transient OBCacheByteArray<BC extends BucketContainer<O,B,Q>> bucketCache

Cache used for storing buckets

bucketPivotCount

protected int bucketPivotCount

Pivot count for each bucket.

Constructor Detail

AbstractBucketSorter

public AbstractBucketSorter(Class type,
                            IncrementalPivotSelector pivotSelector,
                            int pivotCount,
                            int bucketPivotCount)
                     throws OBStorageException,
                            OBException

Throws:

OBStorageException

OBException

AbstractBucketSorter

public AbstractBucketSorter()

Method Detail

setKAlpha

public void setKAlpha(float kAlpha)

For a query k we take the kEstimators[k] estimation and return the value kEstimators[k].mean() + (kEstimators[k].stdDev() * kAlpha) This method sets kAlpha.

Parameters:

kAlpha - new kAlpha to set.

setMaxK

public void setMaxK(int[] maxK)

Set the k values used by this index.

Parameters:

userK -

setSampleSize

public void setSampleSize(int size)

Set the sample size of the estimation

Parameters:

size - the new size

getAddress

public byte[] getAddress(B bucket)
                  throws OBException

Description copied from class: AbstractBucketIndex

Gets the byte address of the given object

Specified by:

getAddress in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Returns:

The rosa filter value of the given object.

Throws:

OBException

getProjection

protected abstract P getProjection(B b)
                                                     throws OBException

Throws:

OBException

compactRepresentationToBytes

protected abstract byte[] compactRepresentationToBytes(CP cp)

bytesToCompactRepresentation

protected abstract CP bytesToCompactRepresentation(byte[] data)

getPInstance

protected abstract Class<CP> getPInstance()

loadMasks

protected void loadMasks()
                  throws OBException

Load the masks from the storage device into memory.

Throws:

OBException

updateDistance

protected abstract void updateDistance(P query,
                                       CP proj,
                                       FixedPriorityQueue<P> queue)

Calculates the distance between a query and some projection

Parameters:

query -

searchBuckets

protected List<P> searchBuckets(P query,
                                int maxF)
                                                  throws InstantiationException,
                                                         IllegalAccessException,
                                                         OBException

Search the f closest buckets to the given query. We drop the distance values for performance reasons, but we could add them if we wanted in the future.

Parameters:

query - the query to employ

maxF - the max number of items that will be returned

Returns:

Throws:

InstantiationException

IllegalAccessException

OBException

init

public void init(OBStoreFactory fact)
          throws OBStorageException,
                 OBException,
                 InstantiationException,
                 IllegalAccessException

Description copied from class: AbstractOBIndex

Initialize the index.

Specified by:

init in interface Index<O extends OB>

Overrides:

init in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Parameters:

fact - The storage factory that will be used to store the data.

Throws:

OBStorageException - If something goes wrong with the DB

OBException - User generated exception

NotFrozenException - if the index has not been frozen.

InstantiationException - If there is a problem when instantiating objects O

IllegalAccessException - If there is a problem when instantiating objects O

getBucketContainer

protected BC getBucketContainer(byte[] id)
                                                        throws OBException,
                                                               InstantiationException,
                                                               IllegalAccessException

Overrides:

getBucketContainer in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Throws:

OBException

InstantiationException

IllegalAccessException

initByteArrayBuckets

protected void initByteArrayBuckets()
                             throws OBException

Description copied from class: AbstractBucketIndex

Initializes the bucket byte array storage. To be called by the init procedure.

Overrides:

initByteArrayBuckets in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Throws:

OBException

getCPSize

protected abstract int getCPSize()

Return the compact representation size

Returns:

setExpectedError

public void setExpectedError(double ep)

Set the expected NN error

Parameters:

ep - CompoundError value.

calculateEstimators

protected void calculateEstimators()
                            throws IllegalIdException,
                                   OBException,
                                   IllegalAccessException,
                                   InstantiationException

Calculate the estimators.

Throws:

IllegalIdException

OBException

IllegalAccessException

InstantiationException

maxKEstimation

protected void maxKEstimation()
                       throws IllegalIdException,
                              OBException,
                              IllegalAccessException,
                              InstantiationException

Sort all masks, and then start the search until the CompoundError is less than some threshold. Do this for each k.

Throws:

IllegalIdException

OBException

IllegalAccessException

InstantiationException

printEstimation

protected String printEstimation(int i)

insertBucket

protected OperationStatus insertBucket(B b,
                                       O object)
                                throws OBStorageException,
                                       IllegalIdException,
                                       IllegalAccessException,
                                       InstantiationException,
                                       OutOfRangeException,
                                       OBException

Stores the given bucket b into the AbstractBucketIndex.Buckets storage device. The given bucket b should have been returned by #getBucket(OB, int)

Overrides:

insertBucket in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Parameters:

b - The bucket in which we will insert the object.

object - The object to insert.

Returns:

A OperationStatus object with the new id of the object if the object was inserted successfully.

Throws:

OBStorageException

IllegalIdException

IllegalAccessException

InstantiationException

OutOfRangeException

OBException

insertBucketBulk

protected OperationStatus insertBucketBulk(B b,
                                           O object)
                                    throws OBStorageException,
                                           IllegalIdException,
                                           IllegalAccessException,
                                           InstantiationException,
                                           OutOfRangeException,
                                           OBException

Stores the given bucket b into the AbstractBucketIndex.Buckets storage device. The given bucket b should have been returned by #getBucket(OB, int) No checks are performed, we simply add the objects believing they are unique.

Overrides:

insertBucketBulk in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Parameters:

b - The bucket in which we will insert the object.

object - The object to insert.

Returns:

A OperationStatus object with the new id of the object if the object was inserted successfully.

Throws:

OBStorageException

IllegalIdException

IllegalAccessException

InstantiationException

OutOfRangeException

OBException

freezeDefault

protected void freezeDefault()
                      throws AlreadyFrozenException,
                             IllegalIdException,
                             IllegalAccessException,
                             InstantiationException,
                             OutOfRangeException,
                             OBException

Overrides:

freezeDefault in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Throws:

AlreadyFrozenException

IllegalIdException

IllegalAccessException

InstantiationException

OutOfRangeException

OBException

close

public void close()
           throws OBException

Description copied from interface: Index

Closes the database.

Specified by:

close in interface Index<O extends OB>

Overrides:

close in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Throws:

OBStorageException - If something goes wrong with the DB.

OBException

getKQuery

protected abstract AbstractOBQuery<O> getKQuery(O object,
                                                int k)
                                                    throws OBException,
                                                           InstantiationException,
                                                           IllegalAccessException

Returns a k query for the given object.

Parameters:

object - (query object)

k - the number of objects to accept in the query.

Returns:

Throws:

IllegalAccessException

InstantiationException

OBException

getAllObjects

public List<O> getAllObjects()
                                 throws IllegalIdException,
                                        IllegalAccessException,
                                        InstantiationException,
                                        OBException

Returns a list of all the objects of this index.

Returns:

a list of all the objects of this index.

Throws:

OBException

InstantiationException

IllegalAccessException

IllegalIdException

initCache

protected void initCache()
                  throws OBException

Description copied from class: AbstractOBIndex

Initializes the object cache AbstractOBIndex.aCache.

Overrides:

initCache in class AbstractOBIndex<O extends OB>

Throws:

OBException

maxKEstimationAux

protected abstract void maxKEstimationAux(O object)
                                   throws OBException,
                                          InstantiationException,
                                          IllegalAccessException

Estimate ks for the given query object and the given list of objects.

Parameters:

object -

objects -

Throws:

OBException

InstantiationException

IllegalAccessException

estimateK

public int estimateK(int queryK)
              throws OBException

Estimate the k needed for a k-nn query.

Parameters:

queryK - k of the k-nn query.

Returns:

Number of buckets that should be retrieved for this query.

Throws:

OBException

getMaxK

public int[] getMaxK()

getExpectedEP

public double getExpectedEP()

getBucketPivotCount

public int getBucketPivotCount()

bucketStats

public void bucketStats()
                 throws OBStorageException,
                        IllegalIdException,
                        IllegalAccessException,
                        InstantiationException,
                        OBException

Overrides:

bucketStats in class AbstractBucketIndex<O extends OB,B extends BucketObject<O>,Q,BC extends BucketContainer<O,B,Q>>

Throws:

OBStorageException

IllegalIdException

IllegalAccessException

InstantiationException

OBException