Associative graph search
An associative graph search system includes a KNN graph determiner to determine in advance W neighbors of each item in a dataset and to store each item and its neighbors in a KNN graph, a reduced dimension vector finder implemented on an associative processing unit (APU) to find a first number of first nearest neighbors of a query vector, the APU operating in a constant complexity irrespective of the size of the number, a result expander to find for each first nearest neighbor, W second nearest neighbors using the KNN graph thereby creating a group of neighbors, and a KNN full dimension vector re-ranker to find a final number of full dimension nearest neighbors of the full dimension query vector from the group of neighbors.
1 . An associative graph search system comprising:
a K-nearest neighbor (KNN) KNN graph determiner to determine in advance W neighbors of each item in a full dimension vector dataset and to store each item and its neighbors in a KNN graph;
an associative processing unit (APU) comprising an associative memory array storing at least a dataset of reduced dimension vectors and activating a KNN search within said associative memory array on said dataset;
a reduced dimension vector finder to instruct said APU to find a first number of first nearest neighbors of a reduced dimension version of a full dimension query vector in said dataset, said APU operating in a constant complexity irrespective of the size of said first number;
a result expander to find for each first nearest neighbor, W second nearest neighbors using said KNN graph thereby creating a group of neighbors; and
a KNN full dimension vector re-ranker to find a final number of full dimension nearest neighbors of said full dimension query vector from said group of neighbors.
2 . The associative graph search system of claim 1 , said reduced dimension vector finder to use a similarity search method which is one of: Hamming distance, L1, L2, and Tanimoto.
3 . The associative graph search system of claim 1 said associative graph search system to expand said group of neighbors by activating said result expander on said second nearest neighbors.
4 . A method comprising:
a host processor providing a received a full dimension query vector to an associative processing unit (APU) comprising an associative memory array storing at least a dataset of reduced dimension vectors;
in said APU, reducing a dimension of said query vector to generate a reduced dimension query vector;
said APU activating a first K nearest neighbor (KNN) algorithm within said associative memory array to find a small number of nearest neighbors of said reduced dimension query vector in said dataset, said KNN algorithm operating in a constant complexity irrespective of the size of said small number;
expanding in said host processor said small number to a larger number of nearest neighbors by using a KNN graph;
fetching in said host processor full dimension vectors associated with said larger number of nearest neighbors; and
activating in said host processor a second K nearest neighbor (KNN) algorithm to find final K full dimension nearest neighbors of said query vector.
5 . The method of claim 4 wherein said activating a first K nearest neighbor (KNN) algorithm comprises using a similarity search method which is one of: Hamming distance, L1, L2, and Tanimoto.
6 . The method of claim 4 wherein said expanding is activated on said larger number of nearest neighbors to further expand the number of nearest neighbors.
7 . A method for associative graph search for finding a K nearest neighbors of a query object, the method comprising:
having a K-nearest neighbor (KNN) graph containing an index of an object to a database and W indexes of known neighbors of said object stored in a host processor, said database storing full dimension vectors of objects;
having a plurality of reduced dimension vectors stored in an associative memory array forming part of an associative processing unit (APU);
obtaining in said APU a reduced dimension query vector of said query object;
performing in said APU a first k nearest neighbor (KNN) algorithm to find a first set of nearest neighbor objects of said reduced dimension query vector in a dataset of reduced dimension vectors stored in said APU, said performing occurring in a constant complexity irrespective of the size of said first set;
obtaining in said host processor for each of said nearest neighbor object additional known neighbors from said KNN graph;
fetching in said host processor full dimension vectors of all said first neighbors and said additional known neighbors; and
performing in said host processor a second KNN search algorithm to find said K nearest neighbors of said query object out of said first neighbors and said additional known neighbors.
8 . The method of claim 7 wherein said performing a first K nearest neighbor (KNN) algorithm comprises using a similarity search method which is one of: Hamming distance, L1, L2, and Tanimoto.
9 . The method of claim 7 wherein said obtaining is activated on said known neighbors to further expand a number of said nearest neighbors.