messif.algorithms.impl
Class SequentialScan

java.lang.Object
  extended by messif.algorithms.Algorithm
      extended by messif.algorithms.impl.SequentialScan
All Implemented Interfaces:
java.io.Serializable

public class SequentialScan
extends Algorithm

Implementation of the naive sequential scan algorithm. It uses one bucket to store objects and performs operations on the bucket. It also supports pivot-based filtering. The pivots can be specified in a constructor.

See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class messif.algorithms.Algorithm
Algorithm.AlgorithmConstructor
 
Field Summary
protected  LocalBucket bucket
          One instance of bucket where all objects are stored
protected  boolean pivotDistsValidIfGiven
          Flag controlling the usage of PrecomputedDistancesFixedArrayFilter -- whether distances are set or appended (see the constructor below for details)
protected  AbstractObjectList<LocalAbstractObject> pivots
          A list of fixed pivots used for filtering
 
Fields inherited from class messif.algorithms.Algorithm
log, maximalConcurrentOperations
 
Constructor Summary
SequentialScan()
          Creates a new instance of SequantialScan access structure with the default MemoryStorageBucket class.
SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass)
          Creates a new instance of SequantialScan access structure with specific bucket class.
SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass, AbstractObjectIterator<LocalAbstractObject> pivotIter, int pivotCount, boolean pivotDistsValidIfGiven)
          Creates a new instance of SequantialScan access structure with specific bucket class and filtering pivots.
SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass, java.util.Map<java.lang.String,java.lang.Object> bucketClassParams)
          Creates a new instance of SequantialScan access structure with specific bucket class.
SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass, java.util.Map<java.lang.String,java.lang.Object> bucketClassParams, AbstractObjectIterator<LocalAbstractObject> pivotIter, int pivotCount, boolean pivotDistsValidIfGiven)
          Creates a new instance of SequantialScan access structure with specific bucket class and filtering pivots.
 
Method Summary
protected  void addPrecompDist(LocalAbstractObject object)
          Add precomputed distances to a given object.
 void approxKNNSearch(ApproxKNNQueryOperation operation)
          Performs the approximate k-nearest neighbor search operation with given ApproxKNNQueryOperation object.
 void bulkInsert(BulkInsertOperation operation)
          Bulk insertion.
 void delete(DeleteByLocatorOperation operation)
          Deletes objects by locators.
 void delete(DeleteOperation operation)
          Deletes an object.
 void destroy()
          Destroy this algorithm.
 void finalize()
          Finalize the algorithm.
 void incrementalNNSearch(IncrementalNNQueryOperation operation)
          Performs the incremental nearest neighbor search operation with given IncrementalNNQueryOperation object.
 void insert(InsertOperation operation)
          Inserts a new object.
 void knnSearch(KNNQueryOperation operation)
          Performs the k-nearest neighbor search operation with given KNNQueryOperation object.
 void rangeSearch(RangeQueryOperation operation)
          Performs the range search operation with given RangeQueryOperation object.
 void search(QueryOperation<?> operation)
          Performs a generic query operation.
 java.lang.String toString()
          Converts the object to a string representation
 
Methods inherited from class messif.algorithms.Algorithm
backgroundExecute, backgroundExecuteOperation, backgroundExecuteOperation, execute, executeOperation, getAnnotatedConstructors, getConstructorArgumentDescriptions, getConstructorDescription, getConstructorDescriptionSimple, getExecutorParamClasses, getFirstSupportedOperation, getName, getObjectClass, getOperationStatistics, getQueryAnswer, getQueryAnswer, getRunningOperationsCount, getSupportedOperations, getSupportedOperations, resetOperationStatistics, restoreFromFile, restoreFromFile, statisticsAfterOperation, statisticsBeforeOperation, storeToFile, waitBackgroundExecuteOperation, waitBackgroundExecuteOperation
 
Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

bucket

protected final LocalBucket bucket
One instance of bucket where all objects are stored


pivots

protected final AbstractObjectList<LocalAbstractObject> pivots
A list of fixed pivots used for filtering


pivotDistsValidIfGiven

