Package elki.index.invertedlist

Class InMemoryInvertedIndex<V extends NumberVector>

java.lang.Object

elki.index.invertedlist.InMemoryInvertedIndex<V>

Type Parameters:

V - Vector type

All Implemented Interfaces:

Index, KNNIndex<V>, RangeIndex<V>

public class InMemoryInvertedIndex<V extends NumberVector>
extends java.lang.Object
implements KNNIndex<V>, RangeIndex<V>

Simple index using inverted lists, for cosine distance only.

TODO: support additional distances.

Since:

0.7.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	InMemoryInvertedIndex.ArcCosineKNNQuery	kNN query object, for arc cosine distance.
protected class	InMemoryInvertedIndex.ArcCosineRangeQuery	Range query object, for cosine distance.
protected class	InMemoryInvertedIndex.CosineKNNQuery	kNN query object, for cosine distance.
protected class	InMemoryInvertedIndex.CosineRangeQuery	kNN query object, for cosine distance.
static class	InMemoryInvertedIndex.Factory<V extends NumberVector>	Index factory

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.ArrayList<ModifiableDoubleDBIDList>	index	Inverted index.
protected WritableDoubleDataStore	length	Length storage.
private static Logging	LOG	Class logger.
protected Relation<V>	relation	The representation we are bound to.

Constructor Summary

Constructors

Constructor	Description
InMemoryInvertedIndex(Relation<V> relation)	Constructor.

Method Summary

Modifier and Type	Method	Description
private ModifiableDoubleDBIDList	getOrCreateColumn(int dim)	Get (or create) a column.
private void	indexDense(DBIDRef ref, V obj)	Index a single (dense) instance.
private void	indexSparse(DBIDRef ref, SparseNumberVector obj)	Index a single (sparse) instance.
void	initialize()	Initialize the index.
KNNSearcher<V>	kNNByObject(DistanceQuery<V> 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.
private double	naiveQuery(V obj, WritableDoubleDataStore scores, HashSetModifiableDBIDs cands)	Query the most similar objects, abstract version.
private double	naiveQueryDense(NumberVector obj, WritableDoubleDataStore scores, HashSetModifiableDBIDs cands)	Query the most similar objects, dense version.
private double	naiveQuerySparse(SparseNumberVector obj, WritableDoubleDataStore scores, HashSetModifiableDBIDs cands)	Query the most similar objects, sparse version.
RangeSearcher<V>	rangeByObject(DistanceQuery<V> distanceQuery, double maxradius, int flags)	Get a range query object for the given distance query and k.

Methods inherited from class java.lang.Object

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

Methods inherited from interface elki.index.KNNIndex

kNNByDBID

Methods inherited from interface elki.index.RangeIndex

rangeByDBID

Field Detail

LOG

private static final Logging LOG

Class logger.

relation

protected final Relation<V extends NumberVector> relation

The representation we are bound to.

index

protected java.util.ArrayList<ModifiableDoubleDBIDList> index

Inverted index.

length

protected WritableDoubleDataStore length

Length storage.

Constructor Detail

InMemoryInvertedIndex

public InMemoryInvertedIndex(Relation<V> relation)

Constructor.

Parameters:

relation - Data.

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

indexSparse

private void indexSparse(DBIDRef ref,
                         SparseNumberVector obj)

Index a single (sparse) instance.

Parameters:

ref - Object reference

obj - Object to index.

indexDense

private void indexDense(DBIDRef ref,
                        V obj)

Index a single (dense) instance.

Parameters:

ref - Object reference

obj - Object to index.

getOrCreateColumn

private ModifiableDoubleDBIDList getOrCreateColumn(int dim)

Get (or create) a column.

Parameters:

dim - Dimension

Returns:

Column

naiveQuerySparse

private double naiveQuerySparse(SparseNumberVector obj,
                                WritableDoubleDataStore scores,
                                HashSetModifiableDBIDs cands)

Query the most similar objects, sparse version.

Parameters:

obj - Query object

scores - Score storage

cands - Non-zero objects set

Returns:

Result

naiveQueryDense

private double naiveQueryDense(NumberVector obj,
                               WritableDoubleDataStore scores,
                               HashSetModifiableDBIDs cands)

Query the most similar objects, dense version.

Parameters:

obj - Query object

scores - Score storage

cands - Non-zero objects set

Returns:

Result

naiveQuery

private double naiveQuery(V obj,
                          WritableDoubleDataStore scores,
                          HashSetModifiableDBIDs cands)

Query the most similar objects, abstract version.

Parameters:

obj - Query object

scores - Score storage (must be initialized with zeros!)

cands - Non-zero objects set (must be empty)

Returns:

Result

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

kNNByObject

public KNNSearcher<V> kNNByObject(DistanceQuery<V> 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 interface KNNIndex<V extends NumberVector>

Parameters:

distanceQuery - Distance query

maxk - Maximum value of k

flags - Hints for the optimizer

Returns:

KNN Query object or null

rangeByObject

public RangeSearcher<V> rangeByObject(DistanceQuery<V> 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 interface RangeIndex<V extends NumberVector>

Parameters:

distanceQuery - Distance query

maxradius - Maximum range

flags - Hints for the optimizer

Returns:

KNN Query object or null