Class InMemoryIDistanceIndex<O>
- java.lang.Object
-
- elki.index.AbstractRefiningIndex<O>
-
- elki.index.idistance.InMemoryIDistanceIndex<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
Index
,KNNIndex<O>
,RangeIndex<O>
@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 BasesH. 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 Description static class
InMemoryIDistanceIndex.Factory<V>
Index factory for iDistance indexes.protected class
InMemoryIDistanceIndex.IDistanceKNNSearcher
kNN query implementation.protected class
InMemoryIDistanceIndex.IDistanceRangeSearcher
Exact range query implementation.-
Nested classes/interfaces inherited from class elki.index.AbstractRefiningIndex
AbstractRefiningIndex.AbstractRefiningQuery
-
-
Field Summary
Fields Modifier and Type Field 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 elki.index.AbstractRefiningIndex
relation
-
-
Constructor Summary
Constructors Constructor Description InMemoryIDistanceIndex(Relation<O> relation, DistanceQuery<O> distance, KMedoidsInitialization<O> initialization, int numref)
Constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description protected static void
binarySearch(ModifiableDoubleDBIDList index, DoubleDBIDListIter iter, double val)
Seek an iterator to the desired position, using binary search.private Distance<? super O>
getDistance()
Distance function.Logging
getLogger()
Get the class logger.void
initialize()
Initialize the index.KNNSearcher<O>
kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
Get a KNN query object for the given distance query and k.void
logStatistics()
Send statistics to the logger, if enabled.RangeSearcher<O>
rangeByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
Get a range query object for the given distance query and k.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 elki.index.AbstractRefiningIndex
countRefinements, refine
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface elki.index.RangeIndex
rangeByDBID
-
-
-
-
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 relationdistance
- Distanceinitialization
- Initialization methodnumref
- 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 interfaceIndex
-
kNNByObject
public KNNSearcher<O> kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)
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:
kNNByObject
in interfaceKNNIndex<O>
- Parameters:
distanceQuery
- Distance querymaxk
- Maximum value of kflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
rangeByObject
public RangeSearcher<O> rangeByObject(DistanceQuery<O> distanceQuery, double maxradius, int flags)
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:
rangeByObject
in interfaceRangeIndex<O>
- Parameters:
distanceQuery
- Distance querymaxradius
- Maximum rangeflags
- Hints for the optimizer- Returns:
- KNN Query object or
null
-
getLogger
public Logging getLogger()
Description copied from class:AbstractRefiningIndex
Get the class logger.- Specified by:
getLogger
in classAbstractRefiningIndex<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 interfaceIndex
- Overrides:
logStatistics
in classAbstractRefiningIndex<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 queryobj
- Query objectreferencepoints
- 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 searchiter
- Iteratorval
- Distance to search to
-
-