DETAILED ACTION
Case Status
This office action is in response to remarks and amendments of 12 June 2026. Claims 1-20 have been examined.
Pertinent Prior Art
Prior art that is considered pertinent to applicant's disclosure but not currently relied upon:
US 12536186
Col. 17, lines 30-35
“…a relative neighborhood graph (RNG) … implements a greedy search procedure for nearest neighbors to a vector and a robust [edge pruning] procedure to optimize a graph for vector searches.”
US 20130231862
Pars. 50-64
Using flags to identify shortcut edges and graph transformation based on them
Claim Rejections - 35 USC § 103
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 (i.e., changing from AIA to pre-AIA ) 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.
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.
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over Iwasaki et al., Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data, hereinafter Iwasaki, in view of Fu et al., Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph, hereinafter Fu.
As per claim 1, Iwasaki discloses An information processing apparatus, comprising:
a processor configured to acquire first graph information indicating a first graph in which a plurality of nodes corresponding to each of a plurality of objects to be searched are connected by edges and condition information indicating a determination condition of a shortcut edge to be deleted in a graph (see section 2.6 Graph Construction and Optimization and note that algorithm 8 shows how to construct an adjusted graph (i.e. first graph); and see section 1 which includes “we also propose a path adjustment method for unnecessary shortcut edges that have alternative paths to drastically reduce degrees” (i.e. condition information)); and
the processor further configured to set an oriented edge with a first node as a start point and a second node as an end point among edges included in the first graph as a target edge, and generate second information indicating a second graph in which the target edge is deleted as the shortcut edge […]including at least a third node connected with an oriented edge with the first node as a start point, and a fourth node serving as a start point of an oriented edge with the second node as an end point, the fourth node being a node reachable from the third node, the first node, and the second node satisfies the determination condition of the shortcut edge, […](Section 2.3, Algorithm 4 AdjustPath Output: Gp(Vp,Ep) (i.e. second information indicating a second graph) and also, above-mentioned algorithm 8 provides adjusted graph Gadj (i.e. second information indicating a second graph); section 2.3 “A target edge means an edge that is checked to determine whether it should be removed” and Algorithm 4, line 5 “nd ← argmin x∈N(Gt,n) d(n, x)” (i.e. target edge), “There are many long shortcut edges that can be substituted with an alternative path.” (i.e. shortcut edge), and Algorithm 5 HasPath, line 1 “for all n ∈ N(G, ns) do” wherein n-s- is the start node, and n is a first connected bypass node (i.e. third node) and the next line of the algorithm discloses mapping to the node that connects directly to the destination, where n is the node that has an edge to n--d (i.e. fourth node serving as a start point…)).
Iwasaki does not expressly disclose target edge deletion by iteratively selecting target edges in ascending order of edge length for each of the plurality of nodes and executing shortcut edge detection processing, in a case where a relationship among distances between each of bypass nodes… wherein the second graph reduces a number of edges to be referred during search processing by deleting the shortcut edges from the first graph However, Fu discloses arranging candidate neighbor nodes or edges for a node in ascending order of distance and iteratively selecting candidates for graph construction or pruning. Fu also discloses determining whether to keep or remove an edge based on a distance relationship among nodes, including a triangle type relationship between a source node, a candidate destination node, and an intermediate/previously selected node. Fu, sections 2.3 disclose Relative Neighborhood Graphs (RNG) (i.e. triangle theorem) and sections 3.3-3.5 edge elimination based on RNG.
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine the teachings of the cited references because Fu’s angular logic would have allowed Iwasaki’s graph search technique to provide more spare and efficient graphs, Fu section 4.1.3 B 2, and Fu section 3.5 includes “By approximating the MRNG, the NSG can inherit similar low search complexity as the MRNG. Meanwhile, the degree upper-bound makes the graph very sparse, and the tree-spanning operation guarantees the connectivity of the NSG. The NSG’s index contains only a sparse graph and no auxiliary structures.”
As per claims 13 and 14, they are analogous to claim 1 and are therefore likewise rejected.
As per claim 2, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein the processor acquires the condition information indicating a determination condition of the shortcut edge based on a distance between the bypass node, the first node, and the second node, and the processor generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where a relationship among a distance between the first node and the second node, a distance between the first node and each of the bypass nodes, and a distance between the second node and each of the bypass nodes satisfies a determination condition of the shortcut edge (See rejection of claim 1 and note that the path adjustment condition evaluates three pairwise distances and section 2.3 says “Our path adjustment removes only edges that can be replaced with an alternative path that consists of two edges... However, even though an alternative path consists of only two edges, if any of these edges on the path is longer than the target edge, the target edge is not removed.”).
As per claim 3, Iwasaki as modified discloses The information processing apparatus according to claim 2, wherein the processor generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where a relationship among a distance between the first node and the second node, a distance between the first node and the third node, and a distance between the second node and the third node, and a relationship among a distance between the first node and the second node, a distance between the first node and the fourth node, and a distance between the second node and the fourth node satisfy a determination condition of the shortcut edge (see rejection of claim 2 and note section 2.3, Algorithm 5 HasPath, lines 1-3 disclose pairwise distance checks as claimed).
As per claim 4, Iwasaki as modified discloses The information processing apparatus according to claim 3, wherein the bypass node includes a fifth node that is a node on a path from the third node to the fourth node when the bypass node is reachable from the third node to the fourth node via one or more nodes, and the processor generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where a relationship among a distance between the first node and the second node, a distance between the first node and the fifth node, and a distance between the second node and the fifth node satisfies a determination condition of the shortcut edge (see rejection of claim 2 and note section 2.3 “target edge e1 is not removed because its alternative path {ns, n1, n2, nd} consists of three edges” wherein n1 and n2 are intermediate nodes on the bypass path).
As per claim 5, Iwasaki as modified discloses The information processing apparatus according to claim 2, wherein the processor acquires the condition information indicating a determination condition of the shortcut edge using a distance between the first node and the second node, a distance between the first node and the bypass node, a distance between the second node and the bypass node (see rejection of claim 2 and note section 2.3, Algorithm 5 HasPath, lines 1-3 disclose pairwise distance checks), and a cosine theorem (Fu, sections 2.3 disclose Relative Neighborhood Graphs (RNG) (i.e. triangle theorem) and sections 3.3-3.5 edge elimination based on RNG); and the processor generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where each of calculated values calculated based on a distance between the first node and the second node, a distance between the first node and each of the bypass nodes, a distance between the second node and each of the bypass nodes, and the cosine theorem satisfies a determination condition of the shortcut edge (see Iwasaki and Fu as cited above and note the elimination / deletion of edges in both references, based on distances and calculations as claimed: Fu, sections 2.3 “The RNG adopts an interesting edge selection strategy to eliminate the longest edge in all the possible triangles on S” and Iwasaki, section 2.3 “A target edge means an edge that is checked to determine whether it should be removed”).
As per claim 6, Iwasaki as modified discloses The information processing apparatus according to claim 5, wherein the processor acquires the condition information indicating a determination condition of the shortcut edge based on comparison between each of the calculated values and a threshold, and the processor generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where each of the calculated values is larger than the threshold (see Iwasaki section 1 which includes “we also propose a path adjustment method for unnecessary shortcut edges that have alternative paths to drastically reduce degrees” (i.e. condition information) and Fu discloses comparing a calculated geometric value and a threshold; Fu, sections 2.3, 3.3-3.5 disclose calculating angles between edges (i.e. a calculated value) derived from a “theorem regarding a triangle” and that the angle between two edges sharing the same node is at least 60 degrees (i.e. threshold)).
As per claim 7, Iwasaki as modified discloses The information processing apparatus according to claim 5, wherein the processor acquires the condition information indicating a determination condition of the shortcut edge based on a distance between the first node and the second node, a distance between the first node and the bypass node, a distance between the second node and the bypass node, (Iwasaki see rejection of claim 2 and note section 2.3, Algorithm 5 HasPath, lines 1-3 disclose pairwise distance checks), and a cosine theorem (see Fu as cited in the rejection of claim 5 and note that to implement the 60 degree pruning rule using the distances calculated by Iwasaki, the cosine theorem formula cosC = (a2 + b2 – c2)/2ab would be applied to determine the angular relationship between the target edge and the bypass path), and the processor generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where each of the calculated values calculated based on the distance between the first node and the second node, the distance between the first node and each of the bypass nodes, the distance between the second node and each of the bypass nodes, and the cosine theorem satisfies a determination condition of the shortcut edge (see Iwasaki and Fu as cited above and note the elimination / deletion of edges in both references, based on distances and calculations as claimed: Fu, sections 2.3 “The RNG adopts an interesting edge selection strategy to eliminate the longest edge in all the possible triangles on S” and Iwasaki, section 2.3 “A target edge means an edge that is checked to determine whether it should be removed”).
As per claim 8, Iwasaki as modified discloses The information processing apparatus according to claim 7, wherein the processor uses the cosine theorem to calculate each of the calculated values that is a cosine value of an angle formed by a side between the first node and each of the bypass nodes and a side between the second node and each of the bypass nodes, and generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where the calculated value satisfies a determination condition of the shortcut edge (see Iwasaki and Fu as cited in the rejection of claim 7 and note that in Fu, to implement the 60 degree pruning rule using the distances calculated by Iwasaki, the cosine theorem formula cosC = (a2 + b2 – c2)/2ab would be applied to determine the angular relationship between the target edge and the bypass path).
As per claim 9, Iwasaki in view of Fu discloses The information processing apparatus according to claim 8, wherein the processor acquires the condition information indicating a determination condition of the shortcut edge based on a threshold corresponding to the cosine value, and the processor generates the second information indicating the second graph in which the target edge is deleted as the shortcut edge in a case where each of the calculated values is larger than the threshold (see Iwasaki and Fu as cited in the rejection of claim 7 and note that in Fu, sections 2.3, 3.3-3.5 disclose calculating angles between edges (i.e. a calculated value) derived from a theorem and that the angle between two edges sharing the same node is at least 60 degrees (i.e. is larger than the threshold)).
As per claim 10, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein the processor generates the second information, wherein the second information comprises information for identifying an edge corresponding to the shortcut edge among the edges included in the first graph (see rejection of generation unit limitation of claim 1).
As per claim 11, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein the processor generates the second information wherein the second information comprises a flag that is associated with each of the edges included in the first graph and indicates whether or not the edge is the shortcut edge (algorithm 7 IsSet provides binary flag output true or false that is “associated with each of the edges included in the first graph and indicates whether or not the edge is the shortcut edge”).
As per claim 12, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein the processor generates, the second information wherein the second information comprises a flag in which the shortcut edge included in the first graph is deleted (see rejection of claim 1 and note Iwasaki, Algorithm 4, the output graph has shortcut edges removed).
As per claim 15, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein the processor is further configured to execute search processing using the second graph to extract a node similar to a query from the plurality of nodes (Iwasaki, algorithm 1, KnnSearch inputs graph G and query object q and outputs result set R of k nearest neighbor nodes; and algorithm 8 constructs adjusted graph Gadj using AdjustPath).
As per claim 16, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein the processor is further configured to receive a query from a terminal device and provide, to the terminal device, an object ID indicating an object corresponding to the query based on search processing using the second graph (as cited in the rejection of claim 1, Iwasaki discloses receiving query object q and returning search result R identifying nearest nodes/objects and Fu further teaches applying graph based ANN search to receive a query and return nearest neighbor search results).
As per claim 17, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein the first graph is a k-nearest neighbor graph or an approximate k-nearest neighbor graph (Iwasaki, sections 1 and 3).
As per claim 18, Iwasaki as modified discloses The information processing apparatus according to claim 1, wherein each of the plurality of objects comprises vector information, and the proximity search comprises an image retrieval service that searches for an image corresponding to a query image (Iwasaki abstract and sections 1 and 3 disclose searching vector objects extracted from documents, images, etc. and uses SIFT/GIST image descriptors for proximity search).
As per claim 19, Iwasaki as modified discloses the information processing apparatus according to claim 1, wherein the processor is further configured to equalize a number of deleted edges for each of the plurality of nodes by iteratively selecting target edges in ascending order of edge length (Iwasaki, section 2.3 discloses processing each node in the graph and selecting, for each node, the nearest or shortest remaining neighbor edge using argmin d(n,x) before determining whether the edge has an alternative path and should be removed, this means edges are processed on a per node basis in ascending edge-length order and Fu discloses distance ordered candidate edge selection or graph pruning).
As per claim 20, Iwasaki as modified discloses The information processing apparatus according to claim 1, further comprising a memory configured to store the first graph and the second information, wherein the second information enables determination of presence or absence of each edge in the second graph (Iwasaki, section 2.3 discloses input graph G(V,E) and output adjusted/path-adjusted graph Gp(Vp,Ep) where the resulting edge set Ep identifies which edges remain after shortcut edge deletion which enables determine of presence or absence of each second graph edge).
Response to Arguments
Applicant's arguments filed 12 June 2026 have been considered.
The 35 USC 101 rejection is withdrawn in view of the argument that the claimed invention integrates the abstract idea into a practical application that provides an improvement to a technical field. It is noted that the claims themselves reflect the disclosed improvement. That is, the claims include the components or steps of the invention that provide the improvement described in the specification. MPEP § 2106.04(d)(1).
Regarding the prior art rejection, page 13 of the remarks include:
PNG
media_image1.png
186
636
media_image1.png
Greyscale
Examiner respectfully disagrees. Fu is relied upon for its distance ordered candidate processing and distance-based edge pruning. Iwasaki already teaches per-node selection of shortest remaining edges and shortcut edge deletion. Fu further supports arranging candidate neighbor nodes or edges in ascending distance order before applying pruning. Thus, the combination obviates iteratively selecting target edges in ascending order of edge length for each node, even if Fu’s specific pruning condition is geometrically expressed as a lune-based rule.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SYED HASAN whose telephone number is (571)270-5008. The examiner can normally be reached M-F 8am - 5 pm.
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, Boris Gorney can be reached at (571)270-5626. 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.
/SYED H HASAN/Primary Examiner, Art Unit 2154
