org.openimaj.knn.pq

Class DoubleSDCNearestNeighbours

java.lang.Object

org.openimaj.knn.DoubleNearestNeighbours

org.openimaj.knn.pq.DoubleADCNearestNeighbours

org.openimaj.knn.pq.DoubleSDCNearestNeighbours

All Implemented Interfaces:

NearestNeighbours<double[],double[],IntDoublePair>

@Reference(type=Article,
           author={"Jegou, Herve","Douze, Matthijs","Schmid, Cordelia"},
           title="Product Quantization for Nearest Neighbor Search",
           year="2011",
           journal="IEEE Trans. Pattern Anal. Mach. Intell.",
           pages={"117","","128"},
           url="http://dx.doi.org/10.1109/TPAMI.2010.57",
           month="January",
           number="1",
           publisher="IEEE Computer Society",
           volume="33",
           customData={"issn","0162-8828","numpages","12","doi","10.1109/TPAMI.2010.57","acmid","1916695","address","Washington, DC, USA","keywords","High-dimensional indexing, High-dimensional indexing, image indexing, very large databases, approximate search., approximate search., image indexing, very large databases"})
public class DoubleSDCNearestNeighbours
extends DoubleADCNearestNeighbours

Nearest-neighbours using Symmetric Distance Computation (SDC) on Product Quantised vectors. In SDC, both query and the database points are quantised. Distances are calculated by look-up from precomputed tables of the distance between all centroids for each subvector.

SDC has the same computational cost as ADC, but a higher error in the computed distance, so its use is not recommended. This implementation is provided for completeness only.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

Field Summary

Fields inherited from class org.openimaj.knn.pq.DoubleADCNearestNeighbours

data, ndims, pq

Constructor Summary

Constructors

Constructor and Description
DoubleSDCNearestNeighbours(DoubleProductQuantiser pq, double[][][] pqCentroids, double[][] dataPoints) Construct the SDC with the given quantiser, centroids (corresponding to the quantiser's internal assigners), and data.

Method Summary

Modifier and Type	Method and Description
protected void	computeDistances(double[] fullQuery, BoundedPriorityQueue<IntDoublePair> queue, IntDoublePair workingPair)

Methods inherited from class org.openimaj.knn.pq.DoubleADCNearestNeighbours

numDimensions, searchKNN, searchKNN, searchKNN, searchNN, searchNN, searchNN, size

Methods inherited from class org.openimaj.knn.DoubleNearestNeighbours

distanceFunc, distanceFunc, distanceFunc, distanceFunc

Methods inherited from class java.lang.Object

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

Constructor Detail

DoubleSDCNearestNeighbours

public DoubleSDCNearestNeighbours(DoubleProductQuantiser pq,
                                  double[][][] pqCentroids,
                                  double[][] dataPoints)

Construct the SDC with the given quantiser, centroids (corresponding to the quantiser's internal assigners), and data.

Parameters:

pq - the Product Quantiser

pqCentroids - the centroids corresponding to the the Product Quantiser's internal assigners.

dataPoints - the data to index

Method Detail

computeDistances

protected void computeDistances(double[] fullQuery,
                                BoundedPriorityQueue<IntDoublePair> queue,
                                IntDoublePair workingPair)

Overrides:

computeDistances in class DoubleADCNearestNeighbours