diff options
Diffstat (limited to 'src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn')
9 files changed, 1368 insertions, 0 deletions
diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNDirectoryEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNDirectoryEntry.java new file mode 100644 index 00000000..b824bc77 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNDirectoryEntry.java @@ -0,0 +1,129 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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.io.IOException; +import java.io.ObjectInput; +import java.io.ObjectOutput; + +import de.lmu.ifi.dbs.elki.data.ModifiableHyperBoundingBox; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialDirectoryEntry; + +/** + * Represents an entry in a directory node of an RdKNN-Tree. Additionally to a + * SpatialDirectoryEntry a RdKNNDirectoryEntry holds the knn distance of the + * underlying RdKNN-Tree node. + * + * @author Elke Achtert + * @param Distance type + */ +public class RdKNNDirectoryEntry extends SpatialDirectoryEntry implements RdKNNEntry { + private static final long serialVersionUID = 2; + + /** + * The aggregated knn distance of this entry. + */ + private double knnDistance; + + /** + * Empty constructor for serialization purposes. + */ + public RdKNNDirectoryEntry() { + // empty constructor + } + + /** + * Constructs a new RDkNNDirectoryEntry object with the given parameters. + * + * @param id the unique id of the underlying node + * @param mbr the minimum bounding rectangle of the underlying node + * @param knnDistance the aggregated knn distance of this entry + */ + public RdKNNDirectoryEntry(int id, ModifiableHyperBoundingBox mbr, double knnDistance) { + super(id, mbr); + this.knnDistance = knnDistance; + } + + @Override + public double getKnnDistance() { + return knnDistance; + } + + @Override + public void setKnnDistance(double knnDistance) { + this.knnDistance = knnDistance; + } + + /** + * Calls the super method and writes the knn distance of this entry to the + * specified stream. + * + * @param out the stream to write the object to + * @throws java.io.IOException Includes any I/O exceptions that may occur + */ + @Override + public void writeExternal(ObjectOutput out) throws IOException { + super.writeExternal(out); + out.writeDouble(knnDistance); + } + + /** + * Calls the super method and reads the knn distance of this entry from the + * specified input stream. + * + * @param in the stream to read data from in order to restore the object + * @throws java.io.IOException if I/O errors occur + * @throws ClassNotFoundException If the class for an object being restored + * cannot be found. + */ + @Override + public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { + super.readExternal(in); + this.knnDistance = in.readDouble(); + } + + /** + * Indicates whether some other object is "equal to" this one. + * + * @param o the object to be tested + * @return true, if the super method returns true and o is an + * RDkNNDirectoryEntry and has the same knnDistance as this entry. + */ + @Override + public boolean equals(Object o) { + if(this == o) { + return true; + } + if(o == null || getClass() != o.getClass()) { + return false; + } + if(!super.equals(o)) { + return false; + } + + final RdKNNDirectoryEntry that = (RdKNNDirectoryEntry) o; + + return knnDistance == that.knnDistance; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNEntry.java new file mode 100644 index 00000000..f96a6419 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNEntry.java @@ -0,0 +1,49 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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 de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialEntry; + +/** + * Defines the requirements for an entry in an RdKNN-Tree node. Additionally to + * an entry in an R*-Tree an RDkNNEntry holds the knn distance of the underlying + * data object or RdKNN-Tree node. + * + * @author Elke Achtert + */ +interface RdKNNEntry extends SpatialEntry { + /** + * Returns the knn distance of this entry. + * + * @return the knn distance of this entry + */ + public double getKnnDistance(); + + /** + * Sets the knn distance of this entry. + * + * @param knnDistance the knn distance to be set + */ + public void setKnnDistance(double knnDistance); +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNLeafEntry.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNLeafEntry.java new file mode 100644 index 00000000..6d665eb9 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNLeafEntry.java @@ -0,0 +1,129 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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.io.IOException; +import java.io.ObjectInput; +import java.io.ObjectOutput; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.ids.DBID; +import de.lmu.ifi.dbs.elki.index.tree.spatial.SpatialPointLeafEntry; + +/** + * Represents an entry in a leaf node of an RdKNN-Tree. Additionally to a + * SpatialLeafEntry a RdKNNLeafEntry holds the knn distance of the underlying + * data object. + * + * @author Elke Achtert + */ +public class RdKNNLeafEntry extends SpatialPointLeafEntry implements RdKNNEntry { + private static final long serialVersionUID = 2; + + /** + * The knn distance of the underlying data object. + */ + private double knnDistance; + + /** + * Empty constructor for serialization purposes. + */ + public RdKNNLeafEntry() { + super(); + } + + /** + * Constructs a new RDkNNLeafEntry object with the given parameters. + * + * @param id the unique id of the underlying data object + * @param vector the underlying data object + * @param knnDistance the knn distance of the underlying data object + */ + public RdKNNLeafEntry(DBID id, NumberVector vector, double knnDistance) { + super(id, vector); + this.knnDistance = knnDistance; + } + + @Override + public double getKnnDistance() { + return knnDistance; + } + + @Override + public void setKnnDistance(double knnDistance) { + this.knnDistance = knnDistance; + } + + /** + * Calls the super method and writes the knn distance of this entry to the + * specified stream. + * + * @param out the stream to write the object to + * @throws java.io.IOException Includes any I/O exceptions that may occur + */ + @Override + public void writeExternal(ObjectOutput out) throws IOException { + super.writeExternal(out); + out.writeDouble(knnDistance); + } + + /** + * Calls the super method and reads the knn distance of this entry from the + * specified input stream. + * + * @param in the stream to read data from in order to restore the object + * @throws java.io.IOException if I/O errors occur + * @throws ClassNotFoundException If the class for an object being restored + * cannot be found. + */ + @Override + public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { + super.readExternal(in); + this.knnDistance = in.readDouble(); + } + + /** + * Indicates whether some other object is "equal to" this one. + * + * @param o the object to be tested + * @return true, if the super method returns true and o is an RDkNNLeafEntry + * and has the same knnDistance as this entry. + */ + @Override + public boolean equals(Object o) { + if(this == o) { + return true; + } + if(o == null || getClass() != o.getClass()) { + return false; + } + if(!super.equals(o)) { + return false; + } + + final RdKNNLeafEntry that = (RdKNNLeafEntry) o; + + return knnDistance == that.knnDistance; + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNNode.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNNode.java new file mode 100644 index 00000000..89e231b4 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNNode.java @@ -0,0 +1,96 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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 de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; + +/** + * Represents a node in a RDkNN-Tree. + * + * @author Elke Achtert + * + * @apiviz.has RdKNNEntry oneway - - contains + */ +public class RdKNNNode extends AbstractRStarTreeNode<RdKNNNode, RdKNNEntry> { + private static final long serialVersionUID = 1; + + /** + * Empty constructor for Externalizable interface. + */ + public RdKNNNode() { + // empty constructor + } + + /** + * Creates a new RdKNNNode object. + * + * @param capacity the capacity (maximum number of entries plus 1 for + * overflow) of this node + * @param isLeaf indicates whether this node is a leaf node + */ + public RdKNNNode(int capacity, boolean isLeaf) { + super(capacity, isLeaf, RdKNNEntry.class); + } + + /** + * Computes and returns the aggregated knn distance of this node + * + * @return the aggregated knn distance of this node + */ + protected double kNNDistance() { + double result = getEntry(0).getKnnDistance(); + for(int i = 1; i < getNumEntries(); i++) { + double knnDistance = getEntry(i).getKnnDistance(); + result = (result < knnDistance) ? knnDistance : result; + } + return result; + } + + @Override + public boolean adjustEntry(RdKNNEntry entry) { + boolean changed = super.adjustEntry(entry); + entry.setKnnDistance(kNNDistance()); + return changed; + } + + /** + * Tests, if the parameters of the entry representing this node, are correctly + * set. Subclasses may need to overwrite this method. + * + * @param parent the parent holding the entry representing this node + * @param index the index of the entry in the parents child array + */ + @Override + protected void integrityCheckParameters(RdKNNNode parent, int index) { + super.integrityCheckParameters(parent, index); + // test if knn distance is correctly set + RdKNNEntry entry = parent.getEntry(index); + double knnDistance = kNNDistance(); + if(entry.getKnnDistance() != knnDistance) { + double soll = knnDistance; + double ist = entry.getKnnDistance(); + throw new RuntimeException("Wrong knnDistance in node " + parent.getPageID() + " at index " + index + " (child " + entry + ")" + "\nsoll: " + soll + ",\n ist: " + ist); + } + } +}
\ No newline at end of file diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTree.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTree.java new file mode 100644 index 00000000..374e9592 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTree.java @@ -0,0 +1,672 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +import de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable; +import de.lmu.ifi.dbs.elki.database.ids.ArrayDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.ArrayModifiableDBIDs; +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.ids.DoubleDBIDList; +import de.lmu.ifi.dbs.elki.database.ids.DoubleDBIDListIter; +import de.lmu.ifi.dbs.elki.database.ids.KNNHeap; +import de.lmu.ifi.dbs.elki.database.ids.KNNList; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDBIDs; +import de.lmu.ifi.dbs.elki.database.ids.ModifiableDoubleDBIDList; +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.query.rknn.RKNNQuery; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.index.DynamicIndex; +import de.lmu.ifi.dbs.elki.index.KNNIndex; +import de.lmu.ifi.dbs.elki.index.RKNNIndex; +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.LeafEntry; +import de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeNode; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.NonFlatRStarTree; +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; +import de.lmu.ifi.dbs.elki.utilities.io.ByteArrayUtil; +import de.lmu.ifi.dbs.elki.utilities.pairs.DoubleObjPair; + +/** + * RDkNNTree is a spatial index structure based on the concepts of the R*-Tree + * supporting efficient processing of reverse k nearest neighbor queries. The + * k-nn distance is stored in each entry of a node. + * <p/> + * TODO: noch nicht fertig!!! + * + * @author Elke Achtert + * + * @apiviz.has RdKNNNode + * @apiviz.has RdKNNTreeHeader + * + * @param <O> Object type + */ +// FIXME: currently does not yet return RKNNQuery objects! +public class RdKNNTree<O extends NumberVector> extends NonFlatRStarTree<RdKNNNode, RdKNNEntry, RdkNNSettings<O>> implements RangeIndex<O>, KNNIndex<O>, RKNNIndex<O>, DynamicIndex { + /** + * The logger for this class. + */ + private static final Logging LOG = Logging.getLogger(RdKNNTree.class); + + /** + * The distance function. + */ + private SpatialDistanceQuery<O> distanceQuery; + + /** + * Internal knn query object, for updating the rKNN. + */ + protected KNNQuery<O> knnQuery; + + /** + * The relation we query. + */ + private Relation<O> relation; + + /** + * Constructor. + * + * @param relation Relation to index + * @param pagefile Data storage + * @param settings Tree settings + */ + public RdKNNTree(Relation<O> relation, PageFile<RdKNNNode> pagefile, RdkNNSettings<O> settings) { + super(pagefile, settings); + this.relation = relation; + this.distanceQuery = settings.distanceFunction.instantiate(relation); + this.knnQuery = relation.getDatabase().getKNNQuery(distanceQuery); + } + + /** + * Performs necessary operations before inserting the specified entry. + * + * @param entry the entry to be inserted + */ + @Override + protected void preInsert(RdKNNEntry entry) { + KNNHeap knns_o = DBIDUtil.newHeap(settings.k_max); + preInsert(entry, getRootEntry(), knns_o); + } + + /** + * Performs necessary operations after deleting the specified object. + */ + @Override + protected void postDelete(RdKNNEntry entry) { + // reverse knn of o + ModifiableDoubleDBIDList rnns = DBIDUtil.newDistanceDBIDList(); + doReverseKNN(getRoot(), ((RdKNNLeafEntry) entry).getDBID(), rnns); + + // knn of rnn + ArrayModifiableDBIDs ids = DBIDUtil.newArray(rnns); + ids.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(ids, settings.k_max); + + // adjust knn distances + adjustKNNDistance(getRootEntry(), ids, knnLists); + } + + /** + * Performs a bulk load on this RTree with the specified data. Is called by + * the constructor and should be overwritten by subclasses if necessary. + */ + @Override + protected void bulkLoad(List<RdKNNEntry> entries) { + super.bulkLoad(entries); + + // adjust all knn distances + ArrayModifiableDBIDs ids = DBIDUtil.newArray(entries.size()); + for(RdKNNEntry entry : entries) { + DBID id = ((RdKNNLeafEntry) entry).getDBID(); + ids.add(id); + } + ids.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(ids, settings.k_max); + adjustKNNDistance(getRootEntry(), ids, knnLists); + + // test + doExtraIntegrityChecks(); + } + + public DoubleDBIDList reverseKNNQuery(DBID oid, int k, SpatialPrimitiveDistanceFunction<? super O> distanceFunction, KNNQuery<O> knnQuery) { + checkDistanceFunction(distanceFunction); + if(k > settings.k_max) { + throw new IllegalArgumentException("Parameter k is not supported, k > k_max: " + k + " > " + settings.k_max); + } + + // get candidates + ModifiableDoubleDBIDList candidates = DBIDUtil.newDistanceDBIDList(); + doReverseKNN(getRoot(), oid, candidates); + + if(k == settings.k_max) { + candidates.sort(); + return candidates; + } + + // refinement of candidates, if k < k_max + ArrayModifiableDBIDs candidateIDs = DBIDUtil.newArray(candidates); + candidateIDs.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(candidateIDs, k); + + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + int i = 0; + for(DBIDIter iter = candidateIDs.iter(); iter.valid(); iter.advance(), i++) { + for(DoubleDBIDListIter qr = knnLists.get(i).iter(); qr.valid(); qr.advance()) { + if(DBIDUtil.equal(oid, qr)) { + result.add(qr.doubleValue(), iter); + break; + } + } + } + + result.sort(); + return result; + } + + public List<ModifiableDoubleDBIDList> bulkReverseKNNQueryForID(DBIDs ids, int k, SpatialPrimitiveDistanceFunction<? super O> distanceFunction, KNNQuery<O> knnQuery) { + checkDistanceFunction(distanceFunction); + if(k > settings.k_max) { + throw new IllegalArgumentException("Parameter k is not supported, k > k_max: " + k + " > " + settings.k_max); + } + + // get candidates + Map<DBID, ModifiableDoubleDBIDList> candidateMap = new HashMap<>(); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + candidateMap.put(id, DBIDUtil.newDistanceDBIDList()); + } + doBulkReverseKNN(getRoot(), ids, candidateMap); + + if(k == settings.k_max) { + List<ModifiableDoubleDBIDList> resultList = new ArrayList<>(); + for(ModifiableDoubleDBIDList candidates : candidateMap.values()) { + candidates.sort(); + resultList.add(candidates); + } + return resultList; + } + + // refinement of candidates, if k < k_max + // perform a knn query for the candidates + ArrayModifiableDBIDs candidateIDs = DBIDUtil.newArray(); + for(ModifiableDoubleDBIDList candidates : candidateMap.values()) { + candidateIDs.addDBIDs(candidates); + } + candidateIDs.sort(); + List<? extends KNNList> knnLists = knnQuery.getKNNForBulkDBIDs(candidateIDs, k); + + // and add candidate c to the result if o is a knn of c + List<ModifiableDoubleDBIDList> resultList = new ArrayList<>(); + for(DBID id : candidateMap.keySet()) { + ModifiableDoubleDBIDList candidates = candidateMap.get(id); + ModifiableDoubleDBIDList result = DBIDUtil.newDistanceDBIDList(); + for(DoubleDBIDListIter candidate = candidates.iter(); candidate.valid(); candidate.advance()) { + int pos = candidateIDs.binarySearch(candidate); + assert (pos >= 0); + for(DoubleDBIDListIter qr = knnLists.get(pos).iter(); qr.valid(); qr.advance()) { + if(DBIDUtil.equal(id, qr)) { + result.add(qr.doubleValue(), candidate); + break; + } + } + } + resultList.add(result); + } + return resultList; + } + + @Override + protected TreeIndexHeader createHeader() { + return new RdKNNTreeHeader(getPageSize(), dirCapacity, leafCapacity, dirMinimum, leafCapacity, settings.k_max); + } + + @Override + protected void initializeCapacities(RdKNNEntry exampleLeaf) { + int dimensionality = exampleLeaf.getDimensionality(); + int distanceSize = ByteArrayUtil.SIZE_DOUBLE; + + // overhead = index(4), numEntries(4), parentID(4), id(4), isLeaf(0.125) + double overhead = 16.125; + if(getPageSize() - overhead < 0) { + throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + } + + // dirCapacity = (pageSize - overhead) / (childID + childMBR + knnDistance) + // + 1 + dirCapacity = (int) ((getPageSize() - overhead) / (4 + 16 * dimensionality + distanceSize)) + 1; + + if(dirCapacity <= 1) { + throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + } + + if(dirCapacity < 10) { + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a directory node = " + (dirCapacity - 1)); + } + + // minimum entries per directory node + dirMinimum = (int) Math.round((dirCapacity - 1) * 0.5); + if(dirMinimum < 2) { + dirMinimum = 2; + } + + // leafCapacity = (pageSize - overhead) / (childID + childValues + + // knnDistance) + 1 + leafCapacity = (int) ((getPageSize() - overhead) / (4 + 8 * dimensionality + distanceSize)) + 1; + + if(leafCapacity <= 1) { + throw new RuntimeException("Node size of " + getPageSize() + " Bytes is chosen too small!"); + } + + if(leafCapacity < 10) { + LOG.warning("Page size is choosen too small! Maximum number of entries " + "in a leaf node = " + (leafCapacity - 1)); + } + + // minimum entries per leaf node + leafMinimum = (int) Math.round((leafCapacity - 1) * 0.5); + if(leafMinimum < 2) { + leafMinimum = 2; + } + + if(LOG.isVerbose()) { + LOG.verbose("Directory Capacity: " + dirCapacity + "\nLeaf Capacity: " + leafCapacity); + } + } + + /** + * Sorts the entries of the specified node according to their minimum distance + * to the specified object. + * + * @param node the node + * @param q the query object + * @param distanceFunction the distance function for computing the distances + * @return a list of the sorted entries + */ + // TODO: move somewhere else? + protected List<DoubleObjPair<RdKNNEntry>> getSortedEntries(AbstractRStarTreeNode<?, ?> node, SpatialComparable q, SpatialPrimitiveDistanceFunction<?> distanceFunction) { + List<DoubleObjPair<RdKNNEntry>> result = new ArrayList<>(); + + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNEntry entry = (RdKNNEntry) node.getEntry(i); + double minDist = distanceFunction.minDist(entry, q); + result.add(new DoubleObjPair<>(minDist, entry)); + } + + Collections.sort(result); + return result; + } + + /** + * Adapts the knn distances before insertion of entry q. + * + * @param q the entry to be inserted + * @param nodeEntry the entry representing the root of the current subtree + * @param knns_q the knns of q + */ + private void preInsert(RdKNNEntry q, RdKNNEntry nodeEntry, KNNHeap knns_q) { + double knnDist_q = knns_q.getKNNDistance(); + RdKNNNode node = getNode(nodeEntry); + double knnDist_node = 0.; + + // leaf node + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNLeafEntry p = (RdKNNLeafEntry) node.getEntry(i); + double dist_pq = distanceQuery.distance(p.getDBID(), ((LeafEntry) q).getDBID()); + + // p is nearer to q than the farthest kNN-candidate of q + // ==> p becomes a knn-candidate + if(dist_pq <= knnDist_q) { + knns_q.insert(dist_pq, p.getDBID()); + if(knns_q.size() >= settings.k_max) { + knnDist_q = knns_q.getKNNDistance(); + q.setKnnDistance(knnDist_q); + } + + } + // p is nearer to q than to its farthest knn-candidate + // q becomes knn of p + if(dist_pq <= p.getKnnDistance()) { + O obj = relation.get(p.getDBID()); + KNNList knns_without_q = knnQuery.getKNNForObject(obj, settings.k_max); + + if(knns_without_q.size() + 1 < settings.k_max) { + p.setKnnDistance(Double.NaN); + } + else { + double knnDist_p = Math.min(knns_without_q.get(knns_without_q.size() - 1).doubleValue(), dist_pq); + p.setKnnDistance(knnDist_p); + } + } + knnDist_node = Math.max(knnDist_node, p.getKnnDistance()); + } + } + // directory node + else { + O obj = relation.get(((LeafEntry) q).getDBID()); + List<DoubleObjPair<RdKNNEntry>> entries = getSortedEntries(node, obj, settings.distanceFunction); + for(DoubleObjPair<RdKNNEntry> distEntry : entries) { + RdKNNEntry entry = distEntry.second; + double entry_knnDist = entry.getKnnDistance(); + + if(distEntry.first < entry_knnDist || distEntry.first < knnDist_q) { + preInsert(q, entry, knns_q); + knnDist_q = knns_q.getKNNDistance(); + } + knnDist_node = Math.max(knnDist_node, entry.getKnnDistance()); + } + } + nodeEntry.setKnnDistance(knnDist_node); + } + + /** + * Performs a reverse knn query in the specified subtree. + * + * @param node the root node of the current subtree + * @param oid the id of the object for which the rknn query is performed + * @param result the list containing the query results + */ + private void doReverseKNN(RdKNNNode node, DBID oid, ModifiableDoubleDBIDList result) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNLeafEntry entry = (RdKNNLeafEntry) node.getEntry(i); + double distance = distanceQuery.distance(entry.getDBID(), oid); + if(distance <= entry.getKnnDistance()) { + result.add(distance, entry.getDBID()); + } + } + } + // node is a inner node + else { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNDirectoryEntry entry = (RdKNNDirectoryEntry) node.getEntry(i); + double minDist = distanceQuery.minDist(entry, oid); + if(minDist <= entry.getKnnDistance()) { + doReverseKNN(getNode(entry), oid, result); + } + } + } + } + + /** + * Performs a bulk reverse knn query in the specified subtree. + * + * @param node the root node of the current subtree + * @param ids the object ids for which the rknn query is performed + * @param result the map containing the query results for each object + */ + private void doBulkReverseKNN(RdKNNNode node, DBIDs ids, Map<DBID, ModifiableDoubleDBIDList> result) { + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNLeafEntry entry = (RdKNNLeafEntry) node.getEntry(i); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + double distance = distanceQuery.distance(entry.getDBID(), id); + if(distance <= entry.getKnnDistance()) { + result.get(id).add(distance, entry.getDBID()); + } + } + } + } + // node is a inner node + else { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNDirectoryEntry entry = (RdKNNDirectoryEntry) node.getEntry(i); + ModifiableDBIDs candidates = DBIDUtil.newArray(); + for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { + DBID id = DBIDUtil.deref(iter); + double minDist = distanceQuery.minDist(entry, id); + if(minDist <= entry.getKnnDistance()) { + candidates.add(id); + } + if(!candidates.isEmpty()) { + doBulkReverseKNN(getNode(entry), candidates, result); + } + } + } + } + } + + /** + * Adjusts the knn distance in the subtree of the specified root entry. + * + * @param entry the root entry of the current subtree + * @param ids <em>Sorted</em> list of IDs + * @param knnLists a map of knn lists for each leaf entry + */ + private void adjustKNNDistance(RdKNNEntry entry, ArrayDBIDs ids, List<? extends KNNList> knnLists) { + RdKNNNode node = getNode(entry); + double knnDist_node = 0.; + if(node.isLeaf()) { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNEntry leafEntry = node.getEntry(i); + DBID id = ((LeafEntry) leafEntry).getDBID(); + int pos = ids.binarySearch(id); + if(pos >= 0) { + leafEntry.setKnnDistance(knnLists.get(pos).getKNNDistance()); + } + knnDist_node = Math.max(knnDist_node, leafEntry.getKnnDistance()); + } + } + else { + for(int i = 0; i < node.getNumEntries(); i++) { + RdKNNEntry dirEntry = node.getEntry(i); + adjustKNNDistance(dirEntry, ids, knnLists); + knnDist_node = Math.max(knnDist_node, dirEntry.getKnnDistance()); + } + } + entry.setKnnDistance(knnDist_node); + } + + /** + * Creates a new leaf node with the specified capacity. + * + * @return a new leaf node + */ + @Override + protected RdKNNNode createNewLeafNode() { + return new RdKNNNode(leafCapacity, true); + } + + /** + * Creates a new directory node with the specified capacity. + * + * @return a new directory node + */ + @Override + protected RdKNNNode createNewDirectoryNode() { + return new RdKNNNode(dirCapacity, false); + } + + /** + * Creates a new directory entry representing the specified node. + * + * @param node the node to be represented by the new entry + */ + @Override + protected RdKNNEntry createNewDirectoryEntry(RdKNNNode node) { + return new RdKNNDirectoryEntry(node.getPageID(), node.computeMBR(), node.kNNDistance()); + } + + /** + * Creates an entry representing the root node. + * + * @return an entry representing the root node + */ + @Override + protected RdKNNEntry createRootEntry() { + return new RdKNNDirectoryEntry(0, null, Double.NaN); + } + + /** + * Throws an IllegalArgumentException if the specified distance function is + * not an instance of the distance function used by this index. + * + * @throws IllegalArgumentException + * @param distanceFunction the distance function to be checked + */ + private void checkDistanceFunction(SpatialPrimitiveDistanceFunction<? super O> distanceFunction) { + if(!settings.distanceFunction.equals(distanceFunction)) { + throw new IllegalArgumentException("Parameter distanceFunction must be an instance of " + this.distanceQuery.getClass() + ", but is " + distanceFunction.getClass()); + } + } + + protected RdKNNLeafEntry createNewLeafEntry(DBID id) { + return new RdKNNLeafEntry(id, relation.get(id), Double.NaN); + } + + @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<RdKNNEntry> 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<RdKNNEntry> 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; + } + return RStarTreeUtil.getRangeQuery(this, (SpatialDistanceQuery<O>) distanceQuery, 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; + } + return RStarTreeUtil.getKNNQuery(this, (SpatialDistanceQuery<O>) distanceQuery, hints); + } + + @Override + public RKNNQuery<O> getRKNNQuery(DistanceQuery<O> distanceQuery, Object... hints) { + // FIXME: re-add + return null; + } + + @Override + public String getLongName() { + return "RdKNNTree"; + } + + @Override + public String getShortName() { + return "rdknntree"; + } + + @Override + protected Logging getLogger() { + return LOG; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeFactory.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeFactory.java new file mode 100644 index 00000000..a2c9d110 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeFactory.java @@ -0,0 +1,120 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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 de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.database.relation.Relation; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski.EuclideanDistanceFunction; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRStarTreeFactory; +import de.lmu.ifi.dbs.elki.persistent.PageFile; +import de.lmu.ifi.dbs.elki.persistent.PageFileFactory; +import de.lmu.ifi.dbs.elki.utilities.ClassGenericsUtil; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.IntParameter; +import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.ObjectParameter; + +/** + * Factory for RdKNN R*-Trees. + * + * @author Erich Schubert + * + * @apiviz.stereotype factory + * @apiviz.uses RdKNNTreeIndex oneway - - «create» + * + * @param <O> Object type + */ +public class RdKNNTreeFactory<O extends NumberVector> extends AbstractRStarTreeFactory<O, RdKNNNode, RdKNNEntry, RdKNNTree<O>, RdkNNSettings<O>> { + /** + * Parameter for k + */ + public static final OptionID K_ID = new OptionID("rdknn.k", "positive integer specifying the maximal number k of reverse " + "k nearest neighbors to be supported."); + + /** + * The default distance function. + */ + public static final Class<?> DEFAULT_DISTANCE_FUNCTION = EuclideanDistanceFunction.class; + + /** + * Parameter for distance function + */ + public static final OptionID DISTANCE_FUNCTION_ID = new OptionID("rdknn.distancefunction", "Distance function to determine the distance between database objects."); + + /** + * Constructor. + * + * @param pageFileFactory Data storage + * @param settings Settings class + */ + public RdKNNTreeFactory(PageFileFactory<?> pageFileFactory, RdkNNSettings<O> settings) { + super(pageFileFactory, settings); + } + + @Override + public RdKNNTree<O> instantiate(Relation<O> relation) { + PageFile<RdKNNNode> pagefile = makePageFile(getNodeClass()); + RdKNNTree<O> index = new RdKNNTree<>(relation, pagefile, settings); + return index; + } + + protected Class<RdKNNNode> getNodeClass() { + return ClassGenericsUtil.uglyCastIntoSubclass(RdKNNNode.class); + } + + /** + * Parameterization class. + * + * @author Erich Schubert + * + * @apiviz.exclude + */ + public static class Parameterizer<O extends NumberVector> extends AbstractRStarTreeFactory.Parameterizer<O, RdkNNSettings<O>> { + @Override + protected void makeOptions(Parameterization config) { + super.makeOptions(config); + IntParameter k_maxP = new IntParameter(K_ID); + k_maxP.addConstraint(CommonConstraints.GREATER_EQUAL_ONE_INT); + if(config.grab(k_maxP)) { + settings.k_max = k_maxP.intValue(); + } + + ObjectParameter<SpatialPrimitiveDistanceFunction<O>> distanceFunctionP = new ObjectParameter<>(DISTANCE_FUNCTION_ID, SpatialPrimitiveDistanceFunction.class, DEFAULT_DISTANCE_FUNCTION); + if(config.grab(distanceFunctionP)) { + settings.distanceFunction = distanceFunctionP.instantiateClass(config); + } + } + + @Override + protected RdKNNTreeFactory<O> makeInstance() { + return new RdKNNTreeFactory<>(pageFileFactory, settings); + } + + @Override + protected RdkNNSettings<O> createSettings() { + return new RdkNNSettings<>(); + } + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeHeader.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeHeader.java new file mode 100644 index 00000000..fdcff104 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdKNNTreeHeader.java @@ -0,0 +1,101 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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.io.IOException; +import java.io.RandomAccessFile; + +import de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader; + +/** + * Encapsulates the header information of a RDkNN-Tree. This information is + * needed for persistent storage. + * + * @author Elke Achtert + */ +class RdKNNTreeHeader extends TreeIndexHeader { + /** + * The size of this header in Bytes, which is 4 Bytes (for {@link #k_max}). + */ + private static int SIZE = 4; + + /** + * The maximum number k of reverse kNN queries to be supported. + */ + int k_max; + + /** + * Empty constructor for serialization. + */ + public RdKNNTreeHeader() { + super(); + } + + /** + * Creates a new header with the specified parameters. + * + * @param pageSize the size of a page in bytes + * @param dirCapacity the maximum number of entries in a directory node + * @param leafCapacity the maximum number of entries in a leaf node + * @param dirMinimum the minimum number of entries in a directory node + * @param leafMinimum the minimum number of entries in a leaf node + * @param k_max the maximum number k of reverse kNN queries to be supported + */ + public RdKNNTreeHeader(int pageSize, int dirCapacity, int leafCapacity, int dirMinimum, int leafMinimum, int k_max) { + super(pageSize, dirCapacity, leafCapacity, dirMinimum, leafMinimum); + this.k_max = k_max; + } + + /** + * Initializes this header from the specified file. Calls + * {@link de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader#readHeader(java.io.RandomAccessFile) + * TreeIndexHeader#readHeader(file)} and reads additionally the integer value + * of {@link #k_max} from the file. + */ + @Override + public void readHeader(RandomAccessFile file) throws IOException { + super.readHeader(file); + this.k_max = file.readInt(); + } + + /** + * Writes this header to the specified file. Calls + * {@link de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader#writeHeader(java.io.RandomAccessFile)} + * and writes additionally the integer value of {@link #k_max} to the file. + */ + @Override + public void writeHeader(RandomAccessFile file) throws IOException { + super.writeHeader(file); + file.writeInt(this.k_max); + } + + /** + * Returns {@link de.lmu.ifi.dbs.elki.index.tree.TreeIndexHeader#size()} plus + * the value of {@link #SIZE}). + */ + @Override + public int size() { + return super.size() + SIZE; + } +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdkNNSettings.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdkNNSettings.java new file mode 100644 index 00000000..3f9997e2 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/RdkNNSettings.java @@ -0,0 +1,46 @@ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn; + +/* + 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 de.lmu.ifi.dbs.elki.data.NumberVector; +import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction; +import de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.AbstractRTreeSettings; + +/** + * Settings for the RdKNN Tree. + * + * @author Erich Schubert + * + * @param <O> Object type + */ +public class RdkNNSettings<O extends NumberVector> extends AbstractRTreeSettings { + /** + * Parameter k. + */ + int k_max; + + /** + * The distance function. + */ + SpatialPrimitiveDistanceFunction<O> distanceFunction; +} diff --git a/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/package-info.java b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/package-info.java new file mode 100644 index 00000000..972376d6 --- /dev/null +++ b/src/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rdknn/package-info.java @@ -0,0 +1,26 @@ +/** + * <p>{@link de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn.RdKNNTree}</p> + */ +/* +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/>. +*/ +package de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.rdknn;
\ No newline at end of file |