de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn

Class RdKNNTree<O extends NumberVector>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.IndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndexTree<N,E>

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<N,E,S>

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings>

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn.RdKNNTree<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

DynamicIndex, Index, KNNIndex<O>, RangeIndex<O>, RKNNIndex<O>, Result

public class RdKNNTree<O extends NumberVector>
extends NonFlatRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings>
implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O>, DynamicIndex

RDkNNTree is a spatial index structure based on the concepts of the R*-Tree supporting efficient processing of reverse k nearest neighbor queries. The k-nn distance is stored in each entry of a node.

TODO: noch nicht fertig!!!

Since:

0.1

Author:

Elke Achtert

Nested Class Summary

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

AbstractRStarTree.Statistics

Field Summary

Fields

Modifier and Type	Field and Description
private SpatialDistanceQuery<O>	distanceQuery The distance function.
protected KNNQuery<O>	knnQuery Internal knn query object, for updating the rKNN.
private static Logging	LOG The logger for this class.
private Relation<O>	relation The relation we query.

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

EXTRA_INTEGRITY_CHECKS, height, settings, statistics

Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor and Description
RdKNNTree(Relation<O> relation, PageFile<RdKNNNode> pagefile, RdkNNSettings settings) Constructor.

Method Summary

Modifier and Type	Method and Description
private void	adjustKNNDistance(RdKNNEntry entry, ArrayDBIDs ids, java.util.List<? extends KNNList> knnLists) Adjusts the knn distance in the subtree of the specified root entry.
protected void	bulkLoad(java.util.List<RdKNNEntry> entries) Performs a bulk load on this RTree with the specified data.
java.util.List<ModifiableDoubleDBIDList>	bulkReverseKNNQueryForID(DBIDs ids, int k, SpatialPrimitiveDistanceFunction<? super O> distanceFunction, KNNQuery<O> knnQuery)
private void	checkDistanceFunction(SpatialPrimitiveDistanceFunction<? super O> distanceFunction) Throws an IllegalArgumentException if the specified distance function is not an instance of the distance function used by this index.
protected TreeIndexHeader	createHeader() Creates a header for this index structure which is an instance of TreeIndexHeader.
protected RdKNNEntry	createNewDirectoryEntry(RdKNNNode node) Creates a new directory entry representing the specified node.
protected RdKNNNode	createNewDirectoryNode() Creates a new directory node with the specified capacity.
protected RdKNNLeafEntry	createNewLeafEntry(DBID id)
protected RdKNNNode	createNewLeafNode() Creates a new leaf node with the specified capacity.
protected RdKNNEntry	createRootEntry() Creates an entry representing the root node.
boolean	delete(DBIDRef id) Deletes the specified object from this index.
void	deleteAll(DBIDs ids) Deletes the specified objects from this index.
private void	doBulkReverseKNN(RdKNNNode node, DBIDs ids, java.util.Map<DBID,ModifiableDoubleDBIDList> result) Performs a bulk reverse knn query in the specified subtree.
private void	doReverseKNN(RdKNNNode node, DBID oid, ModifiableDoubleDBIDList result) Performs a reverse knn query in the specified subtree.
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
protected Logging	getLogger() Get the (STATIC) logger for this class.
java.lang.String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
RangeQuery<O>	getRangeQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a range query object for the given distance query and k.
RKNNQuery<O>	getRKNNQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
java.lang.String	getShortName() A short name for the result, useful for file names.
protected java.util.List<DoubleObjPair<RdKNNEntry>>	getSortedEntries(AbstractRStarTreeNode<?,?> node, SpatialComparable q, SpatialPrimitiveDistanceFunction<?> distanceFunction) Sorts the entries of the specified node according to their minimum distance to the specified object.
void	initialize() Initialize the tree if the page file already existed.
protected void	initializeCapacities(RdKNNEntry exampleLeaf) Determines the maximum and minimum number of entries in a node.
void	insert(DBIDRef id) Inserts the specified real vector object into this index.
void	insertAll(DBIDs ids) Inserts the specified objects into this index.
protected void	postDelete(RdKNNEntry entry) Performs necessary operations after deleting the specified object.
protected void	preInsert(RdKNNEntry entry) Performs necessary operations before inserting the specified entry.
private void	preInsert(RdKNNEntry q, RdKNNEntry nodeEntry, KNNHeap knns_q) Adapts the knn distances before insertion of entry q.
DoubleDBIDList	reverseKNNQuery(DBID oid, int k, SpatialPrimitiveDistanceFunction<? super O> distanceFunction, KNNQuery<O> knnQuery)

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree

