Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
DETAILED ACTION
This action is response to the communication filed on May 6, 2025. Claims 1-20 are pending.
Claim Objections
Claims 1-20 are objected to because of the following informalities: the limitation “DSQ” need to be spell out at the first instance. Appropriate correction is required.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. Regarding the claim 1, it recites executing a breadth first search (BFS) algorithm as part of a graph query to find one or more paths from a source vertex to a destination vertex, wherein: a hash table stores information for each visited vertex, executing the BFS algorithm comprises: reading a set of vertices representing a subpath from an entry in a first DSQ representing a current BFS level, wherein the subpath ends at a current vertex; expanding the current vertex to one or more neighbor vertices; storing information for the current vertex in the hash table; and for each neighbor vertex in the one or more neighbor vertices, storing a new subpath comprising the set of vertices and the neighbor vertex in a second DSQ representing a next BFS level, wherein the method is performed by one or more computing devices.
The claim recited the limitation of executing a breadth first search (BFS) algorithm as part of a graph query to find one or more paths from a source vertex to a destination vertex, wherein: a hash table stores information for each visited vertex, executing the BFS algorithm comprises: reading a set of vertices representing a subpath from an entry in a first DSQ representing a current BFS level, wherein the subpath ends at a current vertex; storing information for the current vertex in the hash table; and for each neighbor vertex in the one or more neighbor vertices, storing a new subpath comprising the set of vertices and the neighbor vertex in a second DSQ representing a next BFS level, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind. User can mentally execute an algorithm (such BFS algorithm as claimed), read information (such as set of vertices as claimed) and memorize (storing as claimed) those information. If necessary, user can also use physical aid such as pencil and paper. See MPEP 2106.04(a)(2) III, B, If a claim recites a limitation that can practically be performed in the human mind, with or without the use of a physical aid such as pen and paper, the limitation falls within the mental processes grouping, and the claim recites an abstract idea. See, e.g., Benson, 409 U.S. at 67, 65, 175 USPQ at 674-75, 674 (noting that the claimed "conversion of [binary-coded decimal] numerals to pure binary numerals can be done mentally," i.e., "as a person would do it by head and hand."). Therefor these limitations are mental process.
The claim recited one additional element: expanding the current vertex to one or more neighbor vertices. The expanding step as recited amounts to data processing and manipulation, which is a form of insignificant extra-solution activity. Accordingly, even in combination, the additional element does not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea. The claim is directed to the abstract idea.
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional element of expanding step amounts to no more than mere instructions to apply the exception using a generic computer component. The courts have recognized these functions as well‐understood, routine, and conventional as they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity (see MPEP 2106.05(d) II, Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information)). Mere instructions to apply an exception using a generic computer component cannot provide an inventive concept. The claim is not patent eligible.
Claim 2 is dependent on claim 1 and includes all the limitations of claim 1. Therefore, claim 2 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of the hash table comprises a disk-spilling hash (DSH) table, the DSH table has a plurality of DSH partitions, each partition of the plurality of DSH partitions is associated with a DSQ representing a current BFS level and a DSQ representing a next BFS level, wherein last vertices of subpaths stored in a given DSQ belong to a same DSH partition, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 3 is dependent on claim 2 and includes all the limitations of claim 2. Therefore, claim 3 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of the DSH table maps each visited vertex to the information for the visited vertex based on a first hash function, and the DSH table is partitioned based on a second hash function, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 4 is dependent on claim 3 and includes all the limitations of claim 3. Therefore, claim 4 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of wherein storing the new subpath comprising the set of vertices and the neighbor vertex in the second DSQ comprises determining a particular DSH partition associated with the neighbor vertex based on the second hash function, wherein the second DSQ is associated with the particular DSH partition, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 5 is dependent on claim 2 and includes all the limitations of claim 2. Therefore, claim 5 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of an active DSH partition and a hash table for the active DSH partition are stored in memory, and at least one partition of the plurality of DSH partitions is stored in external storage, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 6 is dependent on claim 5 and includes all the limitations of claim 5. Therefore, claim 6 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of wherein executing the BFS algorithm further comprises: in response to all sets of vertices being read from the active DSH partition: reading a next DSH partition into memory; building a hash table for the next DSH partition; and making the next DSH partition the active DSH partition, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 7 is dependent on claim 1 and includes all the limitations of claim 1. Therefore, claim 7 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of the BFS algorithm is executed as part of a top-k shortest path graph query, the hash table maps each visited vertex to a number of times that vertex has been reached, and executing the BFS algorithm further comprises updating the number of times the current vertex has been visited in the hash table, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 8 is dependent on claim 7 and includes all the limitations of claim 7. Therefore, claim 8 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of wherein executing the BFS algorithm further comprises: determining a given vertex has been visited k times based on a lookup of the given vertex in the hash table, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 9 is dependent on claim 8 and includes all the limitations of claim 8. Therefore, claim 9 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of wherein executing the BFS algorithm further comprises: in response to the given vertex having no entry in the hash table, inserting an entry for the given vertex in the hash table, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 10 is dependent on claim 8 and includes all the limitations of claim 8. Therefore, claim 10 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of wherein executing the BFS algorithm further comprises: in response to the given vertex having been visited k times, skipping the given vertex, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 11 is dependent on claim 7 and includes all the limitations of claim 7. Therefore, claim 11 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of wherein executing the BFS algorithm further comprises: determining whether a given neighbor vertex has been visited k times based on a lookup of the given neighbor vertex in the hash table; and in response to the given neighbor vertex having been visited k times, skipping the neighbor vertex, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 12 is dependent on claim 1 and includes all the limitations of claim 1. Therefore, claim 12 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of wherein the first DSQ is in read-only mode and the second DSQ is in write-only mode and wherein executing the BFS algorithm further comprises: in response to completing the current BFS level and initiating the next BFS level: changing the second DSQ to read-only mode; deleting data from the first DSQ; changing the first DSQ to write-only mode; and using the second DSQ to represent the current BFS level and the first DSQ to represent the next BFS level, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
Claim 13 is dependent on claim 1 and includes all the limitations of claim 1. Therefore, claim 13 recites the same abstract idea of solving shortest path queries under strict memory constraints. The claim recites the limitations of the BFS algorithm is executed as part of a graph query against a heterogeneous graph, vertices in the heterogeneous graph are represented by a plurality of vertex tables, the hash table is one of a plurality of hash tables, and each hash table within the plurality of hash tables is associated with a vertex table within the plurality of vertex tables, which can be done mentally with or without the use of a physical aid (e.g., pen and paper) or with a generic computer and is not an inventive concept that meaningfully limits the abstract idea. Therefore, the limitation is a mental process.
As to claims 14-20, they have similar limitations as of claims 1-13 above. Hence, they are rejected under the same rational as of claims 1-13 above.
Claim Rejections - 35 USC § 102
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 the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Yamane et al. (Pub. No. : US 20190251123 A1)
As to claim 1 Yamane teaches a method comprising:
executing a breadth first search (BFS) algorithm as part of a graph query to find one or more paths from a source vertex to a destination vertex (paragraphs [0030]-[0032], [0116]-[0119]: in S1001 of the breadth-first search algorithm illustrated in FIG. 9, an empty shortest path matrix S of n rows and n columns is prepared, and a variable j for specifying the end point of the column to be processed in a shortest path matrix S, for example, the end point of the shortest path to be determined), wherein: a hash table stores information for each visited vertex (paragraph [0107]: generates a vertex cluster correspondence table indicating which cluster each vertex belongs to, wherein an index attached table is a table that may enable direct access to the value using the index from the key, for example, a hash table or a binary tree on a main storage, or a B-tree or a hash table on a secondary storage), executing the BFS algorithm comprises:
reading a set of vertices representing a subpath from an entry in a first DSQ representing a current BFS level, wherein the subpath ends at a current vertex (paragraphs [0013], [0074]: in step S1 of the shortest path matrix generation process illustrated in FIG. 6, the assignment unit 12R determines the shortest path between each vertex (1, . . . , N) included in the input graph G. The assignment unit 12R assigns the intermediate edge number (n+1, n+2, . . . ) to each of the shortest paths. In step S2, the assignment unit 12R generates an intermediate path tables (P.sub.1[(k.sub.1, k.sub.2)]=x, and P.sub.2[x]=(k.sub.1, k.sub.2)) in which the intermediate edge (k.sub.1, k.sub.2) and the intermediate edge number (x) which is assigned to the intermediate edge are associated with each other and are stored. Note that each vertex interpreted as DSQ);
expanding the current vertex to one or more neighbor vertices (paragraph [0074]: generates an intermediate path tables);
storing information for the current vertex in the hash table (paragraph [0074]: generates an intermediate path tables (P.sub.1[(k.sub.1, k.sub.2)]=x, and P.sub.2[x]=(k.sub.1, k.sub.2)) in which the intermediate edge (k.sub.1, k.sub.2) and the intermediate edge number (x) which is assigned to the intermediate edge are associated with each other and are stored); and
for each neighbor vertex in the one or more neighbor vertices, storing a new subpath comprising the set of vertices and the neighbor vertex in a second DSQ representing a next BFS level (paragraph [0134]: In the breadth-first search algorithm, the list R[d] in which the vertex number i of the vertex located at a distance d from the vertex j is stored stores, as an element stored in the R[d], not only the vertex number i but also information m on the state of vertex i. For example, in the present embodiment, R[d] is a list of tuple(i, m). The information m on the state of the vertex i is information indicating the state of the vertex i in the process of finding the intermediate path on the shortest path from the vertex i to the vertex j),
wherein the method is performed by one or more computing devices (paragraph [0178]: The function of the information processing apparatus 100 may be implemented by, for example, a computer 40 illustrated in FIG. 12. The computer 40 includes a central processing unit (CPU) 41, a memory 42 as a temporary storage area, and a nonvolatile storage unit 43).
As to claim 2 Yamane teaches wherein: the hash table comprises a disk-spilling hash (DSH) table, the DSH table has a plurality of DSH partitions, each partition of the plurality of DSH partitions is associated with a DSQ representing a current BFS level and a DSQ representing a next BFS level, wherein last vertices of subpaths stored in a given DSQ belong to a same DSH partition (paragraphs [0030]-[0032], [0107], [0116]-[0119]).
As to claim 3 Yamane teaches the DSH table maps each visited vertex to the information for the visited vertex based on a first hash function, and the DSH table is partitioned based on a second hash function (paragraphs [0061]-[0063], [0107]).
As to claim 4 Yamane teaches wherein storing the new subpath comprising the set of vertices and the neighbor vertex in the second DSQ comprises determining a particular DSH partition associated with the neighbor vertex based on the second hash function, wherein the second DSQ is associated with the particular DSH partition (paragraph [0062]).
As to claim 5 Yamane teaches wherein: an active DSH partition and a hash table for the active DSH partition are stored in memory, and at least one partition of the plurality of DSH partitions is stored in external storage (paragraph [0063]).
As to claim 6 Yamane teaches wherein executing the BFS algorithm further comprises: in response to all sets of vertices being read from the active DSH partition: reading a next DSH partition into memory, building a hash table for the next DSH partition, and making the next DSH partition the active DSH partition (paragraph [0066]).
As to claim 7 Yamane teaches the BFS algorithm is executed as part of a top-k shortest path graph query, the hash table maps each visited vertex to a number of times that vertex has been reached, and executing the BFS algorithm further comprises updating the number of times the current vertex has been visited in the hash table (paragraph [0061]).
As to claim 8 Yamane teaches wherein executing the BFS algorithm further comprises: determining a given vertex has been visited k times based on a lookup of the given vertex in the hash table (paragraph [0234]).
As to claim 9 Yamane teaches wherein executing the BFS algorithm further comprises: in response to the given vertex having no entry in the hash table, inserting an entry for the given vertex in the hash table (paragraph [0117]).
As to claim 10 Yamane teaches wherein executing the BFS algorithm further comprises: in response to the given vertex having been visited k times, skipping the given vertex (paragraph [0134]).
As to claim 11 Yamane teaches wherein executing the BFS algorithm further comprises: determining whether a given neighbor vertex has been visited k times based on a lookup of the given neighbor vertex in the hash table; and in response to the given neighbor vertex having been visited k times, skipping the neighbor vertex (paragraph [0116]).
As to claim 12 Yamane teaches wherein the first DSQ is in read-only mode and the second DSQ is in write-only mode and wherein executing the BFS algorithm further comprises: in response to completing the current BFS level and initiating the next BFS level: changing the second DSQ to read-only mode; deleting data from the first DSQ; changing the first DSQ to write-only mode; and using the second DSQ to represent the current BFS level and the first DSQ to represent the next BFS level (paragraphs [0030]-[0032], [0107], [0116]-[0119]).
As to claim 13 Yamane teaches the BFS algorithm is executed as part of a graph query against a heterogeneous graph, vertices in the heterogeneous graph are represented by a plurality of vertex tables, the hash table is one of a plurality of hash tables, and each hash table within the plurality of hash tables is associated with a vertex table within the plurality of vertex tables (paragraphs [0107]-[0110]).
As to claims 14-20, they have similar limitations as of claims 1-13 above. Hence, they are rejected under the same rational as of claims 1-13 above.
Examiner's Note: Examiner has cited particular columns and line numbers or paragraphs in the references as applied to the claims above for the convenience of the applicant. Although the specified citations are representative of the teachings of the art and are applied to the specific limitations within the individual claim, other passages and figures may apply as well. It is respectfully requested from the applicant in preparing responses, to fully consider the references in its entirety as potentially teaching of all or part of the claimed invention, as well as the context.
Conclusion
The prior art made of record, listed on form PTO-892, and not relied upon, if any, is considered pertinent to applicant's disclosure.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MD I UDDIN whose telephone number is (571)270-3559. The examiner can normally be reached M-F, 8:00 am to 5:00 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, Sherief Badawi can be reached at 571-272-9782. 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.
/MD I UDDIN/Primary Examiner, Art Unit 2169
Prosecution Insights