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

java.lang.Object
  de.lmu.ifi.dbs.elki.logging.AbstractLoggable
      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,DeLiCluNode,DeLiCluEntry>
                      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

distanceCalcs, extraIntegrityChecks, height, reinsertions

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.logging.AbstractLoggable

debug, logger

Constructor Summary

DeLiCluTree(Parameterization config)
Constructor, adhering to Parameterizable

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.
protected Class<DeLiCluNode>	getNodeClass() Return the node base class.
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

adjustTree, batchNN, bulkKNNQueryForIDs, choosePath, clearReinsertions, containedTest, createLeafNodes, createNewRoot, delete, doKNNQuery, findPathToObject, getHeight, getLeaves, getSortedEntries, getSortedEntries, getValues, initializeCapacities, initializeFromFile, insert, insert, insertDirectoryEntry, insertLeafEntry, kNNQuery, rangeQuery, rangeQuery, reInsert, reverseKNNQuery, setHeight, toString, union

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

setDatabase

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

close, createHeader, getFileName, getLogicalPageAccess, getNode, getNode, getPhysicalReadAccess, getPhysicalWriteAccess, getRoot, getRootEntry, getRootPath, initialize, resetPageAccess

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

Field Detail

expanded

private HashMap<Integer,HashSet<Integer>> expanded

Holds the ids of the expanded nodes.

Constructor Detail

DeLiCluTree

public DeLiCluTree(Parameterization config)

Constructor, adhering to Parameterizable

Parameters:

config - Parameterization

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

getNodeClass

protected Class<DeLiCluNode> getNodeClass()

Return the node base class.

Specified by:

getNodeClass in class TreeIndex<O extends NumberVector<O,?>,DeLiCluNode,DeLiCluEntry>

Returns:

node base class