@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","01628828","numpages","12","doi","10.1109/TPAMI.2010.57","acmid","1916695","address","Washington, DC, USA","keywords","Highdimensional indexing, Highdimensional indexing, image indexing, very large databases, approximate search., approximate search., image indexing, very large databases"}) public class DoubleADCNearestNeighbours extends DoubleNearestNeighbours
For efficiency, the distance of each subvector of a query is computed to every centroid (for the subvector under consideration) only once, and is then cached for the lookup during the computation of the distance to each database vector.
Modifier and Type  Field and Description 

protected byte[][] 
data 
protected int 
ndims 
protected DoubleProductQuantiser 
pq 
Constructor and Description 

DoubleADCNearestNeighbours(DoubleProductQuantiser pq,
byte[][] pqData,
int ndims)
Construct the ADC with the given quantiser and prequantised data .

DoubleADCNearestNeighbours(DoubleProductQuantiser pq,
double[][] dataPoints)
Construct the ADC with the given quantiser and data points.

Modifier and Type  Method and Description 

protected void 
computeDistances(double[] fullQuery,
BoundedPriorityQueue<IntDoublePair> queue,
IntDoublePair wp) 
int 
numDimensions()
Get the number of dimensions of each vector in the dataset

void 
searchKNN(double[][] qus,
int K,
int[][] indices,
double[][] distances)
Search for the K nearest neighbours to each of the N queries, and return
the indices of each nearest neighbour and their respective distances.

List<IntDoublePair> 
searchKNN(double[] query,
int K)
Search for the K nearest neighbours to the given query and return an
ordered list of pairs containing the distance and index of each
neighbour.

void 
searchKNN(List<double[]> qus,
int K,
int[][] indices,
double[][] distances)
Search for the K nearest neighbours to each of the N queries, and return
the indices of each nearest neighbour and their respective distances.

IntDoublePair 
searchNN(double[] query)
Search for the nearest neighbour to the given query and return a pair
containing the distance and index of that neighbour.

void 
searchNN(double[][] qus,
int[] indices,
double[] distances)
Search for the nearest neighbour to each of the N queries, and return the
index of each nearest neighbour and the respective distance.

void 
searchNN(List<double[]> qus,
int[] indices,
double[] distances)
Search for the nearest neighbour to each of the N queries, and return the
index of each nearest neighbour and the respective distance.

int 
size()
Get the size of the dataset

distanceFunc, distanceFunc, distanceFunc, distanceFunc
protected final DoubleProductQuantiser pq
protected final int ndims
protected final byte[][] data
public DoubleADCNearestNeighbours(DoubleProductQuantiser pq, double[][] dataPoints)
pq
 the Product QuantiserdataPoints
 the data points to indexpublic DoubleADCNearestNeighbours(DoubleProductQuantiser pq, byte[][] pqData, int ndims)
pq
 the Product QuantiserpqData
 the prequantised data (i.e. vectors already quantised with
the given pq)ndims
 the dimensionality of the indexed datapublic void searchNN(double[][] qus, int[] indices, double[] distances)
NearestNeighbours
For efficiency, to use this method, you need to preconstruct the arrays for storing the results outside of the method and pass them in as arguments.
If a nearestneighbour cannot be determined, it will have an index value of 1
qus
 An array of N query vectorsindices
 The return Ndimensional array for holding the indices of the
nearest neighbour of each respective query.distances
 The return Ndimensional array for holding the distances of
the nearest neighbour to each respective query.public void searchKNN(double[][] qus, int K, int[][] indices, double[][] distances)
NearestNeighbours
For efficiency, to use this method, you need to preconstruct the arrays for storing the results outside of the method and pass them in as arguments.
If a kth nearestneighbour cannot be determined, it will have an index value of 1
qus
 An array of N query vectorsK
 the number of neighbours to findindices
 The return N*Kdimensional array for holding the indices of
the K nearest neighbours of each respective query.distances
 The return N*Kdimensional array for holding the distances of
the nearest neighbours of each respective query.public void searchNN(List<double[]> qus, int[] indices, double[] distances)
NearestNeighbours
For efficiency, to use this method, you need to preconstruct the arrays for storing the results outside of the method and pass them in as arguments.
If a nearestneighbour cannot be determined, it will have an index value of 1
qus
 An array of N query vectorsindices
 The return Ndimensional array for holding the indices of the
nearest neighbour of each respective query.distances
 The return Ndimensional array for holding the distances of
the nearest neighbour to each respective query.public void searchKNN(List<double[]> qus, int K, int[][] indices, double[][] distances)
NearestNeighbours
For efficiency, to use this method, you need to preconstruct the arrays for storing the results outside of the method and pass them in as arguments.
If a kth nearestneighbour cannot be determined, it will have an index value of 1
qus
 An array of N query vectorsK
 the number of neighbours to findindices
 The return N*Kdimensional array for holding the indices of
the K nearest neighbours of each respective query.distances
 The return N*Kdimensional array for holding the distances of
the nearest neighbours of each respective query.public List<IntDoublePair> searchKNN(double[] query, int K)
NearestNeighbours
If k neighbours cannot be determined, then the resultant list might have fewer than k elements.
query
 the query vectorK
 the number of neighbours to search forpublic IntDoublePair searchNN(double[] query)
NearestNeighbours
If the nearestneighbour cannot be determined null
will be
returned.
query
 the query vectorprotected void computeDistances(double[] fullQuery, BoundedPriorityQueue<IntDoublePair> queue, IntDoublePair wp)
public int numDimensions()
DoubleNearestNeighbours
numDimensions
in class DoubleNearestNeighbours
public int size()
NearestNeighbours