de.lmu.ifi.dbs.elki.index.invertedlist

Class InMemoryInvertedIndex<V extends NumberVector>

java.lang.Object

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

de.lmu.ifi.dbs.elki.index.invertedlist.InMemoryInvertedIndex<V>

Type Parameters:

V - Vector type

All Implemented Interfaces:

Index, KNNIndex<V>, RangeIndex<V>, Result

public class InMemoryInvertedIndex<V extends NumberVector>
extends AbstractIndex<V>
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 and Description
protected class	InMemoryInvertedIndex.ArcCosineKNNQuery kNN query object, for arc cosine distance.
protected class	InMemoryInvertedIndex.ArcCosineRangeQuery kNN 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 and Description
(package private) java.util.ArrayList<ModifiableDoubleDBIDList>	index Inverted index.
(package private) WritableDoubleDataStore	length Length storage.
private static Logging	LOG Class logger.

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

relation

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
KNNQuery<V>	getKNNQuery(DistanceQuery<V> distanceQuery, java.lang.Object... hints) Get a KNN query object for the given distance query and k.
java.lang.String	getLongName() A "pretty" name for the result, for use in titles, captions and menus.
private ModifiableDoubleDBIDList	getOrCreateColumn(int dim) Get (or create) a column.
RangeQuery<V>	getRangeQuery(DistanceQuery<V> 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.
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.
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.

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.

index

java.util.ArrayList<ModifiableDoubleDBIDList> index

Inverted index.

length

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

getKNNQuery

public KNNQuery<V> getKNNQuery(DistanceQuery<V> 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<V extends NumberVector>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

getRangeQuery

public RangeQuery<V> getRangeQuery(DistanceQuery<V> 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<V extends NumberVector>

Parameters:

distanceQuery - Distance query

hints - Hints for the optimizer

Returns:

KNN Query object or null

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<V extends NumberVector>

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<V extends NumberVector>

Returns:

result name