Package elki.index.tree.metrical.mtreevariants.mktrees

Class AbstractMkTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,N,E>>

java.lang.Object

elki.index.tree.IndexTree<N,E>

elki.index.tree.metrical.MetricalIndexTree<O,N,E>

elki.index.tree.metrical.mtreevariants.AbstractMTree<O,N,E,S>

elki.index.tree.metrical.mtreevariants.mktrees.AbstractMkTree<O,N,E,S>

Type Parameters:

O - the type of DatabaseObject to be stored in the metrical index

N - the type of MetricalNode used in the metrical index

E - the type of MetricalEntry used in the metrical index

S - the type of Settings kept.

All Implemented Interfaces:

Index

Direct Known Subclasses:

AbstractMkTreeUnified, MkAppTree, MkCoPTree

public abstract class AbstractMkTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,N,E>>
extends AbstractMTree<O,N,E,S>

Abstract class for all M-Tree variants supporting processing of reverse k-nearest neighbor queries by using the k-nn distances of the entries, where k is less than or equal to the given parameter.

Since:

0.2

Author:

Elke Achtert

Nested Class Summary

Nested classes/interfaces inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree

AbstractMTree.Statistics

Field Summary

Fields

Modifier and Type	Field	Description
private DistanceQuery<O>	distanceQuery	Distance query to use.
protected KNNSearcher<DBIDRef>	knnq	Internal class for performing knn queries

Fields inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree

settings, statistics

Fields inherited from class elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor	Description
AbstractMkTree(Relation<O> relation, PageFile<N> pagefile, S settings)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected java.util.Map<DBID,KNNList>	batchNN(N node, DBIDs ids, int kmax)	Deprecated. Change to use by-object NN lookups instead.
double	distance(DBIDRef id1, DBIDRef id2)	Returns the distance between the two specified ids.
abstract DoubleDBIDList	reverseKNNQuery(DBIDRef id, int k)	Performs a reverse k-nearest neighbor query for the given object ID.

Methods inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree

createEmptyRoot, createNewDirectoryEntry, distance, doExtraIntegrityChecks, getDistance, getHeight, getLeaves, getSortedEntries, insert, insertAll, logStatistics, toString

Methods inherited from class elki.index.tree.IndexTree

createHeader, createNewDirectoryNode, createNewLeafNode, createRootEntry, deleteNode, getFile, getLogger, getNode, getNode, getPageID, getPageSize, getRootEntry, getRootID, getRootPath, initialize, initialize, initializeCapacities, initializeFromFile, isRoot, postDelete, preInsert, writeNode

Methods inherited from class java.lang.Object

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

Field Detail

knnq

protected KNNSearcher<DBIDRef> knnq

Internal class for performing knn queries

distanceQuery

private DistanceQuery<O> distanceQuery

Distance query to use.

Constructor Detail

AbstractMkTree

public AbstractMkTree(Relation<O> relation,
                      PageFile<N> pagefile,
                      S settings)

Constructor.

Parameters:

relation - Relation to index

pagefile - Page file

settings - Settings class

Method Detail

distance

public double distance(DBIDRef id1,
                       DBIDRef id2)

Description copied from class: AbstractMTree

Returns the distance between the two specified ids.

Specified by:

distance in class AbstractMTree<O,N extends AbstractMTreeNode<O,N,E>,E extends MTreeEntry,S extends MTreeSettings<O,N,E>>

Parameters:

id1 - the first id

id2 - the second id

Returns:

the distance between the two specified ids

reverseKNNQuery

public abstract DoubleDBIDList reverseKNNQuery(DBIDRef id,
                                               int k)

Performs a reverse k-nearest neighbor query for the given object ID. The query result is in ascending order to the distance to the query object.

Parameters:

id - the query object id

k - the number of nearest neighbors to be returned

Returns:

a List of the query results

batchNN

@Deprecated
protected final java.util.Map<DBID,KNNList> batchNN(N node,
                                                          DBIDs ids,
                                                          int kmax)

Deprecated.

Change to use by-object NN lookups instead.

Performs a batch k-nearest neighbor query for a list of query objects.

Parameters:

node - the node representing the subtree on which the query should be performed

ids - the ids of the query objects

kmax - Maximum k value