protected final boolean pivotDistsValidIfGiven
Flag controlling the usage of PrecomputedDistancesFixedArrayFilter -- whether distances are set or appended (see the constructor below for details)

Constructor Detail

SequentialScan

public SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass,
                      java.util.Map<java.lang.String,java.lang.Object> bucketClassParams,
                      AbstractObjectIterator<LocalAbstractObject> pivotIter,
                      int pivotCount,
                      boolean pivotDistsValidIfGiven)
               throws CapacityFullException,
                      java.lang.InstantiationException
Creates a new instance of SequantialScan access structure with specific bucket class and filtering pivots. Additional parameters for the bucket class constructor can be passed.

Parameters:
bucketClass - the class of the storage bucket
bucketClassParams - additional parameters for the bucket class constructor in the name->value form
pivotIter - the iterator from which the fixed pivots will be read
pivotCount - the nubmer of pivots to read from the iterator
pivotDistsValidIfGiven - the flag which controls whether the already associated distances to pivots with new objects are valid or not; if so, they are used without computing and storing them again
Throws:
CapacityFullException - if the maximal number of buckets is already allocated
java.lang.InstantiationException - if
  • the provided storageClass is not a part of LocalBucket hierarchy
  • the storageClass does not have a proper constructor (String,long,long)
  • the correct constructor of storageClass is not accesible
  • the constuctor of storageClass has failed

SequentialScan

public SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass,
                      AbstractObjectIterator<LocalAbstractObject> pivotIter,
                      int pivotCount,
                      boolean pivotDistsValidIfGiven)
               throws CapacityFullException,
                      java.lang.InstantiationException
Creates a new instance of SequantialScan access structure with specific bucket class and filtering pivots.

Parameters:
bucketClass - The class of the storage bucket
pivotIter - The iterator from which the fixed pivots will be read
pivotCount - The nubmer of pivots to read from the iterator
pivotDistsValidIfGiven - The flag which controls whether the already associated distances to pivots with new objects are valid or not. If so, they are used without computing and storing them again.
Throws:
CapacityFullException - if the maximal number of buckets is already allocated
java.lang.InstantiationException - if
  • the provided storageClass is not a part of LocalBucket hierarchy
  • the storageClass does not have a proper constructor (String,long,long)
  • the correct constructor of storageClass is not accesible
  • the constuctor of storageClass has failed

SequentialScan

public SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass,
                      java.util.Map<java.lang.String,java.lang.Object> bucketClassParams)
               throws CapacityFullException,
                      java.lang.InstantiationException
Creates a new instance of SequantialScan access structure with specific bucket class. Additional parameters for the bucket class constructor can be passed.

Parameters:
bucketClass - The class of the storage bucket
bucketClassParams - additional parameters for the bucket class constructor in the name->value form
Throws:
CapacityFullException - if the maximal number of buckets is already allocated
java.lang.InstantiationException - if
  • the provided storageClass is not a part of LocalBucket hierarchy
  • the storageClass does not have a proper constructor (String,long,long)
  • the correct constructor of storageClass is not accesible
  • the constuctor of storageClass has failed

SequentialScan

public SequentialScan(java.lang.Class<? extends LocalBucket> bucketClass)
               throws CapacityFullException,
                      java.lang.InstantiationException
Creates a new instance of SequantialScan access structure with specific bucket class.

Parameters:
bucketClass - The class of the storage bucket
Throws:
CapacityFullException - if the maximal number of buckets is already allocated
java.lang.InstantiationException - if
  • the provided storageClass is not a part of LocalBucket hierarchy
  • the storageClass does not have a proper constructor (String,long,long)
  • the correct constructor of storageClass is not accesible
  • the constuctor of storageClass has failed

SequentialScan

public SequentialScan()
               throws CapacityFullException,
                      java.lang.InstantiationException
Creates a new instance of SequantialScan access structure with the default MemoryStorageBucket class.

Throws:
CapacityFullException - if the maximal number of buckets is already allocated
java.lang.InstantiationException - if
  • the provided storageClass is not a part of LocalBucket hierarchy
  • the storageClass does not have a proper constructor (String,long,long)
  • the correct constructor of storageClass is not accesible
  • the constuctor of storageClass has failed
