@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 IncrementalLongADCNearestNeighbours extends LongNearestNeighbours implements IncrementalNearestNeighbours<long[],double[],IntDoublePair>, 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 LongProductQuantiser |
pq |
| Modifier | Constructor and Description |
|---|---|
protected |
IncrementalLongADCNearestNeighbours() |
|
IncrementalLongADCNearestNeighbours(LongProductQuantiser pq,
DataSource<long[]> dataPoints)
Construct the ADC with the given quantiser and data points.
|
|
IncrementalLongADCNearestNeighbours(LongProductQuantiser pq,
int ndims)
Construct an empty ADC with the given quantiser.
|
|
IncrementalLongADCNearestNeighbours(LongProductQuantiser pq,
int ndims,
int nitems)
Construct an empty ADC with the given quantiser.
|
|
IncrementalLongADCNearestNeighbours(LongProductQuantiser pq,
List<long[]> dataPoints)
Construct the ADC with the given quantiser and data points.
|
|
IncrementalLongADCNearestNeighbours(LongProductQuantiser pq,
long[][] dataPoints)
Construct the ADC with the given quantiser and data points.
|
| Modifier and Type | Method and Description |
|---|---|
int |
add(long[] o)
Add a single data item
|
int[] |
addAll(List<long[]> d)
Insert all the given data
|
byte[] |
binaryHeader()
Header for binary input.
|
protected void |
computeDistances(long[] 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(List<long[]> 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.
|
void |
searchKNN(long[][] 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(long[] 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<long[]> 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.
|
IntDoublePair |
searchNN(long[] query)
Search for the nearest neighbour to the given query and return a pair
containing the distance and index of that neighbour.
|
void |
searchNN(long[][] 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, distanceFuncprotected LongProductQuantiser pq
protected int ndims
protected IncrementalLongADCNearestNeighbours()
public IncrementalLongADCNearestNeighbours(LongProductQuantiser pq, long[][] dataPoints)
pq - the Product QuantiserdataPoints - the data points to indexpublic IncrementalLongADCNearestNeighbours(LongProductQuantiser pq, List<long[]> dataPoints)
pq - the Product QuantiserdataPoints - the data points to indexpublic IncrementalLongADCNearestNeighbours(LongProductQuantiser pq, DataSource<long[]> dataPoints)
pq - the Product QuantiserdataPoints - the data points to indexpublic IncrementalLongADCNearestNeighbours(LongProductQuantiser pq, int ndims)
pq - the Product Quantiserndims - the data dimensionalitypublic IncrementalLongADCNearestNeighbours(LongProductQuantiser pq, int ndims, int nitems)
pq - the Product Quantiserndims - the data dimensionalitynitems - the expected number of data itemspublic int[] addAll(List<long[]> d)
IncrementalNearestNeighboursaddAll in interface IncrementalNearestNeighbours<long[],double[],IntDoublePair>d - the datapublic int add(long[] o)
IncrementalNearestNeighboursadd in interface IncrementalNearestNeighbours<long[],double[],IntDoublePair>o - the object to addpublic int numDimensions()
LongNearestNeighboursnumDimensions in class LongNearestNeighbourspublic int size()
NearestNeighbourssize in interface NearestNeighbours<long[],double[],IntDoublePair>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(long[][] qus, int[] indices, double[] 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<long[],double[],IntDoublePair>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(long[][] qus, int K, int[][] indices, double[][] 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<long[],double[],IntDoublePair>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<long[]> qus, int[] indices, double[] 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<long[],double[],IntDoublePair>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<long[]> qus, int K, int[][] indices, double[][] 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<long[],double[],IntDoublePair>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<IntDoublePair> searchKNN(long[] query, int K)
NearestNeighboursIf k neighbours cannot be determined, then the resultant list might have fewer than k elements.
searchKNN in interface NearestNeighbours<long[],double[],IntDoublePair>query - the query vectorK - the number of neighbours to search forpublic IntDoublePair searchNN(long[] query)
NearestNeighbours
If the nearest-neighbour cannot be determined null will be
returned.
searchNN in interface NearestNeighbours<long[],double[],IntDoublePair>query - the query vectorprotected void computeDistances(long[] fullQuery, BoundedPriorityQueue<IntDoublePair> queue, IntDoublePair wp)