Associative graph search

Patent metadata

Field	Value
Publication number	US-12488002-B2
Application number	US-202217735139-A
Country	US
Kind code	B2
Filing date	May 3, 2022
Priority date	May 23, 2021
Publication date	Dec 2, 2025
Grant date	Dec 2, 2025

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• Gsi Technology Inc

Inventors

• Akerib Avidan

Classifications

• G06F16/2264

  Multidimensional index structures · CPC title

• G06F18/241

  relating to the classification model, e.g. parametric or non-parametric approaches · CPC title

• G06F18/2323

  based on graph theory, e.g. minimum spanning trees [MST] or graph cuts · CPC title

• G06F16/90335

  Query processing · CPC title

• G06F16/24553 Primary

  of query operations · CPC title