DoubleADCNearestNeighbours (OpenIMAJ master project 1.3.10 API)

java.lang.Object
- org.openimaj.knn.DoubleNearestNeighbours
- - org.openimaj.knn.pq.DoubleADCNearestNeighbours

All Implemented Interfaces:: NearestNeighbours<double[],double[],IntDoublePair>

Direct Known Subclasses:: DoubleSDCNearestNeighbours

@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 DoubleADCNearestNeighbours
extends DoubleNearestNeighbours

Nearest-neighbours using Asymmetric Distance Computation (ADC) on Product Quantised vectors. In ADC, only the database points are quantised. The queries themselves are not quantised. The overall distance is computed as the summed distance of each subvector of the query to each corresponding centroids of each database vector.

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.

Author:: Jonathon Hare (jsh2@ecs.soton.ac.uk)

Field Summary

Fields
Modifier and Type Field and Description

protected byte[][] data

protected int ndims

protected DoubleProductQuantiser pq

Fields
Modifier and Type	Field and Description
`protected byte[][]`	`data`
`protected int`	`ndims`
`protected DoubleProductQuantiser`	`pq`

Constructor Summary

Constructors
Constructor and Description
`DoubleADCNearestNeighbours(DoubleProductQuantiser pq, byte[][] pqData, int ndims)` Construct the ADC with the given quantiser and pre-quantised data .
`DoubleADCNearestNeighbours(DoubleProductQuantiser pq, double[][] dataPoints)` Construct the ADC with the given quantiser and data points.

Method Summary

All Methods Instance Methods Concrete Methods
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

Methods inherited from class org.openimaj.knn.DoubleNearestNeighbours
distanceFunc, distanceFunc, distanceFunc, distanceFunc

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - pq
```
protected final DoubleProductQuantiser pq
```
  - ndims
```
protected final int ndims
```
  - data
```
protected final byte[][] data
```
- Constructor Detail
  - DoubleADCNearestNeighbours
```
public DoubleADCNearestNeighbours(DoubleProductQuantiser pq,
                                  double[][] dataPoints)
```
    Construct the ADC with the given quantiser and data points.
    
    Parameters:
    
    pq - the Product Quantiser
    
    dataPoints - the data points to index
  - DoubleADCNearestNeighbours
```
public DoubleADCNearestNeighbours(DoubleProductQuantiser pq,
                                  byte[][] pqData,
                                  int ndims)
```
    Construct the ADC with the given quantiser and pre-quantised data .
    
    Parameters:
    
    pq - the Product Quantiser
    
    pqData - the pre-quantised data (i.e. vectors already quantised with the given pq)
    
    ndims - the dimensionality of the indexed data
- Method Detail
  - searchNN
```
public void searchNN(double[][] qus,
                     int[] indices,
                     double[] distances)
```
    Description copied from interface: NearestNeighbours
    
    Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.
    For 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
    
    Parameters:
    
    qus - An array of N query vectors
    
    indices - 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.
  - searchKNN
```
public void searchKNN(double[][] qus,
                      int K,
                      int[][] indices,
                      double[][] distances)
```
    Description copied from interface: NearestNeighbours
    
    Search for the K nearest neighbours to each of the N queries, and return the indices of each nearest neighbour and their respective distances.
    For 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
    
    Parameters:
    
    qus - An array of N query vectors
    
    K - the number of neighbours to find
    
    indices - 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.
  - searchNN
```
public void searchNN(List<double[]> qus,
                     int[] indices,
                     double[] distances)
```
    Description copied from interface: NearestNeighbours
    
    Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.
    For 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
    
    Parameters:
    
    qus - An array of N query vectors
    
    indices - 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.
  - searchKNN
```
public void searchKNN(List<double[]> qus,
                      int K,
                      int[][] indices,
                      double[][] distances)
```
    Description copied from interface: NearestNeighbours
    
    Search for the K nearest neighbours to each of the N queries, and return the indices of each nearest neighbour and their respective distances.
    For 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
    
    Parameters:
    
    qus - An array of N query vectors
    
    K - the number of neighbours to find
    
    indices - 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.
  - searchKNN
```
public List<IntDoublePair> searchKNN(double[] query,
                                     int K)
```
    Description copied from interface: NearestNeighbours
    
    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.
    If k neighbours cannot be determined, then the resultant list might have fewer than k elements.
    
    Parameters:
    
    query - the query vector
    
    K - the number of neighbours to search for
    
    Returns:
    
    the top K nearest neighbours ordered by increasing distance
  - searchNN
```
public IntDoublePair searchNN(double[] query)
```
    Description copied from interface: NearestNeighbours
    
    Search for the nearest neighbour to the given query and return a pair containing the distance and index of that neighbour.
    If the nearest-neighbour cannot be determined null will be returned.
    
    Parameters:
    
    query - the query vector
    
    Returns:
    
    the distance and index of the nearest neighbour
  - computeDistances
```
protected void computeDistances(double[] fullQuery,
                                BoundedPriorityQueue<IntDoublePair> queue,
                                IntDoublePair wp)
```
  - numDimensions
```
public int numDimensions()
```
    Description copied from class: DoubleNearestNeighbours
    
    Get the number of dimensions of each vector in the dataset
    
    Specified by:
    
    numDimensions in class DoubleNearestNeighbours
    
    Returns:
    
    the number of dimensions
  - size
```
public int size()
```
    Description copied from interface: NearestNeighbours
    
    Get the size of the dataset
    
    Returns:
    
    the dataset size

Class DoubleADCNearestNeighbours

Field Summary

Constructor Summary

Method Summary

Methods inherited from class org.openimaj.knn.DoubleNearestNeighbours

Methods inherited from class java.lang.Object

Field Detail

pq

ndims

data

Constructor Detail

DoubleADCNearestNeighbours

DoubleADCNearestNeighbours

Method Detail

searchNN

searchKNN

searchNN

searchKNN

searchKNN

searchNN

computeDistances

numDimensions

size