|
|
|||||||||||||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object de.lmu.ifi.dbs.elki.logging.AbstractLoggable de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E> de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex<O,N,E> de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E> de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<O,RdKNNNode<D>,RdKNNEntry<D>> de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn.RdKNNTree<O,D>
public class RdKNNTree<O extends NumberVector<O,?>,D extends NumberDistance<D>>
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!!!
Field Summary | |
---|---|
static String |
DEFAULT_DISTANCE_FUNCTION
The default distance function. |
static String |
DISTANCE_FUNCTION_D
Description for parameter distance function. |
static String |
DISTANCE_FUNCTION_P
Parameter for distance function. |
private SpatialDistanceFunction<O,D> |
distanceFunction
The distance function. |
static String |
K_D
Description for parameter k. |
private int |
k_max
Parameter k. |
static String |
K_P
Parameter k. |
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex |
---|
bulk, BULK_LOAD_D, BULK_LOAD_F, BULK_LOAD_STRATEGY_D, BULK_LOAD_STRATEGY_P, bulkLoadStrategy |
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex |
---|
CACHE_SIZE_D, CACHE_SIZE_P, cacheSize, DEFAULT_CACHE_SIZE, DEFAULT_PAGE_SIZE, dirCapacity, dirMinimum, file, FILE_NAME_D, FILE_NAME_P, initialized, leafCapacity, leafMinimum, PAGE_SIZE_D, PAGE_SIZE_P, pageSize |
Fields inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable |
---|
optionHandler |
Fields inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable |
---|
debug |
Constructor Summary | |
---|---|
RdKNNTree()
Creates a new DeLiClu-Tree. |
Method Summary | ||
---|---|---|
private void |
adjustKNNDistance(RdKNNEntry<D> entry,
Map<Integer,KNNList<D>> knnLists)
Adjusts the knn distance in the subtree of the specified root entry. |
|
protected void |
bulkLoad(List<O> objects)
Performs a bulk load on this RTree with the specified data. |
|
protected TreeIndexHeader |
createHeader()
Creates a header for this index structure. |
|
protected RdKNNEntry<D> |
createNewDirectoryEntry(RdKNNNode<D> node)
Creates a new directory entry representing the specified node. |
|
protected RdKNNNode<D> |
createNewDirectoryNode(int capacity)
Creates a new directory node with the specified capacity. |
|
protected RdKNNEntry<D> |
createNewLeafEntry(O object)
Creates a new leaf entry representing the specified data object. |
|
protected RdKNNNode<D> |
createNewLeafNode(int capacity)
Creates a new leaf node with the specified capacity. |
|
protected RdKNNEntry<D> |
createRootEntry()
Creates an entry representing the root node. |
|
private void |
doReverseKNN(RdKNNNode<D> node,
O o,
List<QueryResult<D>> result)
Performs a reverse knn query in the specified subtree. |
|
List<AttributeSettings> |
getAttributeSettings()
Returns the parameter setting of the attributes. |
|
protected void |
initializeCapacities(O object,
boolean verbose)
Determines the maximum and minimum number of entries in a node. |
|
protected void |
postDelete(O o)
Performs necessary operations after deleting the specified object. |
|
protected void |
preInsert(RdKNNEntry<D> entry)
Performs necessary operations before inserting the specified entry. |
|
private void |
preInsert(RdKNNEntry<D> q,
RdKNNEntry<D> nodeEntry,
KNNList<D> knns_q)
Adapts the knn distances before insertion of entry q. |
|
|
reverseKNNQuery(O object,
int k,
DistanceFunction<O,T> distanceFunction)
Performs a reverse k-nearest neighbor query for the given object ID. |
|
void |
setDatabase(Database<O> database)
Sets the databse in the distance function of this index. |
|
String[] |
setParameters(String[] args)
Sets the attributes of the class accordingly to the given parameters. |
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 |
---|
batchNN, bulkKNNQueryForIDs, clearReinsertions, createLeafNodes, delete, doKNNQuery, findPathToObject, getHeight, getLeaves, getSortedEntries, getSortedEntries, getValues, initializeFromFile, insert, insert, kNNQuery, rangeQuery, setHeight, toString |
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex |
---|
close, description, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, resetPageAccess |
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable |
---|
addOption, checkGlobalParameterConstraints, deleteOption, description, description, getParameters, getParameterValue, getPossibleOptions, inlineDescription, isSet, setParameters |
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable |
---|
debugFine, debugFiner, debugFinest, exception, message, progress, progress, progress, verbose, verbose, warning |
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.utilities.optionhandling.Parameterizable |
---|
checkGlobalParameterConstraints, getParameters, getPossibleOptions, inlineDescription |
Field Detail |
---|
public static final String K_P
public static final String K_D
public static final String DEFAULT_DISTANCE_FUNCTION
public static final String DISTANCE_FUNCTION_P
public static final String DISTANCE_FUNCTION_D
private int k_max
private SpatialDistanceFunction<O extends NumberVector<O,?>,D extends NumberDistance<D>> distanceFunction
Constructor Detail |
---|
public RdKNNTree()
Method Detail |
---|
protected void preInsert(RdKNNEntry<D> entry)
preInsert
in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
entry
- the entry to be insertedprotected void postDelete(O o)
postDelete
in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
o
- the object to be deletedprotected void bulkLoad(List<O> objects)
bulkLoad
in class NonFlatRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
objects
- the data objects to be indexedpublic <T extends Distance<T>> List<QueryResult<T>> reverseKNNQuery(O object, int k, DistanceFunction<O,T> distanceFunction)
reverseKNNQuery
in class AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
object
- the query objectk
- the number of nearest neighbors to be returneddistanceFunction
- the distance function that computes the distances beween the objects
protected TreeIndexHeader createHeader()
TreeIndex
createHeader
in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
TreeIndex.createHeader()
protected void initializeCapacities(O object, boolean verbose)
TreeIndex
initializeCapacities
in class AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
object
- an object that will be stored in the indexverbose
- flag to allow verbose messagesTreeIndex.initializeCapacities(de.lmu.ifi.dbs.elki.data.DatabaseObject,boolean)
public String[] setParameters(String[] args) throws ParameterException
Parameterizable
setParameters
in interface Parameterizable
setParameters
in class SpatialIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
args
- parameters to set the attributes accordingly to
ParameterException
- in case of wrong parameter-settingParameterizable.setParameters(String[])
public List<AttributeSettings> getAttributeSettings()
getAttributeSettings
in interface Parameterizable
getAttributeSettings
in class AbstractParameterizable
Parameterizable.getAttributeSettings()
public void setDatabase(Database<O> database)
setDatabase
in interface Index<O extends NumberVector<O,?>>
setDatabase
in class SpatialIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
database
- the databaseprivate void preInsert(RdKNNEntry<D> q, RdKNNEntry<D> nodeEntry, KNNList<D> knns_q)
q
- the entry to be insertednodeEntry
- the entry representing the root of thge current subtreeknns_q
- the knns of qprivate void doReverseKNN(RdKNNNode<D> node, O o, List<QueryResult<D>> result)
node
- the root node of the current subtreeo
- the id of the object for which the rknn query is performedresult
- the list conrtaining the query resultsprivate void adjustKNNDistance(RdKNNEntry<D> entry, Map<Integer,KNNList<D>> knnLists)
entry
- the root entry of the current subtreeknnLists
- a map of knn lists for each leaf entryprotected RdKNNNode<D> createNewLeafNode(int capacity)
createNewLeafNode
in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
capacity
- the capacity of the new node
protected RdKNNNode<D> createNewDirectoryNode(int capacity)
createNewDirectoryNode
in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
capacity
- the capacity of the new node
protected RdKNNEntry<D> createNewLeafEntry(O object)
createNewLeafEntry
in class AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
object
- the data object to be represented by the new entry
protected RdKNNEntry<D> createNewDirectoryEntry(RdKNNNode<D> node)
createNewDirectoryEntry
in class AbstractRStarTree<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
node
- the node to be represented by the new entry
protected RdKNNEntry<D> createRootEntry()
createRootEntry
in class TreeIndex<O extends NumberVector<O,?>,RdKNNNode<D extends NumberDistance<D>>,RdKNNEntry<D extends NumberDistance<D>>>
|
|
||||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |