Class RdKNNTree<O extends NumberVector>
- java.lang.Object
-
- elki.index.tree.IndexTree<N,E>
-
- elki.index.tree.spatial.rstarvariants.AbstractRStarTree<N,E,S>
-
- elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings>
-
- elki.index.tree.spatial.rstarvariants.rdknn.RdKNNTree<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
DistancePriorityIndex<O>
,DynamicIndex
,Index
,KNNIndex<O>
,RangeIndex<O>
,RKNNIndex<O>
public class RdKNNTree<O extends NumberVector> extends NonFlatRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings> implements DistancePriorityIndex<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.FIXME: currently does not have a RkNN implementation!
- Since:
- 0.1
- Author:
- Elke Achtert
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class elki.index.tree.spatial.rstarvariants.AbstractRStarTree
AbstractRStarTree.Statistics
-
-
Field Summary
Fields Modifier and Type Field Description private SpatialDistanceQuery<O>
distanceQuery
The distance function.protected KNNSearcher<DBIDRef>
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 elki.index.tree.spatial.rstarvariants.AbstractRStarTree
EXTRA_INTEGRITY_CHECKS, height, settings, statistics
-
Fields inherited from class elki.index.tree.IndexTree
dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
adjustKNNDistances(RdKNNEntry entry, ArrayDBIDs ids, double[] kdists)
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.private void
checkDistance(SpatialPrimitiveDistance<? super O> distance)
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 ofTreeIndexHeader
.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
doReverseKNN(RdKNNNode node, DBID oid, ModifiableDoubleDBIDList result)
Performs a reverse knn query in the specified subtree.protected Logging
getLogger()
Get the (STATIC) logger for this class.protected java.util.List<DoubleObjPair<RdKNNEntry>>
getSortedEntries(AbstractRStarTreeNode<?,?> node, SpatialComparable q, SpatialPrimitiveDistance<?> distance)
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.KNNSearcher<O>
kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
Get a KNN query object for the given distance query and k.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.PrioritySearcher<O>
priorityByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Get a priority search object.RangeSearcher<O>
rangeByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Get a range query object for the given distance query and k.DoubleDBIDList
reverseKNNQuery(DBID oid, int k, SpatialPrimitiveDistance<? super O> distance)
RKNNSearcher<DBIDRef>
rkNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)
Get a RKNN query object for the given distance query and k.RKNNSearcher<O>
rkNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
Get a RKNN query object for the given distance query and k.-
Methods inherited from class elki.index.tree.spatial.rstarvariants.NonFlatRStarTree
computeHeight, createEmptyRoot, hasOverflow, hasUnderflow
-
Methods inherited from class elki.index.tree.spatial.rstarvariants.AbstractRStarTree
adjustTree, canBulkLoad, choosePath, containedTest, createBulkLeafNodes, createNewRoot, deletePath, doExtraIntegrityChecks, findPathToObject, getHeight, getLeaves, initializeFromFile, insertEntry, insertLeaf, logStatistics, reInsert, setHeight, toString
-
Methods inherited from class elki.index.tree.IndexTree
deleteNode, getFile, getNode, getNode, getPageID, getPageSize, 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 elki.index.DistancePriorityIndex
priorityByDBID
-
Methods inherited from interface elki.index.Index
logStatistics
-
Methods inherited from interface elki.index.RangeIndex
rangeByDBID
-
-
-
-
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 KNNSearcher<DBIDRef> 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 indexpagefile
- Data storagesettings
- Tree settings
-
-
Method Detail
-
preInsert
protected void preInsert(RdKNNEntry entry)
Performs necessary operations before inserting the specified entry.- Overrides:
preInsert
in classIndexTree<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 classIndexTree<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 classNonFlatRStarTree<RdKNNNode,RdKNNEntry,RdkNNSettings>
- Parameters:
entries
- Entries to bulk load
-
reverseKNNQuery
public DoubleDBIDList reverseKNNQuery(DBID oid, int k, SpatialPrimitiveDistance<? super O> distance)
-
createHeader
protected TreeIndexHeader createHeader()
Description copied from class:IndexTree
Creates a header for this index structure which is an instance ofTreeIndexHeader
. Subclasses may need to overwrite this method if they need a more specialized header.- Overrides:
createHeader
in classIndexTree<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 classAbstractRStarTree<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, SpatialPrimitiveDistance<?> distance)
Sorts the entries of the specified node according to their minimum distance to the specified object.- Parameters:
node
- the nodeq
- the query objectdistance
- 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 insertednodeEntry
- the entry representing the root of the current subtreeknns_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 subtreeoid
- the id of the object for which the rknn query is performedresult
- the list containing the query results
-
adjustKNNDistances
private void adjustKNNDistances(RdKNNEntry entry, ArrayDBIDs ids, double[] kdists)
Adjusts the knn distance in the subtree of the specified root entry.- Parameters:
entry
- the root entry of the current subtreeids
- Sorted list of IDskdists
- knn distances
-
createNewLeafNode
protected RdKNNNode createNewLeafNode()
Creates a new leaf node with the specified capacity.- Specified by:
createNewLeafNode
in classIndexTree<RdKNNNode,RdKNNEntry>
- Returns:
- a new leaf node
-
createNewDirectoryNode
protected RdKNNNode createNewDirectoryNode()
Creates a new directory node with the specified capacity.- Specified by:
createNewDirectoryNode
in classIndexTree<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 classAbstractRStarTree<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 classIndexTree<RdKNNNode,RdKNNEntry>
- Returns:
- an entry representing the root node
-
checkDistance
private void checkDistance(SpatialPrimitiveDistance<? super O> distance)
Throws an IllegalArgumentException if the specified distance function is not an instance of the distance function used by this index.- Parameters:
distance
- 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 interfaceIndex
- Overrides:
initialize
in classIndexTree<RdKNNNode,RdKNNEntry>
-
insert
public final void insert(DBIDRef id)
Inserts the specified real vector object into this index.- Specified by:
insert
in interfaceDynamicIndex
- 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 interfaceDynamicIndex
- 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 interfaceDynamicIndex
- 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 interfaceDynamicIndex
- Parameters:
ids
- Objects to remove
-
kNNByObject
public KNNSearcher<O> kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
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:
kNNByObject
in interfaceDistancePriorityIndex<O extends NumberVector>
- Specified by:
kNNByObject
in interfaceKNNIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxk
- Maximum value of kflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
rangeByObject
public RangeSearcher<O> rangeByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
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:
rangeByObject
in interfaceDistancePriorityIndex<O extends NumberVector>
- Specified by:
rangeByObject
in interfaceRangeIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxradius
- Maximum rangeflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
priorityByObject
public PrioritySearcher<O> priorityByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Description copied from interface:DistancePriorityIndex
Get a priority search object.- Specified by:
priorityByObject
in interfaceDistancePriorityIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxradius
- Maximum search range (may beDouble.POSITIVE_INFINITY
flags
- Optimizer hints- Returns:
- Priority searcher
-
rkNNByObject
public RKNNSearcher<O> rkNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
Description copied from interface:RKNNIndex
Get a RKNN query object for the given distance query and k.This function MAY return null, when the given distance is not supported!
- Specified by:
rkNNByObject
in interfaceRKNNIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxk
- Maximum k for RkNN queryflags
- Hints for the optimizer- Returns:
- RKNN Query object or
null
-
rkNNByDBID
public RKNNSearcher<DBIDRef> rkNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)
Description copied from interface:RKNNIndex
Get a RKNN query object for the given distance query and k.This function MAY return null, when the given distance is not supported!
- Specified by:
rkNNByDBID
in interfaceRKNNIndex<O extends NumberVector>
- Parameters:
distanceQuery
- Distance querymaxk
- Maximum k for RkNN queryflags
- Hints for the optimizer- Returns:
- RKNN Query object or
null
-
-