@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 IncrementalShortADCNearestNeighbours extends ShortNearestNeighbours implements IncrementalNearestNeighbours<short[],float[],IntFloatPair>, ReadWriteableBinary
For efficiency, the distance of each sub-vector of a query is computed to every centroid (for the sub-vector 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 ShortProductQuantiser |
pq |
| Modifier | Constructor and Description |
|---|---|
protected |
IncrementalShortADCNearestNeighbours() |
|
IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq,
DataSource<short[]> dataPoints)
Construct the ADC with the given quantiser and data points.
|
|
IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq,
int ndims)
Construct an empty ADC with the given quantiser.
|
|
IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq,
int ndims,
int nitems)
Construct an empty ADC with the given quantiser.
|
|
IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq,
List<short[]> dataPoints)
Construct the ADC with the given quantiser and data points.
|
|
IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq,
short[][] dataPoints)
Construct the ADC with the given quantiser and data points.
|
| Modifier and Type | Method and Description |
|---|---|
int |
add(short[] o)
Add a single data item
|
int[] |
addAll(List<short[]> d)
Insert all the given data
|
byte[] |
binaryHeader()
Header for binary input.
|
protected void |
computeDistances(short[] fullQuery,
BoundedPriorityQueue<IntFloatPair> queue,
IntFloatPair 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(List<short[]> qus,
int K,
int[][] indices,
float[][] 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.
|
void |
searchKNN(short[][] qus,
int K,
int[][] indices,
float[][] 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<IntFloatPair> |
searchKNN(short[] 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 |
searchNN(List<short[]> qus,
int[] indices,
float[] distances)
Search for the nearest neighbour to each of the N queries, and return the
index of each nearest neighbour and the respective distance.
|
IntFloatPair |
searchNN(short[] query)
Search for the nearest neighbour to the given query and return a pair
containing the distance and index of that neighbour.
|
void |
searchNN(short[][] qus,
int[] indices,
float[] 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, distanceFuncprotected ShortProductQuantiser pq
protected int ndims
protected IncrementalShortADCNearestNeighbours()
public IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq, short[][] dataPoints)
pq - the Product QuantiserdataPoints - the data points to indexpublic IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq, List<short[]> dataPoints)
pq - the Product QuantiserdataPoints - the data points to indexpublic IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq, DataSource<short[]> dataPoints)
pq - the Product QuantiserdataPoints - the data points to indexpublic IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq, int ndims)
pq - the Product Quantiserndims - the data dimensionalitypublic IncrementalShortADCNearestNeighbours(ShortProductQuantiser pq, int ndims, int nitems)
pq - the Product Quantiserndims - the data dimensionalitynitems - the expected number of data itemspublic int[] addAll(List<short[]> d)
IncrementalNearestNeighboursaddAll in interface IncrementalNearestNeighbours<short[],float[],IntFloatPair>d - the datapublic int add(short[] o)
IncrementalNearestNeighboursadd in interface IncrementalNearestNeighbours<short[],float[],IntFloatPair>o - the object to addpublic int numDimensions()
ShortNearestNeighboursnumDimensions in class ShortNearestNeighbourspublic int size()
NearestNeighbourssize in interface NearestNeighbours<short[],float[],IntFloatPair>public void readBinary(DataInput in) throws IOException
ReadableBinaryreadBinary in interface ReadableBinaryin - source to read from.IOException - an error reading inputpublic byte[] binaryHeader()
ReadableBinarybinaryHeader in interface ReadableBinarybinaryHeader in interface WriteableBinarypublic void writeBinary(DataOutput out) throws IOException
WriteableBinarywriteBinary in interface WriteableBinaryout - sink to write toIOException - an error writing to outpublic void searchNN(short[][] qus, int[] indices, float[] distances)
NearestNeighboursFor efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.
If a nearest-neighbour cannot be determined, it will have an index value of -1
searchNN in interface NearestNeighbours<short[],float[],IntFloatPair>qus - An array of N query vectorsindices - The return N-dimensional array for holding the indices of the
nearest neighbour of each respective query.distances - The return N-dimensional array for holding the distances of
the nearest neighbour to each respective query.public void searchKNN(short[][] qus, int K, int[][] indices, float[][] distances)
NearestNeighboursFor efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.
If a k-th nearest-neighbour cannot be determined, it will have an index value of -1
searchKNN in interface NearestNeighbours<short[],float[],IntFloatPair>qus - An array of N query vectorsK - the number of neighbours to findindices - The return N*K-dimensional array for holding the indices of
the K nearest neighbours of each respective query.distances - The return N*K-dimensional array for holding the distances of
the nearest neighbours of each respective query.public void searchNN(List<short[]> qus, int[] indices, float[] distances)
NearestNeighboursFor efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.
If a nearest-neighbour cannot be determined, it will have an index value of -1
searchNN in interface NearestNeighbours<short[],float[],IntFloatPair>qus - An array of N query vectorsindices - The return N-dimensional array for holding the indices of the
nearest neighbour of each respective query.distances - The return N-dimensional array for holding the distances of
the nearest neighbour to each respective query.public void searchKNN(List<short[]> qus, int K, int[][] indices, float[][] distances)
NearestNeighboursFor efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.
If a k-th nearest-neighbour cannot be determined, it will have an index value of -1
searchKNN in interface NearestNeighbours<short[],float[],IntFloatPair>qus - An array of N query vectorsK - the number of neighbours to findindices - The return N*K-dimensional array for holding the indices of
the K nearest neighbours of each respective query.distances - The return N*K-dimensional array for holding the distances of
the nearest neighbours of each respective query.public List<IntFloatPair> searchKNN(short[] query, int K)
NearestNeighboursIf k neighbours cannot be determined, then the resultant list might have fewer than k elements.
searchKNN in interface NearestNeighbours<short[],float[],IntFloatPair>query - the query vectorK - the number of neighbours to search forpublic IntFloatPair searchNN(short[] query)
NearestNeighbours
If the nearest-neighbour cannot be determined null will be
returned.
searchNN in interface NearestNeighbours<short[],float[],IntFloatPair>query - the query vectorprotected void computeDistances(short[] fullQuery, BoundedPriorityQueue<IntFloatPair> queue, IntFloatPair wp)