Package elki.index.tree.spatial.kd

Class SmallMemoryKDTree.KDTreeRangeSearcher

java.lang.Object

elki.index.tree.spatial.kd.SmallMemoryKDTree.KDTreeRangeSearcher

All Implemented Interfaces:

RangeSearcher<O>

Enclosing class:

SmallMemoryKDTree<O extends NumberVector>

@Reference(authors="S. Arya and D. M. Mount",
           title="Algorithms for fast vector quantization",
           booktitle="Proc. DCC \'93: Data Compression Conference",
           url="https://doi.org/10.1109/DCC.1993.253111",
           bibkey="doi:10.1109/DCC.1993.253111")
public class SmallMemoryKDTree.KDTreeRangeSearcher
extends java.lang.Object
implements RangeSearcher<O>

Range query for the k-d-tree.

Reference:

S. Arya and D. M. Mount
Algorithms for fast vector quantization
Proc. DCC '93: Data Compression Conference

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
private PartialDistance<? super O>	distance	Distance to use.

Constructor Summary

Constructors

Constructor	Description
KDTreeRangeSearcher(PartialDistance<? super O> distance)	Constructor.

Method Summary

Modifier and Type	Method	Description
ModifiableDoubleDBIDList	getRange(O obj, double range, ModifiableDoubleDBIDList result)	Get the neighbors for a particular id in a given query range.
private void	kdRangeSearch(int left, int right, int axis, O query, ModifiableDoubleDBIDList res, DoubleDBIDListIter iter, double[] bounds, double rawdist, double radius)	Perform a range search on the k-d-tree.

Methods inherited from class java.lang.Object

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

Methods inherited from interface elki.database.query.range.RangeSearcher

getRange

Field Detail

distance

private PartialDistance<? super O extends NumberVector> distance

Distance to use.

Constructor Detail

KDTreeRangeSearcher

public KDTreeRangeSearcher(PartialDistance<? super O> distance)

Constructor.

Parameters:

distance - Distance to use

Method Detail

getRange

public ModifiableDoubleDBIDList getRange(O obj,
                                         double range,
                                         ModifiableDoubleDBIDList result)

Description copied from interface: RangeSearcher

Get the neighbors for a particular id in a given query range.

Specified by:

getRange in interface RangeSearcher<O extends NumberVector>

Parameters:

obj - query object ID

range - Query range

result - Output data structure

Returns:

neighbors

kdRangeSearch

private void kdRangeSearch(int left,
                           int right,
                           int axis,
                           O query,
                           ModifiableDoubleDBIDList res,
                           DoubleDBIDListIter iter,
                           double[] bounds,
                           double rawdist,
                           double radius)

Perform a range search on the k-d-tree.

Parameters:

left - Subtree begin

right - Subtree end (exclusive)

axis - Current splitting axis

query - Query object

res - kNN heap

iter - Iterator variable (reduces memory footprint!)

rawdist - Raw distance to current rectangle (usually squared)

radius - Query radius