Package elki.index.tree.metrical.mtreevariants.mtree

Class MTreeIndex<O>

java.lang.Object

elki.index.tree.IndexTree<N,E>

elki.index.tree.metrical.MetricalIndexTree<O,N,E>

elki.index.tree.metrical.mtreevariants.AbstractMTree<O,MTreeNode<O>,MTreeEntry,MTreeSettings<O,MTreeNode<O>,MTreeEntry>>

elki.index.tree.metrical.mtreevariants.mtree.MTree<O>

elki.index.tree.metrical.mtreevariants.mtree.MTreeIndex<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

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

public class MTreeIndex<O>
extends MTree<O>
implements RangeIndex<O>, KNNIndex<O>, DynamicIndex

Class for using an m-tree as database index.

Since:

0.4.0

Author:

Erich Schubert

Nested Class Summary

Nested classes/interfaces inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree

AbstractMTree.Statistics

Field Summary

Fields

Modifier and Type	Field	Description
protected DistanceQuery<O>	distanceQuery	The distance query.
private Relation<O>	relation	The relation indexed.

Fields inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree

settings, statistics

Fields inherited from class elki.index.tree.IndexTree

dirCapacity, dirMinimum, initialized, leafCapacity, leafMinimum

Constructor Summary

Constructors

Constructor	Description
MTreeIndex(Relation<O> relation, PageFile<MTreeNode<O>> pagefile, MTreeSettings<O,MTreeNode<O>,MTreeEntry> settings)	Constructor.

Method Summary

Modifier and Type	Method	Description
protected MTreeEntry	createNewLeafEntry(DBID id, O object, double parentDistance)
boolean	delete(DBIDRef id)	Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.
void	deleteAll(DBIDs ids)	Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.
double	distance(DBIDRef id1, DBIDRef id2)	Returns the distance between the two specified ids.
void	initialize()	Initialize the tree if the page file already existed.
protected void	initializeCapacities(MTreeEntry exampleLeaf)	Determines the maximum and minimum number of entries in a node.
void	insert(DBIDRef id)	Inserts the specified object into this index.
void	insertAll(DBIDs ids)	Inserts the specified objects into this index.
KNNSearcher<DBIDRef>	kNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
KNNSearcher<O>	kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
RangeSearcher<DBIDRef>	rangeByDBID(DistanceQuery<O> distanceQuery, double maxradius, int flags)	Get a range query object for the given distance query and k.
RangeSearcher<O>	rangeByObject(DistanceQuery<O> distanceQuery, double maxrange, int flags)	Get a range query object for the given distance query and k.

Methods inherited from class elki.index.tree.metrical.mtreevariants.mtree.MTree

createNewDirectoryEntry, createNewDirectoryNode, createNewLeafNode, createRootEntry, getLogger, preInsert

Methods inherited from class elki.index.tree.metrical.mtreevariants.AbstractMTree

createEmptyRoot, distance, doExtraIntegrityChecks, getDistance, getHeight, getLeaves, getSortedEntries, insert, insertAll, logStatistics, toString

Methods inherited from class elki.index.tree.IndexTree

createHeader, deleteNode, getFile, getNode, getNode, getPageID, getPageSize, getRootEntry, getRootID, getRootPath, initialize, initializeFromFile, isRoot, postDelete, writeNode

Methods inherited from class java.lang.Object

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

Methods inherited from interface elki.index.Index

logStatistics

Field Detail

relation

private Relation<O> relation

The relation indexed.

distanceQuery

protected DistanceQuery<O> distanceQuery

The distance query.

Constructor Detail

MTreeIndex

public MTreeIndex(Relation<O> relation,
                  PageFile<MTreeNode<O>> pagefile,
                  MTreeSettings<O,MTreeNode<O>,MTreeEntry> settings)

Constructor.

Parameters:

relation - Relation indexed

pagefile - Page file

settings - Tree settings

Method Detail

distance

public double distance(DBIDRef id1,
                       DBIDRef id2)

Description copied from class: AbstractMTree

Returns the distance between the two specified ids.

Specified by:

distance in class AbstractMTree<O,MTreeNode<O>,MTreeEntry,MTreeSettings<O,MTreeNode<O>,MTreeEntry>>

Parameters:

id1 - the first id

id2 - the second id

Returns:

the distance between the two specified ids

initializeCapacities

protected void initializeCapacities(MTreeEntry exampleLeaf)

Description copied from class: IndexTree

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

Specified by:

initializeCapacities in class IndexTree<MTreeNode<O>,MTreeEntry>

Parameters:

exampleLeaf - an object that will be stored in the index

createNewLeafEntry

protected MTreeEntry createNewLeafEntry(DBID id,
                                        O object,
                                        double parentDistance)

Returns:

a new MTreeLeafEntry representing the specified data object

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<MTreeNode<O>,MTreeEntry>

insert

public void insert(DBIDRef id)

Description copied from interface: DynamicIndex

Inserts the specified object into this index.

Specified by:

insert in interface DynamicIndex

Parameters:

id - the object to be inserted

insertAll

public void insertAll(DBIDs ids)

Description copied from interface: DynamicIndex

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)

Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.

Specified by:

delete in interface DynamicIndex

Parameters:

id - Object to remove

Returns:

true if this index did contain the object, false otherwise

Throws:

java.lang.UnsupportedOperationException - thrown, since deletions aren't implemented yet.

deleteAll

public void deleteAll(DBIDs ids)

Throws an UnsupportedOperationException since deletion of objects is not yet supported by an M-Tree.

Specified by:

deleteAll in interface DynamicIndex

Parameters:

ids - Objects to remove

Throws:

java.lang.UnsupportedOperationException - thrown, since deletions aren't implemented yet.

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 interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum value of k

flags - Hints for the optimizer

Returns:

KNN Query object or null

kNNByDBID

public KNNSearcher<DBIDRef> kNNByDBID(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:

kNNByDBID in interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum value of k

flags - Hints for the optimizer

Returns:

KNN Query object or null

rangeByObject

public RangeSearcher<O> rangeByObject(DistanceQuery<O> distanceQuery,
                                      double maxrange,
                                      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 interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum range

flags - Hints for the optimizer

Returns:

KNN Query object or null

rangeByDBID

public RangeSearcher<DBIDRef> rangeByDBID(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:

rangeByDBID in interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

maxradius - Maximum range

flags - Hints for the optimizer

Returns:

KNN Query object or null