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

Class PartialVAFile.PartialVAFileKNNQuery

java.lang.Object

de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery<O>

de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery<O,D>

de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex.AbstractKNNQuery<DoubleDistance>

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

All Implemented Interfaces:

DatabaseQuery, KNNQuery<V,DoubleDistance>

Enclosing class:

PartialVAFile<V extends NumberVector<?>>

public class PartialVAFile.PartialVAFileKNNQuery
extends AbstractRefiningIndex.AbstractKNNQuery<DoubleDistance>

KNN query for this index.

Field Summary

Fields

Modifier and Type	Field and Description
private double	p Lp-Norm p.
private BitSet	subspace Subspace.

Fields inherited from class de.lmu.ifi.dbs.elki.database.query.knn.AbstractDistanceKNNQuery

distanceQuery

Fields inherited from class de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery

relation

Fields inherited from interface de.lmu.ifi.dbs.elki.database.query.DatabaseQuery

HINT_BULK, HINT_EXACT, HINT_HEAVY_USE, HINT_NO_CACHE, HINT_OPTIMIZED_ONLY, HINT_SINGLE

Constructor Summary

Constructors

Constructor and Description
PartialVAFile.PartialVAFileKNNQuery(DistanceQuery<V,DoubleDistance> ddq, double p, BitSet subspace) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
private LinkedList<PartialVAFile.PartialVACandidate>	filter1(int k, int reducedDims, List<DAFile> daFiles, VectorApproximation queryApprox, int subspaceDims, VALPNormDistance dist)
private int	getIOCosts(DAFile sample, int numberOfDAFiles) Computes IO costs (in bytes) needed for reading several DA-files.
private int	getIOCosts(int size, int subspaceDims) Computes IO costs (in bytes) needed for refining the candidates.
DoubleDistanceKNNList	getKNNForObject(V query, int k) Get the k nearest neighbors for a particular id.
List<DAFile>	getWorstCaseDistOrder(VALPNormDistance dist, BitSet subspace) Order subspaces by their worst case distance.
protected DoubleDistanceKNNList	retrieveAccurateDistances(List<PartialVAFile.PartialVACandidate> sortedCandidates, int k, BitSet subspace, V query)

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

getKNNForBulkDBIDs, getKNNForDBID, incRefinements, refine

Methods inherited from class de.lmu.ifi.dbs.elki.database.query.AbstractDataBasedQuery

getRelation

Methods inherited from class java.lang.Object

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

Field Detail

p

private double p

Lp-Norm p.

subspace

private BitSet subspace

Subspace.

Constructor Detail

PartialVAFile.PartialVAFileKNNQuery

public PartialVAFile.PartialVAFileKNNQuery(DistanceQuery<V,DoubleDistance> ddq,
                                   double p,
                                   BitSet subspace)

Constructor.

Parameters:

ddq - Distance query

p - LP-norm p

subspace - Subspace to query

Method Detail

getKNNForObject

public DoubleDistanceKNNList getKNNForObject(V query,
                                    int k)

Description copied from interface: KNNQuery

Get the k nearest neighbors for a particular id.

Specified by:

getKNNForObject in interface KNNQuery<V extends NumberVector<?>,DoubleDistance>

Specified by:

getKNNForObject in class AbstractDistanceKNNQuery<V extends NumberVector<?>,DoubleDistance>

Parameters:

query - Query object

k - Number of neighbors requested

Returns:

neighbors

filter1

private LinkedList<PartialVAFile.PartialVACandidate> filter1(int k,
                                                   int reducedDims,
                                                   List<DAFile> daFiles,
                                                   VectorApproximation queryApprox,
                                                   int subspaceDims,
                                                   VALPNormDistance dist)

getIOCosts

private int getIOCosts(int size,
             int subspaceDims)

Computes IO costs (in bytes) needed for refining the candidates.

Parameters:

size - The nuber of candidates

subspaceDims - the required subspace dimensions

Returns:

the cost value (in bytes)

getIOCosts

private int getIOCosts(DAFile sample,
             int numberOfDAFiles)

Computes IO costs (in bytes) needed for reading several DA-files.

Parameters:

sample - the DA-file specific costs

numberOfDAFiles - the number of DA-files that have to be read

Returns:

the cost value (in bytes)

getWorstCaseDistOrder

public List<DAFile> getWorstCaseDistOrder(VALPNormDistance dist,
                                 BitSet subspace)

Order subspaces by their worst case distance.

Parameters:

dist - Distance function

subspace - Subspace

Returns:

Ordered list of dimension files

retrieveAccurateDistances

protected DoubleDistanceKNNList retrieveAccurateDistances(List<PartialVAFile.PartialVACandidate> sortedCandidates,
                                              int k,
                                              BitSet subspace,
                                              V query)