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

Class VAFile<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.VAFile<V>

All Implemented Interfaces:

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

@Title(value="An approximation based data structure for similarity search")
@Reference(authors="Weber, R. and Blott, S.",
           title="An approximation based data structure for similarity search",
           booktitle="Report TR1997b, ETH Zentrum, Zurich, Switzerland",
           url="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.480&rep=rep1&type=pdf")
public class VAFile<V extends NumberVector<?,?>>
extends AbstractRefiningIndex<V>
implements KNNIndex<V>, RangeIndex<V>

Vector-approximation file (VAFile) Reference:

Weber, R. and Blott, S.
An approximation based data structure for similarity search
in: Report TR1997b, ETH Zentrum, Zurich, Switzerland

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	VAFile.Factory<V extends NumberVector<?,?>> Index factory class
class	VAFile.VAFileKNNQuery KNN query for this index.
class	VAFile.VAFileRangeQuery Range query for this index.

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
private static Logging	log Logging class
(package private) int	pageSize Page size, for estimating the VA file size
private int	partitions Number of partitions.
(package private) int	scans Number of scans we performed.
private double[][]	splitPositions Quantile grid we use
private List<VectorApproximation>	vectorApprox Approximation index

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

relation

Constructor Summary

Constructors

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

Method Summary

Methods

Modifier and Type	Method and Description
VectorApproximation	calculateApproximation(DBID id, V dv) Calculate the VA file position given the existing borders.
<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.
long	getRandomReadOnly() Get the number of random read operations only.
<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.
long	getReadOperations() Returns the read I/O-Accesses of this file.
long	getScannedPages() Get the number of scanned bytes.
String	getShortName() A short name for the result, useful for file names.
long	getWriteOperations() Returns the write I/O-Accesses of this file.
protected void	initialize(Relation<V> relation, DBIDs ids) Initialize the index.
void	resetPageAccess() Resets the counters for page accesses of this file and flushes the cache.
void	setPartitions(Relation<V> relation) Initialize the data set grid by computing quantiles.

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

getInnerStatistics, getPageFileStatistics, insertAll, refine

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

log

private static final Logging log

Logging class

vectorApprox

private List<VectorApproximation> vectorApprox

Approximation index

partitions

private int partitions

Number of partitions.

splitPositions

private double[][] splitPositions

Quantile grid we use

pageSize

int pageSize

Page size, for estimating the VA file size

scans

int scans

Number of scans we performed.

Constructor Detail

VAFile

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

Constructor.

Parameters:

pageSize - Page size of simulated index

relation - Relation to index

partitions - Number of partitions for each dimension.

Method Detail

initialize

protected void initialize(Relation<V> relation,
              DBIDs ids)

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

setPartitions

public void setPartitions(Relation<V> relation)
                   throws IllegalArgumentException

Initialize the data set grid by computing quantiles.

Parameters:

relation - Data relation

Throws:

IllegalArgumentException

calculateApproximation

public VectorApproximation calculateApproximation(DBID id,
                                         V dv)

Calculate the VA file position given the existing borders.

Parameters:

id - Object ID

dv - Data vector

Returns:

Vector approximation

getReadOperations

public long getReadOperations()

Description copied from interface: PageFileStatistics

Returns the read I/O-Accesses of this file.

Specified by:

getReadOperations in interface PageFileStatistics

Overrides:

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

Returns:

Number of physical read I/O accesses

getRandomReadOnly

public long getRandomReadOnly()

Get the number of random read operations only.

Returns:

Random read operations.

getScannedPages

public long getScannedPages()

Get the number of scanned bytes.

Returns:

Numebr of scanned bytes.

getWriteOperations

public long getWriteOperations()

Description copied from interface: PageFileStatistics

Returns the write I/O-Accesses of this file.

Specified by:

getWriteOperations in interface PageFileStatistics

Overrides:

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

Returns:

Number of physical write I/O accesses

resetPageAccess

public void resetPageAccess()

Description copied from interface: PageFileStatistics

Resets the counters for page accesses of this file and flushes the cache.

Specified by:

resetPageAccess in interface PageFileStatistics

Overrides:

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

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

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

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