diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java')
| -rw-r--r-- | src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java | 203 |
1 files changed, 203 insertions, 0 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java new file mode 100644 index 00000000..6b5204e5 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/flat/FlatRStarTreeIndex.java @@ -0,0 +1,203 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.flat; + +/* + This file is part of ELKI: + Environment for Developing KDD-Applications Supported by Index-Structures + + Copyright (C) 2014 + 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 <http://www.gnu.org/licenses/>. + */ + +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.DBIDIter; +import de.lmu.ifi.dbs.elki.database.ids.DBIDRef; +import de.lmu.ifi.dbs.elki.database.ids.DBIDUtil; +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.index.DynamicIndex; +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.spatial.SpatialEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeUtil; +import de.lmu.ifi.dbs.elki.logging.Logging; +import de.lmu.ifi.dbs.elki.persistent.PageFile; + +/** + * The common use of the flat rstar tree: indexing number vectors. + * + * @author Erich Schubert + * + * @param <O> Object type + */ +public class FlatRStarTreeIndex<O extends NumberVector> extends FlatRStarTree implements RangeIndex<O>, KNNIndex<O>, DynamicIndex { + /** + * The relation we index + */ + private Relation<O> relation; + + /** + * Constructor. + * + * @param relation Relation to index + * @param pagefile Page file + * @param settings Tree settings + */ + public FlatRStarTreeIndex(Relation<O> relation, PageFile<FlatRStarTreeNode> pagefile, AbstractRTreeSettings settings) { + super(pagefile, settings); + this.relation = relation; + } + + /** + * The appropriate logger for this index. + */ + private static final Logging LOG = Logging.getLogger(FlatRStarTreeIndex.class); + + /** + * Wrap a vector as spatial point leaf entry. + * + * @param id Object DBID + * @return spatial leaf + */ + protected SpatialEntry createNewLeafEntry(DBID id) { + return new SpatialPointLeafEntry(id, relation.get(id)); + } + + @Override + public void initialize() { + super.initialize(); + insertAll(relation.getDBIDs()); + } + + /** + * Inserts the specified real vector object into this index. + * + * @param id the object id that was inserted + */ + @Override + public final void insert(DBIDRef id) { + insertLeaf(createNewLeafEntry(DBIDUtil.deref(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<SpatialEntry> leafs = new ArrayList<>(ids.size()); + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + leafs.add(createNewLeafEntry(DBIDUtil.deref(iter))); + } + bulkLoad(leafs); + } + else { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + insert(iter); + } + } + + 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(DBIDRef id) { + // find the leaf node containing o + O obj = relation.get(id); + IndexTreePath<SpatialEntry> deletionPath = findPathToObject(getRootPath(), obj, id); + if(deletionPath == null) { + return false; + } + deletePath(deletionPath); + return true; + } + + @Override + public void deleteAll(DBIDs ids) { + for (DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + delete(DBIDUtil.deref(iter)); + } + } + + @Override + public RangeQuery<O> getRangeQuery(DistanceQuery<O> 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<O> dq = (SpatialDistanceQuery<O>) distanceQuery; + return RStarTreeUtil.getRangeQuery(this, dq, hints); + } + + @Override + public KNNQuery<O> getKNNQuery(DistanceQuery<O> 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<O> dq = (SpatialDistanceQuery<O>) distanceQuery; + return RStarTreeUtil.getKNNQuery(this, dq, hints); + } + + @Override + public String getLongName() { + return "Flat R*-Tree"; + } + + @Override + public String getShortName() { + return "flatrstartree"; + } + + @Override + protected Logging getLogger() { + return LOG; + } +}
\ No newline at end of file |