Package elki.index.laesa

Class LAESA<O>

java.lang.Object

elki.index.laesa.LAESA<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Index, KNNIndex<O>, RangeIndex<O>

@Reference(authors="L. Mic\u00f3, J. Oncina, E. Vidal",
           title="A new version of the nearest-neighbour approximating and eliminating search  algorithm (AESA) with linear preprocessing time and memory requirements",
           booktitle="Pattern Recognit. Lett. 15(1)",
           url="https://doi.org/10.1016/0167-8655(94)90095-7",
           bibkey="DBLP:journals/prl/MicoOV94")
public class LAESA<O>
extends java.lang.Object
implements RangeIndex<O>, KNNIndex<O>

Linear Approximating and Eliminating Search Algorithm

Reference:

L. Micó, J. Oncina, E. Vidal
A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements
Pattern Recognit. Lett. 15(1)

Since:

0.8.0

Author:

Erich Schubert, Robert Gehde

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	LAESA.Factory<O>	Index factory.
class	LAESA.LAESAKNNByDBIDSearcher	KNN searcher by DBID class
class	LAESA.LAESAKNNByObjectSearcher	KNN searcher by object class
class	LAESA.LAESAKNNSearcher<Q>	KNN searcher class
class	LAESA.LAESARangeByDBIDSearcher	Range searcher by DBID class
class	LAESA.LAESARangeByObjectSearcher	Range searcher by object class
class	LAESA.LAESARangeSearcher<Q>	Range searcher class

Field Summary

Fields

Modifier and Type	Field	Description
(package private) HashSetDBIDs	chosenRefP	fast lookup
(package private) Distance<? super O>	distance	Distance function
(package private) DistanceQuery<? super O>	distq	Distance query, bound to the relation
(package private) DoubleDataStore[]	dists	Data storage for precomputed distances to reference points.
(package private) int	k	Condition parameter
private static Logging	LOG	Class logger.
(package private) int	m	Number of reference points
(package private) ArrayModifiableDBIDs	refp	Reference points
(package private) Relation<O>	relation	Relation indexed.
(package private) RandomFactory	rng	Random generator

Constructor Summary

Constructors

Constructor	Description
LAESA(Relation<O> relation, Distance<? super O> distance, int m, int k, RandomFactory rng)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	initialize()	Initialize the index.
KNNSearcher<DBIDRef>	kNNByDBID(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
KNNSearcher<O>	kNNByObject(DistanceQuery<O> distanceQuery, int maxk, int flags)	Get a KNN query object for the given distance query and k.
RangeSearcher<DBIDRef>	rangeByDBID(DistanceQuery<O> distanceQuery, double maxrange, int flags)	Get a range query object for the given distance query and k.
RangeSearcher<O>	rangeByObject(DistanceQuery<O> distanceQuery, double maxrange, 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.Index

logStatistics

Field Detail

LOG

private static final Logging LOG

Class logger.

distance

Distance<? super O> distance

Distance function

distq

DistanceQuery<? super O> distq

Distance query, bound to the relation

m

int m

Number of reference points

k

int k

Condition parameter

rng

RandomFactory rng

Random generator

relation

Relation<O> relation

Relation indexed.

refp

ArrayModifiableDBIDs refp

Reference points

dists

DoubleDataStore[] dists

Data storage for precomputed distances to reference points.

chosenRefP

HashSetDBIDs chosenRefP

fast lookup

Constructor Detail

LAESA

public LAESA(Relation<O> relation,
             Distance<? super O> distance,
             int m,
             int k,
             RandomFactory rng)

Constructor.

Parameters:

distance - Distance function

m - Number of reference points

rng - Random generator

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

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 interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum value of k

flags - Hints for the optimizer

Returns:

KNN Query object or null

kNNByDBID

public KNNSearcher<DBIDRef> kNNByDBID(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:

kNNByDBID in interface KNNIndex<O>

Parameters:

distanceQuery - Distance query

maxk - Maximum value of k

flags - Hints for the optimizer

Returns:

KNN Query object or null

rangeByObject

public RangeSearcher<O> rangeByObject(DistanceQuery<O> distanceQuery,
                                      double maxrange,
                                      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<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum range

flags - Hints for the optimizer

Returns:

KNN Query object or null

rangeByDBID

public RangeSearcher<DBIDRef> rangeByDBID(DistanceQuery<O> distanceQuery,
                                          double maxrange,
                                          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:

rangeByDBID in interface RangeIndex<O>

Parameters:

distanceQuery - Distance query

maxrange - Maximum range

flags - Hints for the optimizer

Returns:

KNN Query object or null