de.lmu.ifi.dbs.elki.index.idistance

Class InMemoryIDistanceIndex<O>

java.lang.Object

de.lmu.ifi.dbs.elki.index.AbstractIndex<O>

de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex<O>

de.lmu.ifi.dbs.elki.index.idistance.InMemoryIDistanceIndex<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Index, KNNIndex<O>, RangeIndex<O>, Result

@Reference(authors="C. Yu, B. C. Ooi, K. L. Tan, H. V. Jagadish",title="Indexing the distance: An efficient method to knn processing",booktitle="Proc. 27th Int. Conf. on Very Large Data Bases",url="http://www.vldb.org/conf/2001/P421.pdf",bibkey="DBLP:conf/vldb/OoiYTJ01") @Reference(authors="H. V. Jagadish, B. C. Ooi, K. L. Tan, C. Yu, R. Zhang",title="iDistance: An adaptive B+-tree based indexing method for nearest neighbor search",booktitle="ACM Transactions on Database Systems (TODS), 30(2)",url="https://doi.org/10.1145/1071610.1071612",bibkey="DBLP:journals/tods/JagadishOTYZ05")
public class InMemoryIDistanceIndex<O>
extends AbstractRefiningIndex<O>
implements RangeIndex<O>, KNNIndex<O>

In-memory iDistance index, a metric indexing method using a reference point embedding.

Important note: we are currently using a different query strategy. The original publication discusses queries based on repeated radius queries. We use a strategy based on shrinking spheres, iteratively refined starting with the closes reference point. We also do not use a B+-tree as data structure, but simple in-memory lists. Therefore, we cannot report page accesses needed.

Feel free to contribute improved query strategies. All the code is essentially here, you only need to query every reference point list, not just the best.

Reference:

C. Yu, B. C. Ooi, K. L. Tan, H. V. Jagadish
Indexing the Distance: An Efficient Method to KNN Processing.
In Proceedings of the 27th International Conference on Very Large Data Bases

H. V. Jagadish, B. C. Ooi, K. L. Tan, C. Yu, R. Zhang
iDistance: An adaptive B+-tree based indexing method for nearest neighbor search.
ACM Transactions on Database Systems (TODS), 30(2).

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	InMemoryIDistanceIndex.Factory<V> Index factory for iDistance indexes.
protected class	InMemoryIDistanceIndex.IDistanceKNNQuery kNN query implementation.
protected class	InMemoryIDistanceIndex.IDistanceRangeQuery Exact Range query implementation.

Nested classes/interfaces inherited from class de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex

AbstractRefiningIndex.AbstractKNNQuery, AbstractRefiningIndex.AbstractRangeQuery

Field Summary

Fields

Modifier and Type	Field and Description
private DistanceQuery<O>	distanceQuery Distance query.
private ModifiableDoubleDBIDList[]	index The actual index.
private KMedoidsInitialization<O>	initialization Initialization method.
private static Logging	LOG Class logger.
private int	numref Number of reference points.
private ArrayDBIDs	referencepoints Reference points.

Fields inherited from class de.lmu.ifi.dbs.elki.index.AbstractIndex

relation

Constructor Summary

Constructors

Constructor and Description
InMemoryIDistanceIndex(Relation<O> relation, DistanceQuery<O> distance, KMedoidsInitialization<O> initialization, int numref) Constructor.

Method Summary

Modifier and Type	Method and Description
protected static void	binarySearch(ModifiableDoubleDBIDList index, DoubleDBIDListIter iter, double val) Seek an iterator to the desired position, using binary search.
private DistanceFunction<? super O>	getDistanceFunction() Distance function.
KNNQuery<O>	getKNNQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
Logging	getLogger() Get the class logger.
java.lang.String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
RangeQuery<O>	getRangeQuery(DistanceQuery<O> distanceQuery, java.lang.Object... hints) Get a range query object for the given distance query and k.
java.lang.String	getShortName() A short name for the result, useful for file names.
void	initialize() Initialize the index.
void	logStatistics() Send statistics to the logger, if enabled.
protected static <O> DoubleIntPair[]	rankReferencePoints(DistanceQuery<O> distanceQuery, O obj, ArrayDBIDs referencepoints) Sort the reference points by distance to the query object

Methods inherited from class de.lmu.ifi.dbs.elki.index.AbstractRefiningIndex

countRefinements, refine

Methods inherited from class java.lang.Object

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

Field Detail

LOG

private static final Logging LOG

Class logger.

distanceQuery

private DistanceQuery<O> distanceQuery

Distance query.

initialization

private KMedoidsInitialization<O> initialization

Initialization method.

numref

private int numref

Number of reference points.

referencepoints

private ArrayDBIDs referencepoints

Reference points.

index

private ModifiableDoubleDBIDList[] index

The actual index.

Constructor Detail

InMemoryIDistanceIndex

public InMemoryIDistanceIndex(Relation<O> relation,
                              DistanceQuery<O> distance,
                              KMedoidsInitialization<O> initialization,
                              int numref)

Constructor.

Parameters:

relation - Data relation

distance - Distance

initialization - Initialization method

numref - Number of reference points

Method Detail

initialize

public void initialize()

Description copied from interface: Index

Initialize the index. For static indexes, this is the moment the index is bulk loaded.

Specified by:

initialize in interface Index

getKNNQuery

public KNNQuery<O> getKNNQuery(DistanceQuery<O> distanceQuery,
                               java.lang.Object... hints)

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:

getKNNQuery in interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getRangeQuery

public RangeQuery<O> getRangeQuery(DistanceQuery<O> distanceQuery,
                                   java.lang.Object... hints)

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:

getRangeQuery in interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getDistanceFunction

private DistanceFunction<? super O> getDistanceFunction()

Distance function.

Returns:

Distance function

getLongName

public java.lang.String getLongName()

Description copied from interface: Result

A "pretty" name for the result, for use in titles, captions and menus.

Specified by:

getLongName in interface Result

Specified by:

getLongName in class AbstractIndex<O>

Returns:

result name

getShortName

public java.lang.String getShortName()

Description copied from interface: Result

A short name for the result, useful for file names.

Specified by:

getShortName in interface Result

Specified by:

getShortName in class AbstractIndex<O>

Returns:

result name

getLogger

public Logging getLogger()

Description copied from class: AbstractRefiningIndex

Get the class logger.

Specified by:

getLogger in class AbstractRefiningIndex<O>

Returns:

Logger

logStatistics

public void logStatistics()

Description copied from interface: Index

Send statistics to the logger, if enabled. Note: you must have set the logging level appropriately before initializing the index! Otherwise, the index might not have collected the desired statistics.

Specified by:

logStatistics in interface Index

Overrides:

logStatistics in class AbstractRefiningIndex<O>

rankReferencePoints

protected static <O> DoubleIntPair[] rankReferencePoints(DistanceQuery<O> distanceQuery,
                                                         O obj,
                                                         ArrayDBIDs referencepoints)

Sort the reference points by distance to the query object

Parameters:

distanceQuery - Distance query

obj - Query object

referencepoints - Iterator for reference points

Returns:

Sorted array.

binarySearch

protected static void binarySearch(ModifiableDoubleDBIDList index,
                                   DoubleDBIDListIter iter,
                                   double val)

Seek an iterator to the desired position, using binary search.

Parameters:

index - Index to search

iter - Iterator

val - Distance to search to