computeHeight, createEmptyRoot, hasOverflow, hasUnderflow

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree

adjustTree, canBulkLoad, choosePath, containedTest, createBulkLeafNodes, createNewRoot, deletePath, doExtraIntegrityChecks, findPathToObject, getHeight, getLeaves, initializeFromFile, insertDirectoryEntry, insertLeaf, insertLeafEntry, logStatistics, reInsert, setHeight, toString

Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.IndexTree

deleteNode, getDirMinimum, getFile, getLeafMinimum, getNode, getNode, getPageID, getPageSize, getRoot, getRootEntry, getRootID, getRootPath, initialize, isRoot, writeNode

Methods inherited from class java.lang.Object

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

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

logStatistics

Field Detail

LOG

private static final Logging LOG

The logger for this class.

distanceQuery

private SpatialDistanceQuery<O extends NumberVector> distanceQuery

The distance function.

knnQuery

protected KNNQuery<O extends NumberVector> knnQuery

Internal knn query object, for updating the rKNN.

relation

private Relation<O extends NumberVector> relation

The relation we query.

Constructor Detail

RdKNNTree

public RdKNNTree(Relation<O> relation,
                 PageFile<RdKNNNode> pagefile,
                 RdkNNSettings settings)

Constructor.

Parameters:

relation - Relation to index

pagefile - Data storage

settings - Tree settings

Method Detail

preInsert

protected void preInsert(RdKNNEntry entry)

Performs necessary operations before inserting the specified entry.

Overrides:

preInsert in class IndexTree<RdKNNNode,RdKNNEntry>

Parameters:

entry - the entry to be inserted

postDelete

protected void postDelete(RdKNNEntry entry)

Performs necessary operations after deleting the specified object.

Overrides:

postDelete in class IndexTree<RdKNNNode,RdKNNEntry>

Parameters:

entry - the entry that was removed

bulkLoad

protected void bulkLoad(java.util.List<RdKNNEntry> entries)

Performs a bulk load on this RTree with the specified data. Is called by the constructor and should be overwritten by subclasses if necessary.

Overrides:

bulkLoad in class NonFlatRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings>

Parameters:

entries - Entries to bulk load

reverseKNNQuery

public DoubleDBIDList reverseKNNQuery(DBID oid,
                                      int k,
                                      SpatialPrimitiveDistanceFunction<? super O> distanceFunction,
                                      KNNQuery<O> knnQuery)

bulkReverseKNNQueryForID

public java.util.List<ModifiableDoubleDBIDList> bulkReverseKNNQueryForID(DBIDs ids,
                                                                         int k,
                                                                         SpatialPrimitiveDistanceFunction<? super O> distanceFunction,
                                                                         KNNQuery<O> knnQuery)

createHeader

protected TreeIndexHeader createHeader()

Description copied from class: IndexTree

Creates a header for this index structure which is an instance of TreeIndexHeader. Subclasses may need to overwrite this method if they need a more specialized header.

Overrides:

createHeader in class IndexTree<RdKNNNode,RdKNNEntry>

Returns:

a new header for this index structure

initializeCapacities

protected void initializeCapacities(RdKNNEntry exampleLeaf)

Description copied from class: IndexTree

Determines the maximum and minimum number of entries in a node.

Overrides:

initializeCapacities in class AbstractRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings>

Parameters:

exampleLeaf - an object that will be stored in the index

getSortedEntries

protected java.util.List<DoubleObjPair<RdKNNEntry>> getSortedEntries(AbstractRStarTreeNode<?,?> node,
                                                                     SpatialComparable q,
                                                                     SpatialPrimitiveDistanceFunction<?> distanceFunction)

Sorts the entries of the specified node according to their minimum distance to the specified object.

Parameters:

node - the node

q - the query object

distanceFunction - the distance function for computing the distances

Returns:

a list of the sorted entries

preInsert

private void preInsert(RdKNNEntry q,
                       RdKNNEntry nodeEntry,
                       KNNHeap knns_q)

Adapts the knn distances before insertion of entry q.

Parameters:

q - the entry to be inserted

nodeEntry - the entry representing the root of the current subtree

knns_q - the knns of q

doReverseKNN

