ANSWERNotice 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
Claims 1-20 are present in this application. Claims 1-20 are pending in this office
action.
This office action is NON-FINAL.
Drawings
The Drawings filed on 12/05/24 are acceptable for examination purposes.
Specification
5, The Specification filed on 12/05/24 is acceptable for examination purposes.
Information Disclosure Statement
The information disclosure statements (IDS) filed on 01/10/25 has been considered by the Examiner and made of record in the application file.
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.
Claim 1 recites, “determining a target bucket page corresponding to a target key in at least one bucket page by performing a hash operation on the target key of a read operation; determining whether a target address corresponding to the target key exists in a plurality of records included in the target bucket page; and in response to a determination that the target address exists in the plurality of records, returning a target value from a corresponding target entry page based on the target address”.
The limitation of “determining a target bucket page corresponding to a target key in at least one bucket page by performing a hash operation on the target key of a read operation; determining whether a target address corresponding to the target key exists in a plurality of records included in the target bucket page; and in response to a determination that the target address exists in the plurality of records, returning a target value from a corresponding target entry page based on the target address”. Nothing in the claim element precludes the step from practically being performed in the mind. Accordingly, the claim recites an abstract idea. The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. 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. Claim
2 recites wherein returning the target value from the target entry page comprises: requesting an exclusive lock for the target bucket page and the target entry page based on the read operation; and generating the target value by aggregating increment values corresponding to the target key from a cache to a disk in claim 2. But requesting an exclusive lock for the target bucket page and the target entry page based on the read operation; and generating the target value by aggregating increment values corresponding to the target key from a cache to a disk does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 3 is dependent on claim 1 and includes all the limitations of claim 1. Claim
3 recites requesting a shared lock for the target bucket page and the target entry page based on a write operation associated with the target key; and storing the increment values corresponding to the target key in the cache separately, and aggregating the increment values stored in the cache in response to being requested in claim 3. But requesting a shared lock for the target bucket page and the target entry page based on a write operation associated with the target key; and storing the increment values corresponding to the target key in the cache separately, and aggregating the increment values stored in the cache in response to being requested does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 4 is dependent on claim 1 and includes all the limitations of claim 1. Claim
4 recites wherein the plurality of records are arranged linearly, and the last record in the plurality of records comprises a record count for the plurality of records and a root page address of a balanced tree to indicate the balanced tree in claim 4. But the plurality of records are arranged linearly, and the last record in the plurality of records comprises a record count for the plurality of records and a root page address of a balanced tree to indicate the balanced tree does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 5 is dependent on claim 4 and includes all the limitations of claim 4. Claim
5 recites in response to a determination that the target address does not exist in the plurality of records, identifying the balanced tree based on the root page address; determining a target index page corresponding to the target key in at least one index page in the balanced tree; and navigating to a corresponding target data page based on a target index in the target index page in claim 5. But in response to a determination that the target address does not exist in the plurality of records, identifying the balanced tree based on the root page address; determining a target index page corresponding to the target key in at least one index page in the balanced tree; and navigating to a corresponding target data page based on a target index in the target index page does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 6 is dependent on claim 1 and includes all the limitations of claim 1. Claim
6 recites requesting an exclusive lock for the target bucket page; determining whether an empty record that has not been used exists in the plurality of records; and in response to a determination that the empty record exists in the plurality of records, requesting an exclusive lock for an entry page corresponding to the empty record for creating a new entry in claim 6. But requesting an exclusive lock for the target bucket page; determining whether an empty record that has not been used exists in the plurality of records; and in response to a determination that the empty record exists in the plurality of records, requesting an exclusive lock for an entry page corresponding to the empty record for creating a new entry does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 7 is dependent on claim 1 and includes all the limitations of claim 1. Claim
7 recites requesting an exclusive lock for the target bucket page; determining whether a record that has been used and contains the target key exists in the plurality of records; in response to a determination that the record exists in the plurality of records, determining whether the last record in the plurality of records has been used; in response to a determination that the last record has not been used, releasing the record for removal of entries, wherein an entry page corresponding to the record is retained in claim 7. But requesting an exclusive lock for the target bucket page; determining whether a record that has been used and contains the target key exists in the plurality of records; in response to a determination that the record exists in the plurality of records, determining whether the last record in the plurality of records has been used; in response to a determination that the last record has not been used, releasing the record for removal of entries, wherein an entry page corresponding to the record is retained does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 8 is dependent on claim 7 and includes all the limitations of claim 7. Claim
8 recites in response to a determination that the last record has been used, identifying the balanced tree based on the root page address of the balanced tree included in the last record; and requesting an exclusive lock for a root page of the balanced tree; and populating an index and data of the first entry in the balanced tree to the record and the entry page corresponding to the record in claim 8. But in response to a determination that the last record has been used, identifying the balanced tree based on the root page address of the balanced tree included in the last record; and requesting an exclusive lock for a root page of the balanced tree; and populating an index and data of the first entry in the balanced tree to the record and the entry page corresponding to the record does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 9 is dependent on claim 1 and includes all the limitations of claim 1. Claim
9 recites wherein the plurality of keys comprise a plurality of volume identifiers, each of the plurality of volume identifiers corresponding to a storage status of a corresponding volume; and a size of the at least one bucket page corresponds to a size limit for a key identifier in claim 9. But wherein the plurality of keys comprise a plurality of volume identifiers, each of the plurality of volume identifiers corresponding to a storage status of a corresponding volume; and a size of the at least one bucket page corresponds to a size limit for a key identifier does not go beyond the abstract idea itself. There are no additional components in the claim that would make it significantly more than the abstract idea.
Claim 10 recites the same limitations as claim 1 above. Therefore, Claim 10 is rejected based on the same reasoning.
Claim 11 recites the same limitations as claim 2 above. Therefore, Claim 11 is rejected based on the same reasoning.
Claim 12 recites the same limitations as claim 3 above. Therefore, Claim 12 is rejected based on the same reasoning.
Claim 13 recites the same limitations as claim 4 above. Therefore, Claim 13 is rejected based on the same reasoning.
Claim 14 recites the same limitations as claim 5 above. Therefore, Claim 14 is rejected based on the same reasoning.
Claim 15 recites the same limitations as claim 6 above. Therefore, Claim 15 is rejected based on the same reasoning.
Claim 16 recites the same limitations as claim 7 above. Therefore, Claim 16 is rejected based on the same reasoning.
Claim 17 recites the same limitations as claim 8 above. Therefore, Claim 17 is rejected based on the same reasoning.
Claim 18 recites the same limitations as claim 9 above. Therefore, Claim 18 is rejected based on the same reasoning.
Claim 19 recites the same limitations as claim 1 above. Therefore, Claim 19 is rejected based on the same reasoning.
Claim 20 recites the same limitations as claim 2 above. Therefore, Claim 20 is rejected based on the same reasoning.
Claim Rejections 35 U.S.C. §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 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.
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 following is a quotation of 35 U.S.C. 103 which forms the basis for all
obviousness rejections set forth in this Office action:
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable
over Bowden et al. (US 2015/0039907 A1) in view of Graefe (US 2021/0216517 A1).
Regarding claim 1, Bowden teaches a method for storage, comprising:
determining a target bucket page corresponding to a target key in at least one bucket page by performing a hash operation on the target key of a read operation, (See Bowden paragraph [0097], an update operation 19, the bucket entry identified by the translation function (the original bucket entry) is read 30 from a target bucket));
determining whether a target address corresponding to the target key exists in a plurality of records included in the target bucket page, (See Bowden paragraph [0110], a lookup operation process for verifying the presence of a key and returning associated satellite data. In step one 41, a lookup key is input to a lookup function…the lookup function f(key) generates a logical bucket identifier that supports (e.g., speeds up) a hash table lookup); and
Bowden does not explicitly disclose in response to a determination that the target address exists in the plurality of records, returning a target value from a corresponding target entry page based on the target address.
However, Graefe teaches in response to a determination that the target address exists in the plurality of records, returning a target value from a corresponding target entry page based on the target address, (See Graefe paragraph [0160], the query handler 840 can identify the data records in the identified merge level 850 matching the query. In some implementations, the query handler 840 can identify the data records matching the key values specified by the query. For example, the query handler 840 can find data records with temperature readings between −50° C. and −10° C. as requested in the query. In some implementations, the query handler 840 can determine whether the data records matching the key values specified by query exist on the database 845).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention, to modify in response to a determination that the target address exists in the plurality of records, returning a target value from a corresponding target entry page based on the target address of Graefe in order to add the first plurality of records of the first run onto the database based on at least one of the first run generation rate and the second run generation rate.
Claims 10 and 19 recite the same limitations as claim 1 above. Therefore, Claims 10 and 19 are rejected based on the same reasoning.
Regarding claim 2, Bowden taught the method of claim 1, as described.
Bowden further teaches wherein returning the target value from the target entry page comprises, (See Bowden paragraph [0110], the target bucket in flash memory is read 45a from flash memory, unless the bucket is stored in cache, in which case it can be read 45b from cache 23. In step six 46, the satellite (record) data for the key is returned to the indexing algorithm):
requesting an exclusive lock for the target bucket page and the target entry page based on the read operation, (See Bowden paragraph [0097], a plurality of cache bucket entries are read sequentially to a contiguous set of partial pages, multiple pages and/or erase blocks (e.g. a new erase block 21b) in flash memory); and
generating the target value by aggregating increment values corresponding to the target key from a cache to a disk, (See Bowden paragraph [0104], each bucket contains a set of one or more records and a reverse pointer for updating the BTT when flash buckets (e.g., pages) are inserted, moved or deleted. Each element of the bucket (record or pointer) may have redundant content added, such as additional ECC bits, to improve the individual reliability of the data structures and significantly increase the useful life of the storage devices).
Claims 11 and 20 recite the same limitations as claim 2 above. Therefore, Claims 11 and 20 are rejected based on the same reasoning.
Regarding claim 3, Bowden taught the method of claim 1, as described.
Bowden further teaches further comprising:
requesting a shared lock for the target bucket page and the target entry page based on a write operation associated with the target key, (See Bowden paragraph [0011], collecting in cache a plurality of the record data entries, to be written to the index, prior to a subsequent sequential write of the collection of entries to at least one physical bucket location of the memory); and
storing the increment values corresponding to the target key in the cache separately, (See Bowden paragraph [0099], performing a sequential write 24 of the collection of cache bucket entries to contiguous flash memory buckets. In one embodiment, a scavenging operation 25 is used for creating free erase blocks; the process includes storing any valid buckets), and
aggregating the increment values stored in the cache in response to being requested, (See Bowden paragraph [0104], each bucket contains a set of one or more records and a reverse pointer for updating the BTT when flash buckets (e.g., pages) are inserted, moved or deleted. Each element of the bucket (record or pointer) may have redundant content added, such as additional ECC bits, to improve the individual reliability of the data structures and significantly increase the useful life of the storage devices).
Claim 12 recites the same limitations as claim 3 above. Therefore, Claim 12 is rejected based on the same reasoning.
Regarding claim 4, Bowden taught the method of claim 1, as described.
Bowden does not explicitly disclose wherein the plurality of records are arranged linearly, and the last record in the plurality of records, comprises a record count for the plurality of records and a root page address of a balanced tree to indicate the balanced tree.
However, Graefe teaches wherein the plurality of records are arranged linearly, and the last record in the plurality of records, (See Graefe paragraph [0012], The first plurality of records can be initially arranged by the first corresponding plurality of index values), comprises a record count for the plurality of records and a root page address of a balanced tree to indicate the balanced tree, (See Graefe paragraph [0057], there is a wide variety of possible sort keys, as for search keys in b-tree indexes…balanced merging where all key values participate in equal or similar counts of comparisons, and merging with a high fan-in, which also reduces the number of merge levels).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was mad ,to modify wherein the plurality of records are arranged linearly, and the last record in the plurality of records, comprises a record count for the plurality of records and a root page address of a balanced tree to indicate the balanced tree of Graefe in order to adding the first plurality of records of the first run onto the database based on at least one of the first run generation rate and the second run generation rate.
Claim 13 recites the same limitations as claim 4 above. Therefore, Claim 13 is rejected based on the same reasoning.
Regarding claim 5, Bowden taught the method of claim 4, as described.
Bowden does not explicitly disclose in response to a determination that the target address does not exist in the plurality of records, identifying the balanced tree based on the root page address; determining a target index page corresponding to the target key in at least one index page in the balanced tree, and navigating to a corresponding target data page based on a target index in the target index page.
However, Graefe teaches in response to a determination that the target address does not exist in the plurality of records, identifying the balanced tree based on the root page address, (See Graefe paragraph [0118], data structure readily supports a multi-level external merge sort. At any point in time, the in-memory partition serves run generation. Each time when the appropriate number of level-0 runs exist (immediately preceding the in-memory partition), they are merged and replaced by a level-1 run); determining a target index page corresponding to the target key in at least one index page in the balanced tree, (See Graefe paragraph [0083], staggered merging turns an unsorted input stream into an ordered index. It employs run generation and merging in the style of a log-structured merge-tree. Merging is efficient because it is balanced); and navigating to a corresponding target data page based on a target index in the target index page, (See Graefe paragraph [0182], The merge tracker 830 can track the racing merge using the merge index 905, and begin a two-way merge as soon as the target quantile 910A is reached).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was mad ,to modify in response to a determination that the target address does not exist in the plurality of records, identifying the balanced tree based on the root page address; determining a target index page corresponding to the target key in at least one index page in the balanced tree, and navigating to a corresponding target data page based on a target index in the target index page of Graefe in order to adding the first plurality of records of the first run onto the database based on at least one of the first run generation rate and the second run generation rate.
Claim 14 recites the same limitations as claim 5 above. Therefore, Claim 14 is rejected based on the same reasoning.
Regarding claim 6, Bowden taught the method of claim 1, as described. Bowden further teaches further comprising:
requesting an exclusive lock for the target bucket page, (See Bowden paragraph [0097], a plurality of cache bucket entries are read sequentially to a contiguous set of partial pages, multiple pages and/or erase blocks (e.g. a new erase block 21b) in flash memory);
determining whether an empty record that has not been used exists in the plurality of records, (See Bowden paragraph [0147], The validity check (read 3) determines whether slot number 3 is empty; if so, then Q can be written to slot 3 and the algorithm is done as no entry was rewritten in slot 3); and
in response to a determination that the empty record exists in the plurality of records, (See Bowden paragraph [0147], Each entry contains a valid bit indicating if that entry is valid. Valid means it is in use (and the current occupant of the location has to be displaced). Not valid means the location is empty, and the record being processed can be written there. The contents of the valid bits can also be stored in a separate Bitmap, at the expense of some memory), requesting an exclusive lock for an entry page corresponding to the empty record for creating a new entry, (See Bowden paragraph [0147], a collection of the record data entries from the cache to the index in at least one new physical bucket location of the memory; and updating the translation table to associate the at least one new physical bucket location with a logical bucket identifier).
Claim 15 recites the same limitations as claim 6 above. Therefore, Claim 15 is rejected based on the same reasoning.
Regarding claim 7, Bowden taught the method of claim 1, as described. Bowden further teaches further comprising:
requesting an exclusive lock for the target bucket page, (See Bowden paragraph [0097], a plurality of cache bucket entries are read sequentially to a contiguous set of partial pages, multiple pages and/or erase blocks (e.g. a new erase block 21b) in flash memory);
determining whether a record that has been used and contains the target key exists in the plurality of records, (See Bowden paragraph [0147], The validity check (read 3) determines whether slot number 3 is empty; if so, then Q can be written to slot 3 and the algorithm is done as no entry was rewritten in slot 3);;
in response to a determination that the record exists in the plurality of records, (See Bowden paragraph [0147], Each entry contains a valid bit indicating if that entry is valid. Valid means it is in use (and the current occupant of the location has to be displaced). Not valid means the location is empty, and the record being processed can be written there. The contents of the valid bits can also be stored in a separate Bitmap, at the expense of some memory), determining whether the last record in the plurality of records has been used, (See Bowden paragraph [0133], the index record is used as an input key to the lookup function f(key));
in response to a determination that the last record has not been used, releasing the record for removal of entries, (See Bowden paragraph [0111], the insert process reads the target bucket 22 from an erase block 21a of flash memory 75a, or from cache 75b. In step six 76, the insert process inserts the record entry into the target bucket and writes the modified bucket to cache),
wherein an entry page corresponding to the record is retained, (See Bowden paragraph [0133], the index record is used as an input key to the lookup function f(key)).
Claim 16 recites the same limitations as claim 7 above. Therefore, Claim 16 is rejected based on the same reasoning.
Regarding claim 8, Bowden taught the method of claim 7, as described. Bowden further teaches further comprising:
requesting an exclusive lock for a root page of the balanced tree, (See Bowden paragraph [0097], a plurality of cache bucket entries are read sequentially to a contiguous set of partial pages, multiple pages and/or erase blocks (e.g. a new erase block 21b) in flash memory); and
Bowden does not explicitly disclose in response to a determination that the last record has been used, identifying the balanced tree based on the root page address of the balanced tree included in the last record, and populating an index and data of the first entry in the balanced tree to the record and the entry page corresponding to the record.
However, Graefe teaches in response to a determination that the last record has been used, identifying the balanced tree based on the root page address of the balanced tree included in the last record, (See Graefe paragraph [0083], generation and merging in the style of a log-structured merge-tree. Merging is efficient because it is balanced, See Graefe paragraph [0116], An exact-match (equality) query performs a root-to-leaf b-tree search within the in-memory partition and then accesses the correct pages within earlier partitions like a linked list. In this search); and populating an index and data of the first entry in the balanced tree to the record and the entry page corresponding to the record, (See Graefe paragraph [0083], generation and merging in the style of a log-structured merge-tree. Merging is efficient because it is balanced, See Graefe paragraph [0116], An exact-match (equality) query performs a root-to-leaf b-tree search within the in-memory partition and then accesses the correct pages within earlier partitions like a linked list. In this search).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was mad ,to modify in response to a determination that the last record has been used, identifying the balanced tree based on the root page address of the balanced tree included in the last record, and populating an index and data of the first entry in the balanced tree to the record and the entry page corresponding to the record of Graefe in order to adding the first plurality of records of the first run onto the database based on at least one of the first run generation rate and the second run generation rate.
Claim 17 recites the same limitations as claim 8 above. Therefore, Claim 17 is rejected based on the same reasoning.
Regarding claim 9, Bowden taught the method of claim 1, as described. Bowden further teaches further wherein
the plurality of keys comprise a plurality of volume identifiers, each of the plurality of volume identifiers corresponding to a storage status of a corresponding volume, (See Bowden paragraph [0147], The contents of slot 3 are known if we have a Bitmap; otherwise, we need to read the entry in slot 3 to determine its status. Each entry contains a valid bit indicating if that entry is valid. Valid means it is in use (and the current occupant of the location has to be displaced); and
a size of the at least one bucket page corresponds to a size limit for a key identifier, (See Bowden paragraph [0151], a bucket entry 160. A 4 KB bucket size is based on the underlying device minimum write size, here a 4 KB page).
Claim 18 recites the same limitations as claim 9 above. Therefore, Claim 18 is rejected based on the same reasoning.
Conclusions/Points of Contacts
The prior art made of record and not relied upon is considered pertinent to
applicant’s disclosure. See form PTO-892.
Shveidel et al. (US Patent No. 11093169 B1), metadata 112 may be stored in storage devices 106 in physical groups or “buckets” where each bucket of metadata 112 may comprise a bucket map page and one or more metadata pages that each characterize a set of n data pages stored in datasets 110. The bucket map page defines the layout of the bucket of metadata including, for example, which metadata pages exist in the bucket.
Yang et al. (US Patent No. 10, 296, 498 B2) a multi-node system uses a hybrid hash index, a portion of which represents a corresponding master hash index, to index into both the master hash table and into a local hash table for a given lock. In this way, the hash index used to store lock metadata in a particular local hash table bucket, on a particular lock master, encodes the lock master index, for a master hash table, to which the locks in the local hash table bucket correspond.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MULUEMEBET GURMU whose telephone number is (571)270-7095. The examiner can normally be reached M-F 9am - 5pm.
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, Tony Mahmoudi can be reached at 5712724078. 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.
/MULUEMEBET GURMU/Primary Examiner, Art Unit 2163