Method Detail

addPrecompDist

protected void addPrecompDist(LocalAbstractObject object)
Add precomputed distances to a given object. Distance to all pivots is measured and stored into PrecomputedDistancesFixedArrayFilter.

Parameters:
object - the object to add the distances to

finalize

public void finalize()
              throws java.lang.Throwable
Description copied from class: Algorithm
Finalize the algorithm. All transient resources associated with this algorithm are released. After this method is called, the behavior of executing any operation is unpredictable.

Overrides:
finalize in class Algorithm
Throws:
java.lang.Throwable - if there was an error finalizing

destroy

public void destroy()
             throws java.lang.Throwable
Description copied from class: Algorithm
Destroy this algorithm. This method releases all resources (transient and persistent) associated with this algorithm. After this method is called, the behavior of executing any operation is unpredictable.

This implementation defaults to call Algorithm.finalize(), but should be overriden if the algorithm needs to differentiate between finalizing and destroying. In that case the "super.destroy()" should not be called if finalizing is not part of destroy.

Overrides:
destroy in class Algorithm
Throws:
java.lang.Throwable - if there was an error while cleaning

insert

public void insert(InsertOperation operation)
            throws CapacityFullException
Inserts a new object.

Parameters:
operation - Operation of insert which carries the object to be inserted.
Throws:
CapacityFullException - if the hard capacity of the bucket is exceeded

bulkInsert

public void bulkInsert(BulkInsertOperation operation)
                throws BucketStorageException
Bulk insertion. Inserts a list of new objects.

Parameters:
operation - The operation of bulk insert which carries the objects to be inserted.
Throws:
BucketStorageException - if the hard capacity of the bucket is exceeded

delete

public void delete(DeleteOperation operation)
            throws BucketStorageException
Deletes an object.

Parameters:
operation - The operation which specifies the object to be deleted.
Throws:
BucketStorageException - if the low occupation limit is reached when deleting object

delete

public void delete(DeleteByLocatorOperation operation)
            throws BucketStorageException
Deletes objects by locators.

Parameters:
operation - the operation which specifies the locators of objects to be deleted
Throws:
BucketStorageException - if the low occupation limit is reached when deleting object

rangeSearch

public void rangeSearch(RangeQueryOperation operation)
Performs the range search operation with given RangeQueryOperation object. The answer is held in the RangeQueryOperation object.

Parameters:
operation - The range query operation which carries the query object and radius as well as the response list.

knnSearch

public void knnSearch(KNNQueryOperation operation)
Performs the k-nearest neighbor search operation with given KNNQueryOperation object. The answer is held in the KNNQueryOperation object.

Parameters:
operation - The kNN query operation which carries the query object and k as well as the response list.

incrementalNNSearch

public void incrementalNNSearch(IncrementalNNQueryOperation operation)
Performs the incremental nearest neighbor search operation with given IncrementalNNQueryOperation object. The answer is held in the IncrementalNNQueryOperation object.

Parameters:
operation - The incremental NN query operation which carries the query object as well as the response list.

approxKNNSearch

public void approxKNNSearch(ApproxKNNQueryOperation operation)
Performs the approximate k-nearest neighbor search operation with given ApproxKNNQueryOperation object. The answer is held in the ApproxKNNQueryOperation object.

Parameters:
operation - The approximate kNN query operation which carries the query object and k as well as the response list.

search

public void search(QueryOperation<?> operation)
            throws java.lang.CloneNotSupportedException,
                   java.lang.InterruptedException
Performs a generic query operation. Note that this method cannot provide precomputed distances.

Parameters:
operation - the query operation which is to be executed and which will received the result list.
Throws:
java.lang.CloneNotSupportedException - if the operation does not support clonning (and thus cannot be used in parallel)
java.lang.InterruptedException - if the processing thread was interrupted during processing

toString

public java.lang.String toString()
Converts the object to a string representation

Overrides:
toString in class java.lang.Object
Returns:
String representation of this algorithm