DETAILED ACTION
1. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
2. In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
3. Claims 1-18, filed on 3/11/2025, are pending in this office action.
Claim Objections
4. Claims 2, 5, 6, 11, 14, and 15 are objected to because of the following informalities:
Claims 2 and 11 recite the acronym “IVF”, yet the claims do not define what the acronym means. Please define the acronym before use.
Claims 5 and 14 recite the acronym “SIMD”, yet the claims do not define what the acronym means. Please define the acronym before use.
Claims 6 and 15 recite the acronym “HNSW”, yet the claims do not define what the acronym means. Please define the acronym before use.
Appropriate correction is required.
Claim Rejections - 35 USC § 103
5. The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
6. Claim(s) 1, 6-10, and 15-18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Xu et al. (US Publication 2022/0327128 A1) in view of He et al. (US publication 2022/0129448 A1).
As per claim 1, Xu teaches A method comprising: (see Abstract)
receiving a vector query that includes a query vector and a predicate on a column of a base table that stores a plurality of vectors; (paragraph 0024, 0034, a querying apparatus receives a query for candidate vector sets comprising object vectors, the query of object vectors interpreted as a query vector, paragraph 0051, 0054, the querying utilizing a lookup table of calculations and expressions for vectors)
in response to receiving the vector query and while traversing a vector index, that is based on the plurality of vectors: based on the query vector, identifying a set of candidate vectors; (paragraph 0020, 0028, 0034, 0036, candidate vector set similar to the query are determined)
for each candidate vector in the set of candidate vectors: identifying, in the vector index, a value, associated with said each candidate vector, for the column, and determining whether the value satisfies the predicate; (Table 1, paragraph 0036, 0043, 0066, a second number of similar candidate vectors are calculated based on calculation result in response to query)
and selecting a strict subset, of the set of candidate vectors, whose values for the column satisfy the predicate; (Table 1, paragraph 0036, 0047, 0063, a plurality of candidate vector subsets are determined
for each candidate vector in the strict subset, computing a vector distance between the query vector and said each candidate vector; (paragraph 0042, 0066, distance between object vector and candidate vectors are calculated)
wherein the method is performed by one or more computing devices. (Figure 1, paragraph 0049, data interface)
Xu does not explicitly indicate a predicate on a non-vector column of a base table that stores a plurality of vectors.
He teaches a predicate on a non-vector column of a base table that stores a plurality of vectors. (paragraph 0036, 0037, a table referenced by a query contains values of vector representations, paragraph 0040, a query referencing a column attribute, interpreted as a non-vector column, paragraph 0043, 0054, 0070, the table having column attributes with feature vectors)
It would have been obvious for one of ordinary skill in the art at the time the invention was made to combine Xu’s method of querying vectors in a candidate vector set based on similarity with He’s ability to provide a column attribute associated with feature vectors utilized in query processing. This gives the user the ability to query tables having column attributes to identify similar vectors. The motivation for doing so would be to better response to queries (paragraph 0004).
As per claim 6, Xu teaches the vector index is an HNSW index that comprises a vector table and a neighbor graph that comprises a plurality of levels that comprises a particular level comprising a graph of nodes representing neighbor relationships among vectors in the plurality of vectors; traversing the vector index comprises, while traversing the graph of nodes: maintaining a candidates heap and a results heap; for each node of multiple nodes in the graph of nodes: adding, to the candidates heap, a node identifier of said each node; wherein identifying the value in the vector index comprises identifying the value in an entry, of the HNSW index, that is associated with the vector that corresponds to the node identifier; determining whether to add the node identifier to the results heap only after determining that the value satisfies the predicate. (paragraph 0021, inverted file system product to convert vector into centroid values, paragraph 0035, nearest N centroids, paragraph 0045, 0047, results tables)
As per claim 7, Xu teaches the vector query is a top-K vector query that specifies a number of items to return, wherein the number of candidate vectors in the strict subset is equal to the number of items to return. (paragraph 0024, top N vector subsets)
As per claim 8, Xu teaches processing a transaction, wherein processing the transaction causes one or more changes to be made to the base table; prior to committing the transaction, causing the one or more changes to be reflected persistently in storage. (paragraph 0037, dynamically defined memory)
As per claim 9, Xu teaches causing the one or more changes to be reflected persistently in storage comprises: modifying the vector index to reflect the one or more changes; or storing the one or more changes in a shared change log that is persistently stored. (paragraph 0045, 0047, generate results tables)
As per claim 10, Xu teaches One or more non-transitory storage media storing instructions which, when executed by one or more computing devices, cause: (see Abstract)
receiving a vector query that includes a query vector and a predicate on a column of a base table that stores a plurality of vectors; (paragraph 0024, 0034, a querying apparatus receives a query for candidate vector sets comprising object vectors, the query of object vectors interpreted as a query vector, paragraph 0051, 0054, the querying utilizing a lookup table of calculations and expressions for vectors)
in response to receiving the vector query and while traversing a vector index, that is based on the plurality of vectors: based on the query vector, identifying a set of candidate vectors; (paragraph 0028, 0034, 0036, candidate vector set similar to the query are determined)
for each candidate vector in the set of candidate vectors: identifying, in the vector index, a value, associated with said each candidate vector, for the column, and determining whether the value satisfies the predicate; (paragraph 0043, 0066, a second number of similar candidate vectors are calculated based on calculation result in response to query)
and selecting a strict subset, of the set of candidate vectors, whose values for the column satisfy the predicate; (paragraph 0036, 0047, 0063, a plurality of candidate vector subsets are determined
for each candidate vector in the strict subset, computing a vector distance between the query vector and said each candidate vector; (paragraph 0042, 0066, distance between object vector and candidate vectors are calculated)
wherein the method is performed by one or more computing devices. (Figure 1, paragraph 0049, data interface)
Xu does not explicitly indicate a predicate on a non-vector column of a base table that stores a plurality of vectors.
He teaches a predicate on a non-vector column of a base table that stores a plurality of vectors. (paragraph 0036, 0037, a table referenced by a query contains values of vector representations, paragraph 0040, a query referencing a column attribute, interpreted as a non-vector column, paragraph 0043, 0054, 0070, the table having column attributes with feature vectors)
It would have been obvious for one of ordinary skill in the art at the time the invention was made to combine Xu’s method of querying vectors in a candidate vector set based on similarity with He’s ability to provide a column attribute associated with feature vectors utilized in query processing. This gives the user the ability to query tables having column attributes to identify similar vectors. The motivation for doing so would be to better response to queries (paragraph 0004).
As per claim 15, Xu teaches the vector index is an HNSW index that comprises a vector table and a neighbor graph that comprises a plurality of levels that comprises a particular level comprising a graph of nodes representing neighbor relationships among vectors in the plurality of vectors; traversing the vector index comprises, while traversing the graph of nodes: maintaining a candidates heap and a results heap; for each node of multiple nodes in the graph of nodes: adding, to the candidates heap, a node identifier of said each node; wherein identifying the value in the vector index comprises identifying the value in an entry, of the HNSW index, that is associated with the vector that corresponds to the node identifier; determining whether to add the node identifier to the results heap only after determining that the value satisfies the predicate. (paragraph 0021, inverted file system product to convert vector into centroid values, paragraph 0035, nearest N centroids, paragraph 0045, 0047, results tables)
As per claim 16, Xu teaches the vector query is a top-K vector query that specifies a number of items to return, wherein the number of candidate vectors in the strict subset is equal to the number of items to return. (paragraph 0024, top N vector subsets)
As per claim 17, Xu teaches processing a transaction, wherein processing the transaction causes one or more changes to be made to the base table; prior to committing the transaction, causing the one or more changes to be reflected persistently in storage. (paragraph 0037, dynamically defined memory)
As per claim 18, Xu teaches causing the one or more changes to be reflected persistently in storage comprises: modifying the vector index to reflect the one or more changes; or storing the one or more changes in a shared change log that is persistently stored. (paragraph 0045, 0047, generate results tables)
Allowable Subject Matter
7. The following is a statement of reasons for the indication of allowable subject matter:
Claims 2-5 and 11-14 contain allowable subject matter over the prior art of record because the prior art of record fails to teach or fairly suggest the vector index is an IVF index that comprises a centroids table and a centroid partitions table that stores the plurality of vectors and values of the non-vector column; traversing the vector index comprises: for each centroid in the centroids table: generating a similarity score between the query vector and said each centroid; adding the similarity score to a set of similarity scores; identifying a strict subset of the set of similarity scores; for each similarity score in the strict subset: identifying a partition, in the centroids partition table, that corresponds to the centroid of said each similarity score; wherein identifying the set of candidate vectors comprises identifying candidate vectors in the partition; wherein identifying the value in the vector index comprises identifying the value associated with the partition., as disclosed in dependent claim 2 and similarly in dependent claim 11. Specifically, the prior art of Xu in view of He teaches querying vectors in a candidate vector set based on similarity and column attributes, but does not explicitly indicate the vector index that is traversed is an IVF index comprising a centroids table and a centroid partitions table storing vectors and values of non-vector columns, the centroids utilized to generate similarity scores between query vectors and centroids, and utilizing the similarity score to identify partitions.
Claim 2-5 and 11-14 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Zhang (US Publication 2020/0311077 A1)
Veit (US Publication 2023/0111978 A1)
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DANGELINO N GORTAYO whose telephone number is (571)272-7204. The examiner can normally be reached Monday-Friday 7:00am - 3:30pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Charles Rones can be reached at 571-272-4085. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/DANGELINO N GORTAYO/Primary Examiner, Art Unit 2168