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 .
This is a non-final Office Action in response to the present US application number 18/928706, filed on 10/28/2024, with an amendment filed on 12/11/2025.
Claims 1, 3-8, 10-15, and 17-20 are presented for examination, with claims 1, 8 and 15 being independent.
Response to Arguments
Applicant’s arguments with respect to the 35 USC 101 rejection have been fully considered and are persuasive. The 35 USC 101 rejection has been withdrawn.
The double patenting rejection is withdrawn in view of applicant’s amendments to the claims.
Applicant's arguments with respect to the 35 USC 103 rejections have been fully considered but they are not persuasive.
Applicant argues at pp.15-16 of applicant’s remarks that Li does not teach “determining whether an increase of the size is to be executed on a container list, wherein the container list comprises one or more pointers corresponding to the one or more data structures.” Specifically, applicant argues that Li appears to describe determining an available memory of a data structure such as a lock free vector, not a container list of pointers to data structures.
Examiner respectfully disagrees. Li teaches a lock-free vector data structure that constitutes a container list, with each element being a pointer to a data structure (Li; pars [0021], [0025]-[0026], [0028]). Li describes determining whether the vector (i.e., the container list) needs to grow and, when growth is required, Li’s method creates a new, larger container list and copies the pointers to the data structures into this new list (Li; par [0028]). Therefore,, Li discloses both a container list comprising pointers to data structures and determining whether to increase its size. This is consistent with standard implementations of vectors of pointers. Therefore, Applicant’s argument is not persuasive.
Applicant argues at p.16 of applicant’s remarks that Li does not disclose “storing the pointer to the another data structure in the second portion of the memory and storing the another data structure in a third portion of the memory.” Specifically, applicant argues that Li only teaches storing new data in a new memory and returning a pointer to it, not storing a pointer in one memory location and the data structure in another.
Examiner respectfully disagrees. Li describes that when the vector grows, a new memory block (second portion) is allocated for the expanded container list, and the pointers to the data structures are copied into this new memory (Li; par [0028]). The data structures themselves may reside in separate memory locations (third portion), as is standard for vectors of pointers. Therefore, the pointer is stored in the new container list (second portion), while the referenced data structure remains in its original or a newly allocated location (third portion). This meets the claim language as presently written.
Examiner Note
With respect to claim 1, it is noted that “based on the determination that an increase of the size is to be executed, inserting the second data to another data structure” is a contingent limitation and that “the broadest reasonable interpretation of a method (or process) claim having contingent limitations requires only those steps that must be performed and does not include steps that are not required to be performed because the condition(s) precedent are not met.” Please see MPEP 2111.04 II. It is suggested that the previous limitation of the claim be amended to recite, “determining that an increase of the size is to be executed on a container list” instead of “determining whether an increase of the size is to be executed on a container list.” Claim 7 has similar contingent limitation issues in the last 2 limitations of the claim.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 7, 14, and 20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 7 recites, “determining a delete operation associated with the first portion of the memory; in response to the delete operation…” However, a delete operation is not performed in the previous limitation; rather it is just determined. So, the language, “in response to the delete operation…” is ambiguous and it is unclear if the claim should recite, “in response to determining the delete operation…” The current language makes it sound as though it is in response to performing the delete operation, but that does not seem to be the case.
Claim 7 also recites, “in response to determining whether the time is less than … generating a trigger…” However, it is unclear in light of paragraphs [0106]-[0107] of the specification if this should recite “in response to determining that the time is less than … generating a trigger…” Claim 14 contains similar issues.
Claim 20 recites the limitation “the database system." There is insufficient antecedent basis for this limitation in the claim.
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.
Claims 1, 3, 5-8, 10, 12-15, 17, 19 and 20 are rejected under 35 U.S.C. 103 as being unpatentable Li et al., US 2009/0287899 (hereinafter Li), and further in view of Bensberg et al., US 2018/0276122 (hereinafter Bensberg).
Regarding claim 1, Li disclose, A computer-implemented method for providing a lock-free read access to one or more data structures in a database system, the computer-implemented method comprising:
allocating, by one or more processors, a first portion of a memory corresponding to a first data structure of the one or more data structures, wherein the first data structure comprises a size (e.g. allocate a first portion of memory of the lock-free vector [is a data structure] exclusively to the requesting thread. Lock-free vector 104 includes a number of indicators and variables 110a-110d, such as a total size 110a of the vector 104, a count/portion 110b of the vector 104 currently being used/allocated, a counter 110c of pending write requests, and/or a flag 110d indicating whether vector 104 is growing. In other embodiments, fewer, different, or additional indicators and variables may be utilized, Li: [0012], [0016], [0020]-[0021], Fig. 1); and
performing a first operation associated with the first data structure (e.g. vector 104 may have at least three methods 106a-106c: a push_back or write method 106a, a read method 106b, and a grow method 106c, Li: [0022]) comprising:
inserting first data to the first data structure (e.g. a request from a thread of the computing device to write data to the lock-free vector. In various embodiments, the lock-free vector may then determine whether the lock-free vector is growing and, if the lock-free vector is not growing, may allocate a first portion of memory of the lock-free vector exclusively to the requesting thread [as inserting/storing first data to data structure], Li: [0012]);
storing the first data in the first portion of the memory (e.g. allocate a first portion of memory of the lock-free vector exclusively to the requesting thread [as inserting/storing first data to data structure], Li: [0012]);
receiving a first request to insert second data (e.g. receiving a write request, Li: [0025]);
in response to the receiving the first request, determining whether an increase of the size is to be executed on a container list, wherein the container list comprises one or more pointers corresponding to the one or more data structures (e.g. Upon receiving a write request [as first request], the push_back method 106a of vector 104 may first increment a pending-requests-counter variable 110c to indicate that an additional request is pending. Push_back method 106a may then determine whether vector 104 [as container list] is growing. If the flag indicator 110d indicates that vector 104 is not growing, push_back method 106a may then compare the size 110a of the vector 104 to the portion used 110b. If size 110a is greater than portion 110b, push_back method 106a may invoke resource allocator 108 to allocate an element or portion of memory 112 exclusively to the requesting thread 102 , Li: [0025]-[0026]);
based on the determination that an increase of the size is to be executed, inserting the second data to another data structure (e.g. the grow method 106c of lock-free vector 104 may first reserve a new portion of memory [as another data structure] of computing device 100. In one embodiment, the amount of memory reserved may be twice the size of memory 112. For example, if memory 112 was 256 kilobytes, grow method 106c may reserve 512 kilobytes as the new memory 112. In some embodiments, grow method 106c may then reset the size 110a of vector 104. For example, if the previous size of vector 104 was one hundred elements and the grow method 106c has doubled the memory 112, grow method 106c may reset the size 110a to two hundred elements, Li: [0028]), comprising:
executing the increase of the size of the container list to generate a modified container list (e.g. In some embodiments, grow method 106c may then reset the size 110a of vector 104 [as container list]. For example, if the previous size of vector 104 was one hundred elements and the grow method 106c has doubled the memory 112, grow method 106c may reset the size 110a to two hundred elements, Li: [0028]), wherein the modified container list comprises a pointer to the another data structure (e.g. if the data to be written was provided by the thread 102 as a parameter, the push_back method 106a or resource allocator 108 may write the data to the memory 112 allocated by resource allocator 108 and push_back method 106a may return an index or pointer to the element/memory 112 to the thread 102. If the data to be written was not provided, the push_back method 106a may simply return an index or pointer to the allocated element/memory 112 to the thread 102, enabling the thread to write to the allocated element/memory 112 using the index/pointer, Li: [0026]);
allocating a second portion of the memory corresponding to the modified container list, wherein the second portion of the memory is different from the first portion of the memory (e.g. the grow method 106c of lock-free vector 104 may first reserve a new portion of memory [as second portion of the memory] of computing device 100. In one embodiment, the amount of memory reserved may be twice the size of memory 112. For example, if memory 112 was 256 kilobytes, grow method 106c may reserve 512 kilobytes as the new memory 112, Li: [0028]);
duplicating the one or more pointers of the container list from the first portion of the memory to the second portion of the memory (e.g. Upon reserving new memory 112, grow method 106c may copy contents [as duplicating] of vector 104, such as the buffer/element values stored in the previous memory 112, to the new memory 112, Li: [0028]);
storing the pointer to the another data structure in the second portion of the memory and storing the another data structure in a third portion of the memory (e.g. Upon reserving new memory 112, grow method 106c may copy contents [as duplicating] of vector 104, such as the buffer/element values stored in the previous memory 112, to the new memory 112, Li: [0028]); and
Li does not directly or explicitly disclose:
executing garbage collection to free-up the first portion of the memory based on at least one parallel operation associated with the first data structure.
Bensberg teaches:
executing garbage collection to free-up the first portion of the memory based on at least one parallel operation associated with the first data structure (e.g. the present disclosure are generally directed to asynchronous garbage collection in parallel transaction systems. In general, garbage collection can be described as automatic memory management, in which a computer-implemented memory manager (also referred to as a garbage collector) reclaims memory occupied by data that is no longer in use by a system, such as a database system, Bensberg: [0015]).
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the invention to modify lock-free vector method as disclosed by Li to include asynchronous garbage collection in parallel transaction systems as taught by Bensberg to maintaining pendency of a clean-up entry until any parallel transaction are executed.
Regarding claim 3, Bensberg further teaches:
generating a first container comprising a first pre-generated iterator and the container list (e.g. the transaction data 204 can indicate a transaction associated with data stored in one or more tables 210 [as container lists] of a column/row store 211 [as a first container], and the transaction manager is informed of execution of the transaction on the tables 210, Bensberg: [0024], fig. 2) ; and
generating a second container comprising a second pre-generated iterator and the modified container list (e.g. document store 208 [as second container]. Example transactions can include modifying documents within [as modified container list], adding documents to, and deleting documents from the document store 208. In the depicted example, the document store 208 includes a document store (DS) transaction manager 212, and a clean-up manager 214. In some examples, the DS transaction manager 212 coordinates transactions to be executed within the document store 208, Bensberg: [0024], fig. 2).
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the invention to modify lock-free vector method as disclosed by Li to include asynchronous garbage collection in parallel transaction systems as taught by Bensberg to maintaining pendency of a clean-up entry until any parallel transaction are executed.
Regarding claim 5, Bensberg further teaches: generating a first container comprising a pre-generated accessor (e.g. the client device 102 can interact with the database system to access data stored therein. For example, the client device 102 can interact with the database system to read data from, delete data from, add data to, and/or modify data within one or more tables [as pre-generated accessor], Bensberg: [0021], fig. 2).
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the invention to modify lock-free vector method as disclosed by Li to include asynchronous garbage collection in parallel transaction systems as taught by Bensberg to maintaining pendency of a clean-up entry until any parallel transaction are executed.
Regarding claim 6, Bensberg further teaches, wherein the database system comprises a transaction manager and a clean-up manager (e.g. Transaction Manager 206/212 and Clean-up Manager 214, Bensberg: fig. 2).
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the invention to modify lock-free vector method as disclosed by Li to include asynchronous garbage collection in parallel transaction systems as taught by Bensberg to maintaining pendency of a clean-up entry until any parallel transaction are executed.
Regarding claim 7, Bensberg further teaches, wherein the executing garbage collection to free-up the first portion of the memory based on the at least one parallel operation comprises:
determining a delete operation associated with the first portion of the memory (e.g. determining that a transaction of a plurality of transactions performed in at least a portion of a system includes a delete operation, Bensberg: [0016],[0029],[0045]);
in response to the delete operation, inserting a clean-up entry in the transaction manager, the transaction manager delegating the clean-up entry to the clean-up manager (e.g. in response to the delete operation, inserting a clean-up entry in the secondary transaction manager, Bensberg: [0016],[0031],[0046]-[0047]);
attaching the clean-up entry to a subsequent transaction in order to determine and to assign a time to the clean-up entry that is used to subsequently trigger garbage collection, wherein the time is associated with the at least one parallel operation (e.g. attaching the clean-up entry to a subsequent transaction in order to determine and assign a time to the cleanup-entry that is used to subsequently trigger garbage collection, Bensberg: [0016],[0031],[0037],[0047]);
comparing the time to a most-recent minimum read timestamp, wherein minimum read timestamps are associated with start times of a plurality of transactions and wherein a pendency of the clean-up entry is maintained until the at least one parallel transaction is executed (Bensberg: [0016],[0031],[0039],[0047]);
determining whether the time is less than the most-recent minimum read timestamp (Bensberg: [0039],[0047]); and
in response to determining whether the time is less than the most-recent minimum read timestamp, generating a trigger to execute the clean-up entry to free-up the first portion of the memory (Bensberg: [0039],[0047]).
Claims 8, 10, 12, 13, and 14 recite A computing system comprising steps are similar to subject matter of claims 1, 3, 5, 6, and 7. Therefore, claims 8, 10, 12, 13, and 14 are rejected by the same reasons as in claims 1, 3, 5, 6, and 7.
Claims 15, 17, 19 and 20 recite A non-transitory computer-readable medium comprising steps are similar to subject matter of claims 1, 3, 5 and 6. Therefore, claims 15, 17, 19 and 20 are rejected by the same reasons as in claims 1, 3, 5 and 6.
Claims 4, 11 and 18 are rejected under 35 U.S.C. 103 as being unpatentable Li, in view of Bensberg, and further in view of Wang et al., US 2022/0382674 (hereinafter Wang).
Li in view of Bensberg does not directly or explicitly disclose limitation in claim 4:
wherein the first data structure is a tree data structure.
Wang teaches:
wherein the first data structure is a tree data structure (e.g. index structure, such as a tree structure, Wang: [0002], fig. 3).
Therefore, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the invention to modify lock-free vector method as disclosed by Li in view of Bensberg to include garbage collection of tree structure as taught by Wang to provide related storage function.
Claims 11 and 18 are similar to claim 4. Therefore, they are rejected by the same reason as claim 4.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Kavita Stanley whose telephone number is (571)272-8352. The examiner can normally be reached M-F 9:30am-6pm.
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, Cordelia (Dede) Zecher can be reached at 571-272-7771. 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.
/KAVITA STANLEY/Supervisory Patent Examiner, Art Unit 2153
Prosecution Insights