package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.deliclu;
/*
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
Copyright (C) 2011
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see .
*/
import java.util.ArrayList;
import java.util.List;
import de.lmu.ifi.dbs.elki.data.NumberVector;
import de.lmu.ifi.dbs.elki.database.ids.DBID;
import de.lmu.ifi.dbs.elki.database.ids.DBIDs;
import de.lmu.ifi.dbs.elki.database.query.distance.DistanceQuery;
import de.lmu.ifi.dbs.elki.database.query.distance.SpatialDistanceQuery;
import de.lmu.ifi.dbs.elki.database.query.knn.KNNQuery;
import de.lmu.ifi.dbs.elki.database.query.range.RangeQuery;
import de.lmu.ifi.dbs.elki.database.relation.Relation;
import de.lmu.ifi.dbs.elki.distance.distancevalue.Distance;
import de.lmu.ifi.dbs.elki.index.KNNIndex;
import de.lmu.ifi.dbs.elki.index.RangeIndex;
import de.lmu.ifi.dbs.elki.index.tree.IndexTreePath;
import de.lmu.ifi.dbs.elki.index.tree.TreeIndexPathComponent;
import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.bulk.BulkSplit;
import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeUtil;
import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.util.InsertionStrategy;
import de.lmu.ifi.dbs.elki.logging.Logging;
import de.lmu.ifi.dbs.elki.persistent.PageFile;
/**
* The common use of the DeLiClu tree: indexing number vectors.
*
* @author Erich Schubert
*
* @param Object type
*/
public class DeLiCluTreeIndex> extends DeLiCluTree implements KNNIndex, RangeIndex {
/**
* The relation we index
*/
private Relation relation;
/**
* Constructor.
*
* @param relation Relation to index
* @param pagefile Page file
* @param bulkSplitter bulk load strategy
* @param insertionStrategy the strategy to find the insertion child
*/
public DeLiCluTreeIndex(Relation relation, PageFile pagefile, BulkSplit bulkSplitter, InsertionStrategy insertionStrategy) {
super(pagefile, bulkSplitter, insertionStrategy);
this.relation = relation;
this.initialize();
}
/**
* The appropriate logger for this index.
*/
private static final Logging logger = Logging.getLogger(DeLiCluTreeIndex.class);
/**
* Creates a new leaf entry representing the specified data object.
*
* @param id Object id
*/
protected DeLiCluLeafEntry createNewLeafEntry(DBID id) {
return new DeLiCluLeafEntry(id, relation.get(id));
}
/**
* Marks the specified object as handled and returns the path of node ids from
* the root to the objects's parent.
*
* @param id the objects id to be marked as handled
* @param obj the object to be marked as handled
* @return the path of node ids from the root to the objects's parent
*/
public synchronized List> setHandled(DBID id, O obj) {
if(logger.isDebugging()) {
logger.debugFine("setHandled " + id + ", " + obj + "\n");
}
// find the leaf node containing o
IndexTreePath pathToObject = findPathToObject(getRootPath(), obj, id);
if(pathToObject == null) {
return null;
}
// set o handled
DeLiCluEntry entry = pathToObject.getLastPathComponent().getEntry();
entry.setHasHandled(true);
entry.setHasUnhandled(false);
for(IndexTreePath path = pathToObject; path.getParentPath() != null; path = path.getParentPath()) {
DeLiCluEntry parentEntry = path.getParentPath().getLastPathComponent().getEntry();
DeLiCluNode node = getNode(parentEntry);
boolean hasHandled = false;
boolean hasUnhandled = false;
for(int i = 0; i < node.getNumEntries(); i++) {
final DeLiCluEntry nodeEntry = node.getEntry(i);
hasHandled = hasHandled || nodeEntry.hasHandled();
hasUnhandled = hasUnhandled || nodeEntry.hasUnhandled();
}
parentEntry.setHasUnhandled(hasUnhandled);
parentEntry.setHasHandled(hasHandled);
}
return pathToObject.getPath();
}
/**
* Inserts the specified real vector object into this index.
*
* @param id the object id that was inserted
*/
@Override
public final void insert(DBID id) {
insertLeaf(createNewLeafEntry(id));
}
/**
* Inserts the specified objects into this index. If a bulk load mode is
* implemented, the objects are inserted in one bulk.
*
* @param ids the objects to be inserted
*/
@Override
public final void insertAll(DBIDs ids) {
if(ids.isEmpty() || (ids.size() == 1)) {
return;
}
// Make an example leaf
if(canBulkLoad()) {
List leafs = new ArrayList(ids.size());
for(DBID id : ids) {
leafs.add(createNewLeafEntry(id));
}
bulkLoad(leafs);
}
else {
for(DBID id : ids) {
insert(id);
}
}
doExtraIntegrityChecks();
}
/**
* Deletes the specified object from this index.
*
* @return true if this index did contain the object with the specified id,
* false otherwise
*/
@Override
public final boolean delete(DBID id) {
// find the leaf node containing o
O obj = relation.get(id);
IndexTreePath deletionPath = findPathToObject(getRootPath(), obj, id);
if(deletionPath == null) {
return false;
}
deletePath(deletionPath);
return true;
}
@Override
public void deleteAll(DBIDs ids) {
for(DBID id : ids) {
delete(id);
}
}
@Override
public > RangeQuery getRangeQuery(DistanceQuery distanceQuery, Object... hints) {
// Query on the relation we index
if(distanceQuery.getRelation() != relation) {
return null;
}
// Can we support this distance function - spatial distances only!
if(!(distanceQuery instanceof SpatialDistanceQuery)) {
return null;
}
SpatialDistanceQuery dq = (SpatialDistanceQuery) distanceQuery;
return RStarTreeUtil.getRangeQuery(this, dq, hints);
}
@Override
public > KNNQuery getKNNQuery(DistanceQuery distanceQuery, Object... hints) {
// Query on the relation we index
if(distanceQuery.getRelation() != relation) {
return null;
}
// Can we support this distance function - spatial distances only!
if(!(distanceQuery instanceof SpatialDistanceQuery)) {
return null;
}
SpatialDistanceQuery dq = (SpatialDistanceQuery) distanceQuery;
return RStarTreeUtil.getKNNQuery(this, dq, hints);
}
@Override
public String getLongName() {
return "DeLiClu-Tree";
}
@Override
public String getShortName() {
return "deliclutree";
}
@Override
protected Logging getLogger() {
return logger;
}
}