DETAILED ACTION
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 .
In response to Applicant’s claims filed on July 21, 2024, claims 1, 3-16 are now pending for examination in the application.
“The 112 rejection under 35 USC 112 set forth in the 07/21/2025 office action is hereby withdrawn.”
Response to Arguments
This office action is in response to amendment filed 07/21/2025. In this action claim(s) 1, 3-16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Papamanthou et al. (US Pub. No. 20110225429) and Patiejunas et al. (US Pub. No. 20140046909) in further view of Ramsey et al. (US Pub. No. 20210064366). The Ramsey et al. reference has been added to address the amendment of different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements such that the hierarchical accumulator structure comprises a heterogeneous set of different types of second level accumulators.
Claim Rejections - 35 USC § 103
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.
Claim(s) 1, 3-16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Papamanthou et al. (US Pub. No. 20110225429) and Patiejunas et al. (US Pub. No. 20140046909) in further view of Ramsey et al. (US Pub. No. 20210064366).
With respect to claim 1, Papamanthou et al. discloses a computer-implemented method for storing data, the method comprising
storing the data in a hierarchical accumulator structure (Paragraph 20 discloses generating a hash tree or other hierarchical data structure), the hierarchical accumulator structure comprising at least a first level and a second level, wherein the first level comprises a first level accumulator and the second level comprises a plurality of second level accumulators (Paragraph 6 discloses maintaining an accumulation tree corresponding to the stored data, where the accumulation tree comprises an ordered tree structure having a root node, at least one leaf node and at least one internal node disposed between the root node and the at least one leaf node);
the first level accumulator encompasses a plurality of first level elements and a first level digest of the plurality of first level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest);
each of the plurality of second level accumulators encompasses a plurality of second level elements and a second level digest of the plurality of second level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest);
each of the second level digests of the plurality of second level accumulators corresponds to one of the plurality of first level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest); and
wherein storing the data comprises computing the plurality of second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements (Page 433 discloses the accumulation tree is generated or maintained in conjunction with an authenticated hash table having O(n) buckets, each bucket containing O(1) elements of the stored data, where the accumulation tree is constructed over the buckets). Papamanthou et al does not explicitly disclose a subset of the plurality of first level elements comprises metadata, the metadata comprising accumulator information for the corresponding second level accumulator.
However, Patiejunas et al. teaches a subset of the plurality of first level elements comprises metadata, the metadata comprising accumulator information for the corresponding second level accumulator (Paragraph 141 discloses portions of the data and/or metadata of the archival data storage service).
Therefore, it would have been obvious before the effective filing data of invention was made to a person having ordinary skill in the art to modify Papamanthou et al and Patiejunas et al. This would have facilitated improved access of computational results. See Patiejunas et al. Paragraph 2.
Papamanthou et al as modified by Patiejunas et al. does not disclose computing different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements such that the hierarchical accumulator structure comprises a heterogeneous set of different types of second level accumulators.
However, Ramsey et al. teaches computing different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements such that the hierarchical accumulator structure comprises a heterogeneous set of different types of second level accumulators (Paragraph 15 discloses accumulators can be implemented at different levels in the processing hierarchy of the GPU 115).
Therefore, it would have been obvious before the effective filing data of invention was made to a person having ordinary skill in the art to modify Papamanthou et al and Patiejunas et al. with Ramsey et al. This would have facilitated improved access of computational results. See Ramsey et al. Paragraph 1.
With respect to claim 15, Papamanthou et al discloses a computing system comprising:
a processing unit (See Fig. 4) comprising one or more hardware processors; and
a storage unit (See Fig. 4) comprising one or more storage devices,
wherein the processing unit stores data in a hierarchical accumulator structure in store the data in a hierarchical accumulator structure (Paragraph 20 discloses generating a hash tree or other hierarchical data structure), the hierarchical accumulator structure comprising at least a first level and a second level, wherein the first level comprises a first level accumulator and the second level comprises a plurality of second level accumulators (Paragraph 6 discloses maintaining an accumulation tree corresponding to the stored data, where the accumulation tree comprises an ordered tree structure having a root node, at least one leaf node and at least one internal node disposed between the root node and the at least one leaf node);
the first level accumulator encompasses a plurality of first level elements and a first level digest of the plurality of first level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest);
each of the plurality of second level accumulators encompasses a plurality of second level elements and a second level digest of the plurality of second level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest);
each of the second level digests of the plurality of second level accumulators corresponds to one of the plurality of first level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest); and
wherein storing the data comprises computing the plurality of second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements (Page 433 discloses the accumulation tree is generated or maintained in conjunction with an authenticated hash table having O(n) buckets, each bucket containing O(1) elements of the stored data, where the accumulation tree is constructed over the buckets). Papamanthou et al does not explicitly disclose a subset of the plurality of first level elements comprises metadata, the metadata comprising accumulator information for the corresponding second level accumulator.
However, Patiejunas et al. teaches a subset of the plurality of first level elements comprises metadata, the metadata comprising accumulator information for the corresponding second level accumulator (Paragraph 141 discloses portions of the data and/or metadata of the archival data storage service).
Therefore, it would have been obvious before the effective filing data of invention was made to a person having ordinary skill in the art to modify Papamanthou et al and Patiejunas et al. This would have facilitated improved access of computational results. See Patiejunas et al. Paragraph 2.
Papamanthou et al as modified by Patiejunas et al. does not disclose computing different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements such that the hierarchical accumulator structure comprises a heterogeneous set of different types of second level accumulators.
However, Ramsey et al. teaches computing different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements such that the hierarchical accumulator structure comprises a heterogeneous set of different types of second level accumulators (Paragraph 15 discloses accumulators can be implemented at different levels in the processing hierarchy of the GPU 115).
Therefore, it would have been obvious before the effective filing data of invention was made to a person having ordinary skill in the art to modify Papamanthou et al and Patiejunas et al. with Ramsey et al. This would have facilitated improved access of computational results. See Ramsey et al. Paragraph 1.
With respect to claim 16, Papamanthou et al discloses a computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by the computing system to cause the computing system to perform a method for storing data, the method comprising
storing the data in a hierarchical accumulator structure (Paragraph 20 discloses generating a hash tree or other hierarchical data structure), the hierarchical accumulator structure comprising at least a first level and a second level, wherein the first level comprises a first level accumulator and the second level comprises a plurality of second level accumulators (Paragraph 6 discloses maintaining an accumulation tree corresponding to the stored data, where the accumulation tree comprises an ordered tree structure having a root node, at least one leaf node and at least one internal node disposed between the root node and the at least one leaf node);
the first level accumulator encompasses a plurality of first level elements and a first level digest of the plurality of first level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest);
each of the plurality of second level accumulators encompasses a plurality of second level elements and a second level digest of the plurality of second level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest);
each of the second level digests of the plurality of second level accumulators corresponds to one of the plurality of first level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest); and
wherein storing the data comprises computing the plurality of second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements (Page 433 discloses the accumulation tree is generated or maintained in conjunction with an authenticated hash table having O(n) buckets, each bucket containing O(1) elements of the stored data, where the accumulation tree is constructed over the buckets). Papamanthou et al does not explicitly disclose a subset of the plurality of first level elements comprises metadata, the metadata comprising accumulator information for the corresponding second level accumulator.
However, Patiejunas et al. teaches a subset of the plurality of first level elements comprises metadata, the metadata comprising accumulator information for the corresponding second level accumulator (Paragraph 141 discloses portions of the data and/or metadata of the archival data storage service).
Therefore, it would have been obvious before the effective filing data of invention was made to a person having ordinary skill in the art to modify Papamanthou et al and Patiejunas et al. This would have facilitated improved access of computational results. See Patiejunas et al. Paragraph 2.
Papamanthou et al as modified by Patiejunas et al. does not disclose computing different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements such that the hierarchical accumulator structure comprises a heterogeneous set of different types of second level accumulators.
However, Ramsey et al. teaches computing different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements such that the hierarchical accumulator structure comprises a heterogeneous set of different types of second level accumulators (Paragraph 15 discloses accumulators can be implemented at different levels in the processing hierarchy of the GPU 115).
Therefore, it would have been obvious before the effective filing data of invention was made to a person having ordinary skill in the art to modify Papamanthou et al and Patiejunas et al. with Ramsey et al. This would have facilitated improved access of computational results. See Ramsey et al. Paragraph 1.
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 2, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein storing the data comprises computing different accumulator types of the second level accumulators in dependence on the respective accumulator information of the metadata of the first level elements (Paragraph 446 discloses employing an accumulator over the accumulation values of the nodes lying one level below the node for which the accumulation value is determined).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 3, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein the hierarchical accumulator structure further comprises a third level comprising a plurality of third level accumulators (See Fig. 2);
wherein each of the plurality of third level accumulators encompasses a plurality of third level elements and a third level digest of the plurality of third level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest);
each of the third level digests of the plurality of third level accumulators corresponds to one of the plurality of second level elements (Paragraph 197 discloses The update authentication information contains all the RSA digests along the path of the update, the respective new prime representatives and a constant size signature of the root RSA digest); and
a subset of the plurality of second level elements comprises metadata, the metadata comprising accumulator information for the corresponding third level accumulator (Page 433 discloses the accumulation tree is generated or maintained in conjunction with an authenticated hash table having O(n) buckets, each bucket containing O(1) elements of the stored data, where the accumulation tree is constructed over the buckets).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 4, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein the accumulator information of the metadata comprises information of the data type of the corresponding second level and/or third level accumulators (Paragraph 339 discloses accumulator scheme will use type A pairings).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 5, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein the accumulator information defines an accumulator type for the corresponding second level and/or third level accumulators (Paragraph 21 discloses In the main result discussed herein, it is shown how to use two different accumulator schemes (e.g., [11, 34]) in a hierarchical way over the set and the underlying hash table, to securely authenticate both membership and non-membership queries and fully achieve the complexity goals).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 6, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein the accumulator information comprises information of write and/or read access patterns of the corresponding accumulator (Paragraph 25 discloses different data-access patterns).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 7, Papamanthou et al. teaches a computer-implemented method according to claim 2, wherein the method comprises selecting the respective accumulator type such that one or more predefined operations on the data of the corresponding accumulator can be performed in an efficient manner (Paragraph 26 discloses Efficient and secure protocols are provided for optimally authenticating (non-) membership queries on hash tables, using cryptographic accumulators as the basic security primitive and applying them in a novel hierarchical way over the stored data).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 8, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein storing the data comprises computing the first level accumulator and/or one or more of the plurality of second level accumulators and/or one or more of the plurality of third level accumulators as cryptographic accumulators (Paragraph 26 discloses cryptographic accumulators as the basic security primitive and applying them in a novel hierarchical way over the stored data).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 9, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein storing the data comprises computing the first level accumulator and/or one or more of the plurality of second level accumulators and/or one or more of the plurality of third level accumulators as hash trees (Paragraph 409 discloses A root node (e.g., located at the top or root of the hash tree or at the top left or root of the skip list) leads to one or more internal nodes and/or zero or more lead nodes).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 9. With respect to claim 10, Papamanthou et al. teaches a computer-implemented method according to claim 9, wherein computing the first level accumulator and/or one or more of the plurality of second level accumulators and/or one or more of the plurality of third level accumulators comprises computing a hash tree representing the data as a tree from the group consisting of a balanced tree; a red-black tree; a Patricia trie; and a hash chain (Paragraph 409 discloses A root node (e.g., located at the top or root of the hash tree or at the top left or root of the skip list) leads to one or more internal nodes and/or zero or more lead nodes).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 8. With respect to claim 11, Papamanthou et al. teaches a computer-implemented method according to claim 8, wherein storing the data comprises computing the plurality of second level accumulators and/or the plurality of third level accumulators in such a way that an average witness size of witnesses for the accumulator elements of the second level accumulators and/or the plurality of third level accumulators is minimized (Paragraph 39 discloses individual precomputed witnesses can each be updated in constant time, thus incurring a linear total cost for updating all the witnesses after an update in the set).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 12, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein storing the data comprises regularly analysing write accesses and/or read accesses to the hierarchical accumulator structure (Paragraph 25 discloses different data-access patterns); and
the method further comprises adapting the metadata of the plurality of first level elements and/or one or more of the plurality of second level elements and/or one or more of the plurality of third level elements in dependence on the analysis of the write accesses and/or the read accesses (Paragraph 25 discloses different data-access patterns).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 13, Papamanthou et al. teaches a computer-implemented method according to claim 1, wherein computing the first level accumulator and/or one or more of the plurality of second level accumulators and/or one or more of the plurality of third level accumulators comprises regularly computing a sequence of payloads (Paragraph 322 discloses the communication complexity of the exemplary schemes is analyzed by computing the exact sizes of the verification proofs and the update authentication information. Finally, the computational and communication analysis are experimentally validated);
regularly storing computational results of the sequence of payloads in the hierarchical accumulator structure (Paragraph 322 discloses the communication complexity of the exemplary schemes is analyzed by computing the exact sizes of the verification proofs and the update authentication information. Finally, the computational and communication analysis are experimentally validated);
regularly analysing the computational results (Paragraph 322 discloses the communication complexity of the exemplary schemes is analyzed by computing the exact sizes of the verification proofs and the update authentication information. Finally, the computational and communication analysis are experimentally validated); and
regularly adapting the metadata of the plurality of first level elements and/or the plurality of second level elements the plurality of third level elements in dependence on the analysis of the computational results (Paragraph 322 discloses the communication complexity of the exemplary schemes is analyzed by computing the exact sizes of the verification proofs and the update authentication information. Finally, the computational and communication analysis are experimentally validated).
The Papamanthou et al. reference as modified by Patiejunas et al. and Ramsey et al. teaches all the limitations of claim 1. With respect to claim 14, Papamanthou et al. teaches a computer-implemented method according to claim 1, further comprising
receiving a request for a computational result (Paragraph 333 discloses comparing the result (from which one also cuts the last 256 0's) with the SHA-256 digest of .beta..sub.i-1.sup..alpha..sup.i-1 mod N);
computing a witness for the computational result (Paragraph 332 discloses During an update the server has to compute the witnesses explicitly and, therefore, perform .di-elect cons..sup.-1n.sup..di-elect cons. log n.sup..di-elect cons. exponentiations and .di-elect cons..sup.-1f() computations in total);
providing the witness, the computational result and the digest of the first level accumulator as response to the request (Paragraph 333 discloses comparing the result (from which one also cuts the last 256 0's) with the SHA-256 digest of .beta..sub.i-1.sup..alpha..sup.i-1 mod N).
Relevant Prior Art
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
US PG-Pub. No. 20220092113 is directed Multi-Level Data Structure Comparison Using Commutative Digesting For Unordered Data Collections: [0006] an exemplary method comprises obtaining at least two multi-level data structures, wherein at least one of the multi-level data structures comprises an unordered data collection; determining a data structure digest value for each of the at least two multi-level data structures by accumulating a data element digest value for each data element of the respective multi-level data structure, wherein a data element digest value for a given data element comprising an unordered data collection is determined using a commutative accumulator function; and evaluating a similarity of the at least two multi-level data structures by comparing the respective data structure digest values.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). 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 NICHOLAS E ALLEN whose telephone number is (571)270-3562. The examiner can normally be reached Monday through Thursday 830-630.
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.
/N.E.A/Examiner, Art Unit 2154
/BORIS GORNEY/Supervisory Patent Examiner, Art Unit 2154