@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 IncrementalDoubleADCNearestNeighbours extends DoubleNearestNeighbours implements IncrementalNearestNeighbours<double[],double[],IntDoublePair>, ReadWriteableBinary
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 List<byte[]> 
data 
protected int 
ndims 
protected DoubleProductQuantiser 
pq 
Modifier  Constructor and Description 

protected 
IncrementalDoubleADCNearestNeighbours() 

IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq,
DataSource<double[]> dataPoints)
Construct the ADC with the given quantiser and data points.


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


IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq,
int ndims)
Construct an empty ADC with the given quantiser.


IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq,
int ndims,
int nitems)
Construct an empty ADC with the given quantiser.


IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq,
List<double[]> dataPoints)
Construct the ADC with the given quantiser and data points.

Modifier and Type  Method and Description 

int 
add(double[] o)
Add a single data item

int[] 
addAll(List<double[]> d)
Insert all the given data

byte[] 
binaryHeader()
Header for binary input.

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

void 
readBinary(DataInput in)
Read internal state from in.

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

void 
writeBinary(DataOutput out)
Write the content of this as binary to out.

distanceFunc, distanceFunc, distanceFunc, distanceFunc
protected DoubleProductQuantiser pq
protected int ndims
protected IncrementalDoubleADCNearestNeighbours()
public IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq, double[][] dataPoints)
pq
 the Product QuantiserdataPoints
 the data points to indexpublic IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq, List<double[]> dataPoints)
pq
 the Product QuantiserdataPoints
 the data points to indexpublic IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq, DataSource<double[]> dataPoints)
pq
 the Product QuantiserdataPoints
 the data points to indexpublic IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq, int ndims)
pq
 the Product Quantiserndims
 the data dimensionalitypublic IncrementalDoubleADCNearestNeighbours(DoubleProductQuantiser pq, int ndims, int nitems)
pq
 the Product Quantiserndims
 the data dimensionalitynitems
 the expected number of data itemspublic int[] addAll(List<double[]> d)
IncrementalNearestNeighbours
addAll
in interface IncrementalNearestNeighbours<double[],double[],IntDoublePair>
d
 the datapublic int add(double[] o)
IncrementalNearestNeighbours
add
in interface IncrementalNearestNeighbours<double[],double[],IntDoublePair>
o
 the object to addpublic int numDimensions()
DoubleNearestNeighbours
numDimensions
in class DoubleNearestNeighbours
public int size()
NearestNeighbours
size
in interface NearestNeighbours<double[],double[],IntDoublePair>
public void readBinary(DataInput in) throws IOException
ReadableBinary
readBinary
in interface ReadableBinary
in
 source to read from.IOException
 an error reading inputpublic byte[] binaryHeader()
ReadableBinary
binaryHeader
in interface ReadableBinary
binaryHeader
in interface WriteableBinary
public void writeBinary(DataOutput out) throws IOException
WriteableBinary
writeBinary
in interface WriteableBinary
out
 sink to write toIOException
 an error writing to outpublic 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
searchNN
in interface NearestNeighbours<double[],double[],IntDoublePair>
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
searchKNN
in interface NearestNeighbours<double[],double[],IntDoublePair>
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
searchNN
in interface NearestNeighbours<double[],double[],IntDoublePair>
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
searchKNN
in interface NearestNeighbours<double[],double[],IntDoublePair>
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.
searchKNN
in interface NearestNeighbours<double[],double[],IntDoublePair>
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.
searchNN
in interface NearestNeighbours<double[],double[],IntDoublePair>
query
 the query vectorprotected void computeDistances(double[] fullQuery, BoundedPriorityQueue<IntDoublePair> queue, IntDoublePair wp)