org.openimaj.knn.pq

Class LongSDCNearestNeighbours

java.lang.Object

org.openimaj.knn.LongNearestNeighbours

org.openimaj.knn.pq.LongADCNearestNeighbours

org.openimaj.knn.pq.LongSDCNearestNeighbours

All Implemented Interfaces:

NearestNeighbours<long[],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 LongSDCNearestNeighbours
extends LongADCNearestNeighbours

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.LongADCNearestNeighbours

data, ndims, pq

Constructor Summary

Constructors

Constructor and Description
LongSDCNearestNeighbours(LongProductQuantiser pq, long[][][] pqCentroids, long[][] 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(long[] fullQuery, BoundedPriorityQueue<IntDoublePair> queue, IntDoublePair workingPair)

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

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

Methods inherited from class org.openimaj.knn.LongNearestNeighbours

distanceFunc, distanceFunc, distanceFunc, distanceFunc

Methods inherited from class java.lang.Object

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

Constructor Detail

LongSDCNearestNeighbours

public LongSDCNearestNeighbours(LongProductQuantiser pq,
                                long[][][] pqCentroids,
                                long[][] 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(long[] fullQuery,
                                BoundedPriorityQueue<IntDoublePair> queue,
                                IntDoublePair workingPair)

Overrides:

computeDistances in class LongADCNearestNeighbours