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 .
Information Disclosure Statement
The Information Disclosure Statement filed on December 15, 2024 is considered.
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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1-4, 6-14 and 16-20 are rejected under 35 U.S.C. 103 as being unpatentable over Danilov et al. (US 2020/0334142 A1, hereinafter Danilov) in view of Brannigan et al. (US 2018/0342007 A1, hereinafter Brannigan).
Regarding claim 1, Danilov discloses a computing system (figure 1, 100) for performing workload-aware space reclamation ([0028], quasi-compacting garbage collector can verify the unused blocks to make sure their capacity can be safely reclaimed), the computing system comprising: processing circuitry (figure 1, 126) and memory (figure 1, 128) storing instructions that, during execution, causes the processing circuitry to: track extent usage characteristics for each of a plurality of extents storing data for a database ([0039], quasi-compacting garbage collector obtains a list of chunks that are in use and owned by the storage node such that information indicates which fragments of that chunk are in use and which are not in use); and perform memory reclamation to reclaim storage areas corresponding to invalid data (figure 6 and [0060], performing a union operation on the chunk identifiers in the datasets, and thereby knows which of the chunks that it owns are in use (block 668), and thus can subtract the chunks in use from the set of chunks that are owned to obtain a dataset of the chunks not in use, which are then deleted to reclaim their space), wherein performing the memory reclamation comprises: generating a list of extents to be reclaimed based on the tracked extent usage characteristics(figures 14-15 and [0076]-[0078], each node to produce a local list of chunks in use, as well as the fragments in use per chunk and combine each local list to produce a single list); and reclaiming memory space on the plurality of extents in order based on the list of extents ([0078], each owned chunk that is not in the combined list of used chunks and is ready for garbage collection can be deleted and the capacity occupied by deleted chunks can be reclaimed and reused). Danilov differs from the claimed invention in not specifically teaching to track extent usage characteristics for each of a plurality of extents storing data for a graph database. However, it is old and notoriously well known in the art of Graph database being run through one or more computational and/or analytics regimes to identify pertinent known or inferred data points from which various relationships between producers, consumers, and delivery agents engaged with the system, for example see Brannigan ([0125]). Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Danilov to track extent usage characteristics for each of a plurality of extents storing data for a graph database, as per teaching of Giles, in order to achieve better performance.
Regarding claim 2, Danilov teaches generating an initial list of extents; and sorting the initial list in an order of reclamation priority based on the tracked extent usage characteristics (figure 3 and [0044]-[0045], entries in the index 330 are sorted by the sizes of an unused block they contain, largest unused blocks first, as represented in the sorted index 334).
Regarding claim 3, Danilov teaches that the tracked extent usage characteristics comprise an update gradient describing a rate of fragmentation; and the initial list of extents is generated by selecting a subset of the plurality of extents that contains a smallest update gradient (figure 7 and [0062]-[0063], creating the index of available block space from unused fragment information, and updates the index so that the selected block(s) are no longer available).
Regarding claim 4, Danilov teaches that the tracked extent usage characteristics further comprise a fragmentation ratio describing a current state of fragmentation ; and the order of reclamation priority is based on the fragmentation ratios of the extents in the initial list of extents ([0073] and [0076], composited lists can be performed by sorting the chunk identifiers and removing duplicate identifiers and the B+ trees owned by that node to produce a local list of chunks in use, as well as the fragments in use per chunk).
Regarding claim 6, Danilov teaches that the tracked extent usage characteristics comprise time-to-live information for each of the plurality of extents, wherein the list of extents excludes extents containing time-to-live information below a predetermined threshold ([0058], the system traverses the B+ trees to produce a list of tree chunks in use, that is, those chunks that have at least one live tree element inside).
Regarding claim 7, Danilov teaches that the time-to-live information for a given extent is based on a time-to-live of a most recently updated piece of data in the given extent ([0058]-[0059], tree chunk that is in the list of known chunks but not in the list of used chunks contains no live data and the other nodes provide the owning node with a list of the chunks in use that it is using and are owned by the owning node at garbage collection time).
Regarding claim 8, Brannigan teaches that data from all various sources may be collected and organized in a structure that is specifically designed to pinpoint correlations, such as the graph database, which obvious comprises a Bw-tree graph database ([0125]) in order to achieve better performance.
Regarding claim 9, Danilov teaches that the plurality of extents comprises a first subset of extents storing base page data and a second subset of extents storing delta page data (figure 4A and [0047], data storage system has just one tree in this example, in which the tree has three elements, a Root, read as base page data, Leaf 1 and Leaf 2, read as delta page data).
Regarding claim 10, Brannigan teaches that Graph database may be run through one or more computational and/or analytics regimes, so as to identify pertinent known or inferred data points from which various relationships between producers, consumers, and delivery agents engaged with the system, which would be obvious to implement on a social media platform ([0125] and [0157]).
Regarding claim 11, the limitations of the claim are rejected as the same reasons as set forth in claim 1.
Regarding claim 12, the limitations of the claim are rejected as the same reasons as set forth in claim 2.
Regarding claim 13, the limitations of the claim are rejected as the same reasons as set forth in claim 3.
Regarding claim 14, the limitations of the claim are rejected as the same reasons as set forth in claim 4.
Regarding claim 16, the limitations of the claim are rejected as the same reasons as set forth in claim 6.
Regarding claim 17, the limitations of the claim are rejected as the same reasons as set forth in claim 7.
Regarding claim 18, the limitations of the claim are rejected as the same reasons as set forth in claim 8.
Regarding claim 19, the limitations of the claim are rejected as the same reasons as set forth in claim 9.
Regarding claim 20, the limitations of the claim are rejected as the same reasons as set forth in claims 1, 8 and 9.
Allowable Subject Matter
Claims 5 and 15 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.
The following is a statement of reasons for the indication of allowable subject matter: The prior art of record fails to teach nor suggest “wherein the tracked extent usage characteristics comprise: an update gradient describing a rate of fragmentation; and a fragmentation ratio describing a current state of fragmentation, wherein the list of extents to be reclaimed is generated further based on a ranking of a formulaic combination of the update gradients and the fragmentation ratios of the plurality of extents” as recited in claims 5 and 15.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Mitsuma et al. (US 2020/0042607 A1) discloses a computer-implemented method for performing a storage reclaim on a storage device including the steps of generating an extent list in the index partition of the second tape image, adjusting the file offset for a record stored in an extent list generated in a second index partition of the second tape image, and removing metadata and file data (figure 5 and [0061]-[0080]).
Fang et al. (US 2019/0205265 A1) discloses a method for processing a memory and apparatus comprising the steps of acquiring reclaimable memory pages occupied by an application to be processed; acquiring an idle duration of the application to be processed for each reclaimable memory page; determining a duration threshold according to the idle durations for the reclaimable memory pages; and selecting from the reclaimable memory pages a memory page for which the idle duration exceeds the duration threshold and reclaiming the memory page (abstract).
Pendharkar et al. (US 8,775,751 B1) discloses a method for reclaiming physical memory blocks within tier-1 storage device so that the storage use efficiency can be driven higher with small administrative overhead (abstract and figures 4-5).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ZHUO H LI whose telephone number is (571)272-4183. The examiner can normally be reached Mon. Tue. and Thurs. 8:00-4: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, Rocio Del Mar Perez-Velez can be reached at (571)-270-5935. 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.
/ZHUO H LI/Primary Examiner, Art Unit 2133