private void doReverseKNN(RdKNNNode node,
                          DBID oid,
                          ModifiableDoubleDBIDList result)

Performs a reverse knn query in the specified subtree.

Parameters:

node - the root node of the current subtree

oid - the id of the object for which the rknn query is performed

result - the list containing the query results

doBulkReverseKNN

private void doBulkReverseKNN(RdKNNNode node,
                              DBIDs ids,
                              java.util.Map<DBID,ModifiableDoubleDBIDList> result)

Performs a bulk reverse knn query in the specified subtree.

Parameters:

node - the root node of the current subtree

ids - the object ids for which the rknn query is performed

result - the map containing the query results for each object

adjustKNNDistance

private void adjustKNNDistance(RdKNNEntry entry,
                               ArrayDBIDs ids,
                               java.util.List<? extends KNNList> knnLists)

Adjusts the knn distance in the subtree of the specified root entry.

Parameters:

entry - the root entry of the current subtree

ids - Sorted list of IDs

knnLists - a map of knn lists for each leaf entry

createNewLeafNode

protected RdKNNNode createNewLeafNode()

Creates a new leaf node with the specified capacity.

Specified by:

createNewLeafNode in class IndexTree<RdKNNNode,RdKNNEntry>

Returns:

a new leaf node

createNewDirectoryNode

protected RdKNNNode createNewDirectoryNode()

Creates a new directory node with the specified capacity.

Specified by:

createNewDirectoryNode in class IndexTree<RdKNNNode,RdKNNEntry>

Returns:

a new directory node

createNewDirectoryEntry

protected RdKNNEntry createNewDirectoryEntry(RdKNNNode node)

Creates a new directory entry representing the specified node.

Specified by:

createNewDirectoryEntry in class AbstractRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings>

Parameters:

node - the node to be represented by the new entry

Returns:

the newly created directory entry

createRootEntry

protected RdKNNEntry createRootEntry()

Creates an entry representing the root node.

Specified by:

createRootEntry in class IndexTree<RdKNNNode,RdKNNEntry>

Returns:

an entry representing the root node

checkDistanceFunction

private void checkDistanceFunction(SpatialPrimitiveDistanceFunction<? super O> distanceFunction)

Throws an IllegalArgumentException if the specified distance function is not an instance of the distance function used by this index.

Parameters:

distanceFunction - the distance function to be checked

Throws:

java.lang.IllegalArgumentException

createNewLeafEntry

protected RdKNNLeafEntry createNewLeafEntry(DBID id)

initialize

public void initialize()

Description copied from class: IndexTree

Initialize the tree if the page file already existed.

Specified by:

initialize in interface Index

Overrides:

initialize in class IndexTree<RdKNNNode,RdKNNEntry>

insert

public final void insert(DBIDRef id)

Inserts the specified real vector object into this index.

Specified by:

insert in interface DynamicIndex

Parameters:

id - the object id that was inserted

insertAll

public final void insertAll(DBIDs ids)

Inserts the specified objects into this index. If a bulk load mode is implemented, the objects are inserted in one bulk.

Specified by:

insertAll in interface DynamicIndex

Parameters:

ids - the objects to be inserted

delete

public final boolean delete(DBIDRef id)

Deletes the specified object from this index.

Specified by:

delete in interface DynamicIndex

Parameters:

id - Object to remove

Returns:

true if this index did contain the object with the specified id, false otherwise

deleteAll

public void deleteAll(DBIDs ids)

Description copied from interface: DynamicIndex

Deletes the specified objects from this index.

Specified by:

deleteAll in interface DynamicIndex

Parameters:

ids - Objects to remove

getRangeQuery

public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery,
                                   java.lang.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<O extends NumberVector>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getKNNQuery

public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery,
                               java.lang.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<O extends NumberVector>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getRKNNQuery

public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery,
                                 java.lang.Object... hints)

Description copied from interface: RKNNIndex

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:

getRKNNQuery in interface RKNNIndex<O extends NumberVector>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getLongName

public java.lang.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

Returns:

result name

getShortName

public java.lang.String getShortName()

Description copied from interface: Result

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

Specified by:

getShortName in interface Result

Returns:

result name

getLogger

protected Logging getLogger()

Description copied from class: IndexTree

Get the (STATIC) logger for this class.

Specified by:

getLogger in class IndexTree<RdKNNNode,RdKNNEntry>

Returns:

the static logger