Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu
Class DeLiCluTree<O extends NumberVector<O,?>>

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      extended by de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
          extended by de.lmu.ifi.dbs.elki.index.tree.TreeIndex<O,N,E>
              extended by de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex<O,N,E>
                  extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree<O,N,E>
                      extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree<O,DeLiCluNode,DeLiCluEntry>
                          extended by de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu.DeLiCluTree<O>
Type Parameters:
O - object type
All Implemented Interfaces:
Index<O>, Parameterizable

public class DeLiCluTree<O extends NumberVector<O,?>>
extends NonFlatRStarTree<O,DeLiCluNode,DeLiCluEntry>

DeLiCluTree is a spatial index structure based on an R-TRee. DeLiCluTree is designed for the DeLiClu algorithm, having in each node a boolean array which indicates whether the child nodes are already handled by the DeLiClu algorithm.

Author:
Elke Achtert

Field Summary
private  HashMap<Integer,HashSet<Integer>> expanded
          Holds the ids of the expanded nodes.
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTree
extraIntegrityChecks
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex
bulk, BULK_LOAD_ID, BULK_LOAD_STRATEGY_ID, bulkLoadStrategy
 
Fields inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
CACHE_SIZE_ID, cacheSize, dirCapacity, dirMinimum, file, FILE_ID, initialized, leafCapacity, leafMinimum, PAGE_SIZE_ID, 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, logger
 
Constructor Summary
DeLiCluTree()
          Creates a new DeLiClu-Tree.
 
Method Summary
protected  DeLiCluEntry createNewDirectoryEntry(DeLiCluNode node)
          Creates a new directory entry representing the specified node.
protected  DeLiCluNode createNewDirectoryNode(int capacity)
          Creates a new directory node with the specified capacity.
protected  DeLiCluEntry createNewLeafEntry(O object)
          Creates a new leaf entry representing the specified data object.
protected  DeLiCluNode createNewLeafNode(int capacity)
          Creates a new leaf node with the specified capacity.
protected  DeLiCluEntry createRootEntry()
          Creates an entry representing the root node.
 Set<Integer> getExpanded(DeLiCluNode entry)
          Returns the nodes which are already expanded with the specified node.
 Set<Integer> getExpanded(SpatialEntry entry)
          Returns the nodes which are already expanded with the specified node.
 int numNodes()
          Determines and returns the number of nodes in this index.
protected  void postDelete(O o)
          Performs necessary operations after deleting the specified object.
protected  void preInsert(DeLiCluEntry entry)
          Performs necessary operations before inserting the specified entry.
 void setExpanded(SpatialEntry entry1, SpatialEntry entry2)
          Marks the nodes with the specified ids as expanded.
 List<TreeIndexPathComponent<DeLiCluEntry>> setHandled(O o)
          Marks the specified object as handled and returns the path of node ids from the root to the objects's parent.
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree
bulkLoad, 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, initializeCapacities, initializeFromFile, insert, insert, kNNQuery, rangeQuery, reverseKNNQuery, setHeight, toString
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialIndex
setDatabase, setParameters
 
Methods inherited from class de.lmu.ifi.dbs.elki.index.tree.TreeIndex
close, createHeader, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, resetPageAccess
 
Methods inherited from class de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizable
addOption, addParameterizable, addParameterizable, checkGlobalParameterConstraints, collectOptions, getAttributeSettings, getParameters, rememberParametersExcept, removeOption, removeParameterizable, shortDescription
 
Methods inherited from class de.lmu.ifi.dbs.elki.logging.AbstractLoggable
debugFine, debugFiner, debugFinest, exception, progress, 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, collectOptions, getParameters, shortDescription
 

Field Detail

expanded

private HashMap<Integer,HashSet<Integer>> expanded
Holds the ids of the expanded nodes.

Constructor Detail

DeLiCluTree

public DeLiCluTree()
Creates a new DeLiClu-Tree.

Method Detail

setHandled

public List<TreeIndexPathComponent<DeLiCluEntry>> setHandled(O o)
Marks the specified object as handled and returns the path of node ids from the root to the objects's parent.

Parameters:
o - the object to be marked as handled
Returns:
the path of node ids from the root to the objects's parent

setExpanded

public void setExpanded(SpatialEntry entry1,
                        SpatialEntry entry2)
Marks the nodes with the specified ids as expanded.

Parameters:
entry1 - the first node
entry2 - the second node

getExpanded

public Set<Integer> getExpanded(SpatialEntry entry)
Returns the nodes which are already expanded with the specified node.

Parameters:
entry - the id of the node for which the expansions should be returned
Returns:
the nodes which are already expanded with the specified node

getExpanded

public Set<Integer> getExpanded(DeLiCluNode entry)
Returns the nodes which are already expanded with the specified node.

Parameters:
entry - the id of the node for which the expansions should be returned
Returns:
the nodes which are already expanded with the specified node

numNodes

public int numNodes()
Determines and returns the number of nodes in this index.

Returns:
the number of nodes in this index

createNewLeafNode

protected DeLiCluNode createNewLeafNode(int capacity)
Creates a new leaf node with the specified capacity.

Specified by:
createNewLeafNode in class TreeIndex<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>
Parameters:
capacity - the capacity of the new node
Returns:
a new leaf node

createNewDirectoryNode

protected DeLiCluNode createNewDirectoryNode(int capacity)
Creates a new directory node with the specified capacity.

Specified by:
createNewDirectoryNode in class TreeIndex<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>
Parameters:
capacity - the capacity of the new node
Returns:
a new directory node

createNewLeafEntry

protected DeLiCluEntry createNewLeafEntry(O object)
Creates a new leaf entry representing the specified data object.

Specified by:
createNewLeafEntry in class AbstractRStarTree<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>
Parameters:
object - the data object to be represented by the new entry
Returns:
the newly created leaf entry

createNewDirectoryEntry

protected DeLiCluEntry createNewDirectoryEntry(DeLiCluNode node)
Creates a new directory entry representing the specified node.

Specified by:
createNewDirectoryEntry in class AbstractRStarTree<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>
Parameters:
node - the node to be represented by the new entry
Returns:
the newly created directory entry

createRootEntry

protected DeLiCluEntry createRootEntry()
Creates an entry representing the root node.

Specified by:
createRootEntry in class TreeIndex<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>
Returns:
an entry representing the root node

preInsert

protected void preInsert(DeLiCluEntry entry)
Performs necessary operations before inserting the specified entry.

Specified by:
preInsert in class TreeIndex<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>
Parameters:
entry - the entry to be inserted

postDelete

protected void postDelete(O o)
Performs necessary operations after deleting the specified object.

Specified by:
postDelete in class TreeIndex<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>
Parameters:
o - the object to be deleted

Release 0.2 (2009-07-06_1820)