de.lmu.ifi.dbs.elki.index.vafile

Class PartialVAFile<V extends NumberVector<?,?>>

java.lang.Object

de.lmu.ifi.dbs.elki.index.AbstractIndex<O>

de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex<V>

de.lmu.ifi.dbs.elki.index.vafile.PartialVAFile<V>

All Implemented Interfaces:

Index, KNNIndex<V>, RangeIndex<V>, PageFileStatistics, Result

@Reference(authors="Hans-Peter Kriegel, Peer Kr\u00f6ger, Matthias Schubert, Ziyue Zhu",
           title="Efficient Query Processing in Arbitrary Subspaces Using Vector Approximations",
           booktitle="Proc. 18th Int. Conf. on Scientific and Statistical Database Management (SSDBM 06), Wien, Austria, 2006",
           url="http://dx.doi.org/10.1109/SSDBM.2006.23")
public class PartialVAFile<V extends NumberVector<?,?>>
extends AbstractRefiningIndex<V>
implements KNNIndex<V>, RangeIndex<V>

PartialVAFile. In-memory only implementation. Reference:

Hans-Peter Kriegel, Peer Kröger, Matthias Schubert, Ziyue Zhu:
Efficient Query Processing in Arbitrary Subspaces Using Vector Approximations
in Proc. 18th Int. Conf. on Scientific and Statistical Database Management (SSDBM 06), Wien, Austria, 2006.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	PartialVAFile.Factory<V extends NumberVector<?,?>> Index factory class
protected static class	PartialVAFile.PartialVACandidate Object in a VA approximation.
class	PartialVAFile.PartialVAFileKNNQuery KNN query for this index.
class	PartialVAFile.PartialVAFileRangeQuery Range query for this index.
static class	PartialVAFile.Statistics Class for tracking Partial VA file statistics TODO: refactor into a common statistics API
protected static class	PartialVAFile.WorstCaseDistComparator Compare DAfiles by their worst case distance.

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex

AbstractRefiningIndex.AbstractKNNQuery<D extends Distance<D>>, AbstractRefiningIndex.AbstractRangeQuery<D extends Distance<D>>

Field Summary

Fields

Modifier and Type	Field and Description
(package private) List<DAFile>	daFiles Partial VA files
private static Logging	logger Class logger
private int	pageSize Page size
private int	partitions Number of partitions
private double[][]	splitPartitions Splitting grid
protected PartialVAFile.Statistics	stats Statistics
private ArrayList<VectorApproximation>	vectorApprox The (full - we are in-memory only right now) vector approximations.

Fields inherited from class de.lmu.ifi.dbs.elki.index.AbstractIndex

relation

Constructor Summary

Constructors

Constructor and Description
PartialVAFile(int pageSize, Relation<V> relation, int partitions) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected VectorApproximation	calculateFullApproximation(DBID id, V dv) Calculate the VA file position given the existing borders.
protected static VectorApproximation	calculatePartialApproximation(DBID id, NumberVector<?,?> dv, List<DoubleObjPair<DAFile>> daFiles) Calculate partial vector approximation
protected static void	calculateSelectivityCoeffs(List<DoubleObjPair<DAFile>> daFiles, NumberVector<?,?> query, double epsilon) Calculate selectivity coefficients.
protected static BitSet	fakeSubspace(Relation<? extends NumberVector<?,?>> relation) Fake subspace (full-dimensional).
<D extends Distance<D>> KNNQuery<V,D>	getKNNQuery(DistanceQuery<V,D> distanceQuery, Object... hints) Get a KNN query object for the given distance query and k.
String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
<D extends Distance<D>> RangeQuery<V,D>	getRangeQuery(DistanceQuery<V,D> distanceQuery, Object... hints) Get a range query object for the given distance query and k.
String	getShortName() A short name for the result, useful for file names.
void	initialize(Relation<V> relation, DBIDs ids) Initialize the index.

Methods inherited from class de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex

