de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query

Class RStarTreeKNNQuery<O extends SpatialComparable>

java.lang.Object

de.lmu.ifi.dbs.elki.index.tree.spatial.rstarvariants.query.RStarTreeKNNQuery<O>

All Implemented Interfaces:

DatabaseQuery, KNNQuery<O>

Direct Known Subclasses:

EuclideanRStarTreeKNNQuery

@Reference(authors="G. R. Hjaltason, H. Samet",
           title="Ranking in spatial databases",
           booktitle="4th Symp. Advances in Spatial Databases (SSD\'95)",
           url="https://doi.org/10.1007/3-540-60159-7_6",
           bibkey="DBLP:conf/ssd/HjaltasonS95")
public class RStarTreeKNNQuery<O extends SpatialComparable>
extends java.lang.Object
implements KNNQuery<O>

Instance of a KNN query for a particular spatial index.

Reference:

G. R. Hjaltason, H. Samet
Ranking in spatial databases
4th Symp. Advances in Spatial Databases (SSD'95)

Since:

0.4.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	RStarTreeKNNQuery.DoubleDistanceEntry Optimized double distance entry implementation.

Field Summary

Fields

Modifier and Type	Field and Description
protected SpatialPrimitiveDistanceFunction<? super O>	distanceFunction Spatial primitive distance function.
protected Relation<? extends O>	relation Relation we query.
protected AbstractRStarTree<?,?,?>	tree The index to use

Fields inherited from interface de.lmu.ifi.dbs.elki.database.query.DatabaseQuery

HINT_BULK, HINT_EXACT, HINT_HEAVY_USE, HINT_NO_CACHE, HINT_OPTIMIZED_ONLY, HINT_SINGLE

Constructor Summary

Constructors

Constructor and Description
RStarTreeKNNQuery(AbstractRStarTree<?,?,?> tree, Relation<? extends O> relation, SpatialPrimitiveDistanceFunction<? super O> distanceFunction) Constructor.

Method Summary

Modifier and Type	Method and Description
protected void	batchNN(AbstractRStarTreeNode<?,?> node, java.util.Map<DBID,KNNHeap> knnLists) Performs a batch knn query.
private double	expandNode(O object, KNNHeap knnList, DoubleIntegerMinHeap pq, double maxDist, int nodeID)
java.util.List<KNNList>	getKNNForBulkDBIDs(ArrayDBIDs ids, int k) Bulk query method
KNNList	getKNNForDBID(DBIDRef id, int k) Get the k nearest neighbors for a particular id.
KNNList	getKNNForObject(O obj, int k) Get the k nearest neighbors for a particular id.
protected java.util.List<RStarTreeKNNQuery.DoubleDistanceEntry>	getSortedEntries(AbstractRStarTreeNode<?,?> node, DBIDs ids) Sorts the entries of the specified node according to their minimum distance to the specified objects.

Methods inherited from class java.lang.Object

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

Field Detail

tree

protected final AbstractRStarTree<?,?,?> tree

The index to use

distanceFunction

protected final SpatialPrimitiveDistanceFunction<? super O extends SpatialComparable> distanceFunction

Spatial primitive distance function.

relation

protected Relation<? extends O extends SpatialComparable> relation

Relation we query.

Constructor Detail

RStarTreeKNNQuery

public RStarTreeKNNQuery(AbstractRStarTree<?,?,?> tree,
                         Relation<? extends O> relation,
                         SpatialPrimitiveDistanceFunction<? super O> distanceFunction)

Constructor.

Parameters:

tree - Index to use

relation - Data relation to query

distanceFunction - Distance function

Method Detail

getKNNForDBID

public KNNList getKNNForDBID(DBIDRef id,
                             int k)

Description copied from interface: KNNQuery

Get the k nearest neighbors for a particular id.

Specified by:

getKNNForDBID in interface KNNQuery<O extends SpatialComparable>

Parameters:

id - query object ID

k - Number of neighbors requested

Returns:

neighbors

getKNNForObject

public KNNList getKNNForObject(O obj,
                               int k)

Description copied from interface: KNNQuery

Get the k nearest neighbors for a particular id.

Specified by:

getKNNForObject in interface KNNQuery<O extends SpatialComparable>

Parameters:

obj - Query object

k - Number of neighbors requested

Returns:

neighbors

expandNode

private double expandNode(O object,
                          KNNHeap knnList,
                          DoubleIntegerMinHeap pq,
                          double maxDist,
                          int nodeID)

batchNN

protected void batchNN(AbstractRStarTreeNode<?,?> node,
                       java.util.Map<DBID,KNNHeap> knnLists)

Performs a batch knn query.

Parameters:

node - the node for which the query should be performed

knnLists - a map containing the knn lists for each query objects

getSortedEntries

protected java.util.List<RStarTreeKNNQuery.DoubleDistanceEntry> getSortedEntries(AbstractRStarTreeNode<?,?> node,
                                                                                 DBIDs ids)

Sorts the entries of the specified node according to their minimum distance to the specified objects.

Parameters:

node - the node

ids - the id of the objects

Returns:

a list of the sorted entries

getKNNForBulkDBIDs

public java.util.List<KNNList> getKNNForBulkDBIDs(ArrayDBIDs ids,
                                                  int k)

Description copied from interface: KNNQuery

Bulk query method

Specified by:

getKNNForBulkDBIDs in interface KNNQuery<O extends SpatialComparable>

Parameters:

ids - query object IDs

k - Number of neighbors requested

Returns:

neighbors