org.openimaj.knn.pq

Class ByteSDCNearestNeighbours

java.lang.Object

org.openimaj.knn.ByteNearestNeighbours

org.openimaj.knn.pq.ByteADCNearestNeighbours

org.openimaj.knn.pq.ByteSDCNearestNeighbours

All Implemented Interfaces:

NearestNeighbours<byte[],float[],IntFloatPair>

@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 ByteSDCNearestNeighbours
extends ByteADCNearestNeighbours

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

data, ndims, pq

Constructor Summary

Constructors

Constructor and Description
ByteSDCNearestNeighbours(ByteProductQuantiser pq, byte[][][] pqCentroids, byte[][] 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(byte[] fullQuery, BoundedPriorityQueue<IntFloatPair> queue, IntFloatPair workingPair)

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

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

Methods inherited from class org.openimaj.knn.ByteNearestNeighbours

distanceFunc, distanceFunc, distanceFunc, distanceFunc

Methods inherited from class java.lang.Object

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

Constructor Detail

ByteSDCNearestNeighbours

public ByteSDCNearestNeighbours(ByteProductQuantiser pq,
                                byte[][][] pqCentroids,
                                byte[][] 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(byte[] fullQuery,
                                BoundedPriorityQueue<IntFloatPair> queue,
                                IntFloatPair workingPair)

Overrides:

computeDistances in class ByteADCNearestNeighbours