getInnerStatistics, getPageFileStatistics, getReadOperations, getWriteOperations, insertAll, refine, resetPageAccess

Methods inherited from class de.lmu.ifi.dbs.elki.index.AbstractIndex

delete, deleteAll, insert

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.index.Index

delete, deleteAll, getPageFileStatistics, insert, insertAll

Field Detail

logger

private static final Logging logger

Class logger

daFiles

List<DAFile> daFiles

Partial VA files

partitions

private final int partitions

Number of partitions

pageSize

private final int pageSize

Page size

splitPartitions

private double[][] splitPartitions

Splitting grid

stats

protected PartialVAFile.Statistics stats

Statistics

vectorApprox

private ArrayList<VectorApproximation> vectorApprox

The (full - we are in-memory only right now) vector approximations.

Constructor Detail

PartialVAFile

public PartialVAFile(int pageSize,
             Relation<V> relation,
             int partitions)

Constructor.

Parameters:

pageSize - Page size

relation - Data relation

partitions - Number of partitions

Method Detail

initialize

public void initialize(Relation<V> relation,
              DBIDs ids)
                throws IllegalStateException

Description copied from class: AbstractRefiningIndex

Initialize the index.

Specified by:

initialize in class AbstractRefiningIndex<V extends NumberVector<?,?>>

Parameters:

relation - Relation to index

ids - database ids

Throws:

IllegalStateException

getShortName

public String getShortName()

Description copied from interface: Result

A short name for the result, useful for file names.

Specified by:

getShortName in interface Result

Specified by:

getShortName in class AbstractIndex<V extends NumberVector<?,?>>

Returns:

result name

getLongName

public String getLongName()

Description copied from interface: Result

A "pretty" name for the result, for use in titles, captions and menus.

Specified by:

getLongName in interface Result

Specified by:

getLongName in class AbstractIndex<V extends NumberVector<?,?>>

Returns:

result name

fakeSubspace

protected static BitSet fakeSubspace(Relation<? extends NumberVector<?,?>> relation)

Fake subspace (full-dimensional).

Parameters:

relation - Relation with full dimensionality

Returns:

Bit set with all bits set.

calculateFullApproximation

protected VectorApproximation calculateFullApproximation(DBID id,
                                             V dv)

Calculate the VA file position given the existing borders.

Parameters:

id - Object ID

dv - Data vector

Returns:

Vector approximation

getKNNQuery

public <D extends Distance<D>> KNNQuery<V,D> getKNNQuery(DistanceQuery<V,D> distanceQuery,
                                                Object... hints)

Description copied from interface: KNNIndex

Get a KNN query object for the given distance query and k. This function MAY return null, when the given distance is not supported!

Specified by:

getKNNQuery in interface KNNIndex<V extends NumberVector<?,?>>

Type Parameters:

D - Distance type

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getRangeQuery

public <D extends Distance<D>> RangeQuery<V,D> getRangeQuery(DistanceQuery<V,D> distanceQuery,
                                                    Object... hints)

Description copied from interface: RangeIndex

Get a range query object for the given distance query and k. This function MAY return null, when the given distance is not supported!

Specified by:

getRangeQuery in interface RangeIndex<V extends NumberVector<?,?>>

Type Parameters:

D - Distance type

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

calculateSelectivityCoeffs

protected static void calculateSelectivityCoeffs(List<DoubleObjPair<DAFile>> daFiles,
                              NumberVector<?,?> query,
                              double epsilon)

Calculate selectivity coefficients.

Parameters:

daFiles - List of files to use

query - Query vector

epsilon - Epsilon radius

calculatePartialApproximation

protected static VectorApproximation calculatePartialApproximation(DBID id,
                                                NumberVector<?,?> dv,
                                                List<DoubleObjPair<DAFile>> daFiles)

Calculate partial vector approximation

Parameters:

id - Object ID

dv - Object vector

daFiles - List of approximations to use

Returns:

Vector approximation