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 .
Specification
The abstract of the disclosure is objected to because it contains phrases that should be avoided such as “provided”. A corrected abstract of the disclosure is required and must be presented on a separate sheet, apart from any other text. See MPEP § 608.01(b).
Applicant is reminded of the proper language and format for an abstract of the disclosure.
The abstract should be in narrative form and generally limited to a single paragraph on a separate sheet within the range of 50 to 150 words in length. The abstract should describe the disclosure sufficiently to assist readers in deciding whether there is a need for consulting the full patent text for details.
The language should be clear and concise and should not repeat information given in the title. It should avoid using phrases which can be implied, such as, “The disclosure concerns,” “The disclosure defined by this invention,” “The disclosure describes,” etc. In addition, the form and legal phraseology often used in patent claims, such as “means” and “said,” should be avoided.
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.
Claim 11 is 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 11 recites the limitation "the snapshot" in line 3. There is insufficient antecedent basis for this limitation in the claim.
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.
Claims 1-8 are rejected under 35 U.S.C. 103 as being unpatentable Paul et al. (US 20190318042, hereinafter Paul) in view of Ertl (US 20230205660).
Re. claim 1, Paul discloses an apparatus comprising: hash circuitry configured, in response to receipt of a set of values, to generate a set of hash values (Paul discloses a new element may be read from the multiset that is being evaluated, and a hash value for the new element may be determined [0033]. An HLL estimator applies a hash function to the elements [0012]); signature storage circuitry configured to store signature data indicative of a subset of the set of hash values (Paul discloses Each hash value is mapped to a particular bucket. A bucket includes an index and a value. The first x bits (e.g., 12 bits) of the hash value may determine the index of the bucket to which the hash value is mapped, and the last y bits (e.g., 52 bits) of the hash value may determine the value that is stored in the bucket [0012]), wherein the signature storage circuitry is responsive to receipt of a hash value of the set of hash values: when the hash value falls within a dynamically varying range defined at least in part based on the subset, to retain the hash value in the subset and to discard an existing member of the subset (Paul discloses If it is determined that the new value is greater than the existing value, the existing value in the bucket may be replaced with the new value [0077][0063]); and when the hash value does not fall within the dynamically varying range, to discard the hash value (Paul discloses the index of the first bucket in the unsorted portion is 4011. Thus, in this example, the HLL estimator may compare the value of the first bucket in the unsorted portion with the value of the new element. Since the value of the new element (which is 1) is less than the value of the first bucket in the unsorted portion (which is 2), the HLL estimator may simply discard the new element without making any changes to the sparse representation [0043][0063][0077]).
Paul discloses a signature storage circuity, Paul does not explicitly teach but Ertl teaches wherein store, for each stored hash value of the subset, an occurrence count indicative of a number of repeat occurrences of the stored hash value that occur in the set of hash values during a period in which the stored hash value is retained in the subset (Ertl teaches when two MinHash records having the same register count and register capacity are received [0130]. Lower initial value for K.sub.low may be calculated and the recording may be repeated [0150]); and calculation circuitry configured to calculate an estimate of a frequently occurring portion of the set of values based on stored hash values for which the occurrence count meets a predetermined condition (Ertl teaches determines the cardinality of the sets that are described by the received MinHash records, either from separately recorded cardinality monitoring data, or by using the MinHash records to calculate an estimation for the cardinality. As described in step 1003, the cardinality estimation may iterate over the register values K′ of the registers of each MinHash record, subtract the register value from 1, calculate the logarithm of the subtraction result and then add the negated results of the logarithm to calculate a register sum value [0131][0150][0090]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul to include store, for each stored hash value of the subset, an occurrence count indicative of a number of repeat occurrences of the stored hash value that occur in the set of hash values during a period in which the stored hash value is retained in the subset; and calculation circuitry configured to calculate an estimate of a frequently occurring portion of the set of values based on stored hash values for which the occurrence count meets a predetermined condition as disclosed by Ertl. One of ordinary skill in the art would have been motivated for the purpose of improve the estimation error, higher estimation accuracy (Ertl [0012]).
Re. claim 2, Paul-Ertl teach the apparatus of claim 1, wherein: the signature data is second signature data, the subset is a second subset, and the second signature data is stored during a second access window; the signature storage circuitry is configured to store first signature data indicative of a first subset of the set of hash values during a first access window; and the calculation circuitry is configured to calculate the estimate based on comparison of the first signature data and the second signature data (Ertl teaches calculating/estimating the cardinality of sets or overlap/similarity metrics for two or more sets are frequently required [0004][0016][0044]. Compares the calculated update value candidate k with the register value lower bound K.sub.low [0086] Fig. 9).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul to include the signature data is second signature data, the subset is a second subset, and the second signature data is stored during a second access window; the signature storage circuitry is configured to store first signature data indicative of a first subset of the set of hash values during a first access window; and the calculation circuitry is configured to calculate the estimate based on comparison of the first signature data and the second signature data as disclosed by Ertl. One of ordinary skill in the art would have been motivated for the purpose of improve the estimation error, higher estimation accuracy (Ertl [0012]).
Re. claim 3, Paul-Ertl teach the apparatus of claim 2, wherein a start of the second access window begins after a start of the first access window and at least a portion of the second access window overlaps with the first access window data (Ertl teaches calculating/estimating the cardinality of sets or overlap/similarity metrics for two or more sets are frequently required [0004][0016][0044]. Compares the calculated update value candidate k with the register value lower bound K.sub.low [0086] Fig. 9).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul to include wherein a start of the second access window begins after a start of the first access window and at least a portion of the second access window overlaps with the first access window data as disclosed by Ertl. One of ordinary skill in the art would have been motivated for the purpose of improve the estimation error, higher estimation accuracy (Ertl [0012]).
Re. claim 4, Paul-Ertl teach the apparatus of claim 2, wherein first signature data is independent of a number of repeat occurrences of hash values retained in the first subset (Ertl teaches when two MinHash records having the same register count and register capacity are received [0130]. Lower initial value for K.sub.low may be calculated and the recording may be repeated [0150]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul to include wherein first signature data is independent of a number of repeat occurrences of hash values retained in the first subset as disclosed by Ertl. One of ordinary skill in the art would have been motivated for the purpose of improve the estimation error, higher estimation accuracy (Ertl [0012]).
Re. claim 5, Paul-Ertl teach the apparatus of claim 2, wherein the estimate is based on an intersection size of an intersection of the second subset of hash values for which the occurrence count meets the predetermined condition and the first subset of hash values (Paul discloses the HLL estimator may multiply the sorting threshold by the number of times that the sparse representation has been sorted and the number of bits in each bucket (the sparse representation may be configured so that each bucket has the same size), and then add 1 [0036]).
Re. claim 6, Paul-Ertl teach the apparatus of claim 5, comprising cardinality estimation circuitry configured to calculate a cardinality estimate of the set of values, wherein the estimate comprises multiplying the cardinality estimate by a ratio of the intersection size and a size of the first subset (Paul discloses the HLL estimator may multiply the sorting threshold by the number of times that the sparse representation has been sorted and the number of bits in each bucket (the sparse representation may be configured so that each bucket has the same size), and then add 1 [0036]).
Re. claim 7, Paul-Ertl teach the apparatus of claim 6, the calculation circuitry is configured to estimate a number of newly received values based on a difference between the first cardinality estimate and the second cardinality estimate (Paul discloses the HLL estimator may compare the value of the first bucket in the unsorted portion with the value of the new element. Since the value of the new element (which is 1) is less than the value of the first bucket in the unsorted portion (which is 2), the HLL estimator may simply discard the new element without making any changes to the sparse representation [0043]).
Paul does not explicitly teach but Ertl teaches wherein: the cardinality estimation circuitry is configured to calculate a first cardinality estimate at the start of the second access window, and a second cardinality estimate at the end of the second access window (Ertl teaches r MinHash for the creation of LSH indices as has a much lower memory footprint than MinHash for similar supported cardinalities and desired estimation accuracies [0136]. Start index 1111 and end index 1112 define a range of register index values of register records 210 that are considered for a specific signature segment [0138] Fig. 11);
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul to include the cardinality estimation circuitry is configured to calculate a first cardinality estimate at the start of the second access window, and a second cardinality estimate at the end of the second access window as disclosed by Ertl. One of ordinary skill in the art would have been motivated for the purpose of improve the estimation error, higher estimation accuracy (Ertl [0012]).
Re. claim 8, Paul-Ertl teach the apparatus of claim 7, wherein: the signature storage circuitry is configured to discard a plurality of hash values based on the number of newly received values (Paul discloses the HLL estimator may compare the value of the first bucket in the unsorted portion with the value of the new element. Since the value of the new element (which is 1) is less than the value of the first bucket in the unsorted portion (which is 2), the HLL estimator may simply discard the new element without making any changes to the sparse representation [0043]).
Paul does not explicitly teach but Ertl teaches a number of hash values discarded is based on the number of newly received values divided by the second estimate of cardinality (Ertl teaches compare the created random number with the result of the configuration parameter b taken to the power of −K.sub.low and terminates the process with step 515 if x.sub.j is greater, as with this relation of x.sub.j and K.sub.low, neither x.sub.j, nor any subsequently created ascending random number may change any register value [0084]. The random number may then be divided by the result of register count m+1−iteration count j. [0096] [0115]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul to include a number of hash values discarded is based on the number of newly received values divided by the second estimate of cardinality as disclosed by Ertl. One of ordinary skill in the art would have been motivated for the purpose of improve the estimation error, higher estimation accuracy (Ertl [0012]).
Re. claim 13, Paul-Ertl teach the apparatus of claim 1, wherein the set of values is a set of accessed memory addresses, and the frequently occurring portion is a set of frequently accessed memory addresses (Paul [0012][0024][0036][0039]).
Re. claim 14, Paul-Ertl teach the apparatus of claim 1, wherein at least one of an upper bound and a lower bound of the dynamically varying range is defined based on an extremum of the subset (Paul [0034]).
Re. claim 16, claim 16 is rejected with the same rationale as applied in claims 1-3 above.
Re. claim 17. Paul discloses a system comprising: the apparatus of claim 1 (Paul and Ertl teaches claim 1), implemented in at least one packaged chip; at least one system component; and a board, wherein the at least one packaged chip and the at least one system component are assembled on the board (Paul discloses a single or multi-chip [0066]. A board with processor, memory and resister and etc. [0067]).
Re. claim 18. Paul discloses a chip-containing product comprising the system of claim 17 (Paul and Ertl teaches claim 17), wherein the system is assembled on a further board with at least one other product component (Paul discloses a single or multi-chip [0066]. A board with processor, memory and resister and etc. [0067]).
Re. claim 19, claim 19 is rejected with the same rationale as applied in claim 1 above.
Re. claim 20, Paul discloses a non-transitory computer-readable medium storing computer-readable code for fabrication of the apparatus of claim 1 (Paul discloses a RAM [0067]. Paul and Ertl teaches claim 1).
Claims 9-12 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Paul et al. (US 20190318042, hereinafter Paul) in view of Ertl (US 20230205660) and in further view of Barrell et al. (US 11429587, hereinafter Barrell).
Re. claim 9, Paul-Ertl teach the apparatus of claim 1, Paul-Ertl do not explicitly teach but Barrell teaches wherein the signature storage circuitry is configured to evict hash values based on a comparison between the occurrence count and a threshold for each one of the hash values (Barrell teaches the counter associated with each hash entry may provide each entry with a relative temporal component that can be compared against a threshold to determine a relative age of the entry. When the counter is above a threshold, the entry may be removed from the hash database [Col 7 lines 4-21]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul-Ertl to include wherein the signature storage circuitry is configured to evict hash values based on a comparison between the occurrence count and a threshold for each one of the hash values as disclosed by Barrell. One of ordinary skill in the art would have been motivated for the purpose of preventing storage of duplicative data (Barrell [Col 1 lines 11-24]).
Re. claim 10, Paul-Ertl-Barrell teach the apparatus of claim 9, Paul-Ertl do not explicitly teach but Barrell teaches comprising an access counter, wherein the signature storage circuitry is configured to store, for each stored hash value of the subset, a snapshot of the access counter, wherein the calculation circuitry is configured, for each one of the hash values, to perform the comparison based on a difference between the access counter and the snapshot for that one of the hash values (Barrell teaches the counter associated with each hash entry may provide each entry with a relative temporal component that can be compared against a threshold to determine a relative age of the entry. When the counter is above a threshold, the entry may be removed from the hash database [Col 7 lines 4-21]. Determine if the data is still a duplicate, as situations could arise where data that once was a duplicate is no longer a duplicate and is now unique data (e.g. the duplicate copies were deleted) that could have an associated entry trimmed from the hash database [Col 7 lines 22-45]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul-Ertl to include an access counter, wherein the signature storage circuitry is configured to store, for each stored hash value of the subset, a snapshot of the access counter, wherein the calculation circuitry is configured, for each one of the hash values, to perform the comparison based on a difference between the access counter and the snapshot for that one of the hash values as disclosed by Barrell. One of ordinary skill in the art would have been motivated for the purpose of preventing storage of duplicative data (Barrell [Col 1 lines 11-24]).
Re. claim 11, Paul-Ertl-Barrell teach the apparatus of claim 9, Paul-Ertl do not explicitly teach but Barrell teaches wherein the signature storage circuitry is configured to evict hash values for which a ratio between the occurrence count and a difference between the snapshot and the access counter is less than the threshold (Barrell teaches the counter associated with each hash entry may provide each entry with a relative temporal component that can be compared against a threshold to determine a relative age of the entry. When the counter is above a threshold, the entry may be removed from the hash database [Col 7 lines 4-21]. Determine if the data is still a duplicate, as situations could arise where data that once was a duplicate is no longer a duplicate and is now unique data (e.g. the duplicate copies were deleted) that could have an associated entry trimmed from the hash database [Col 7 lines 22-45]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul-Ertl to include wherein the signature storage circuitry is configured to evict hash values for which a ratio between the occurrence count and a difference between the snapshot and the access counter is less than the threshold as disclosed by Barrell. One of ordinary skill in the art would have been motivated for the purpose of preventing storage of duplicative data (Barrell [Col 1 lines 11-24]).
Re. claim 12, Paul-Ertl-Barrell teach the apparatus of claim 11, Paul-Ertl do not explicitly teach but Barrell teaches wherein evicting hash values comprises setting the hash value to one of: a predetermined constant, the predetermined constant numerically furthest outside of the dynamically varying range; and an invalid value (Barell teaches setting a first indicator or flag identifying the hash entry [Col 13 lines 20-39]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul-Ertl to include wherein evicting hash values comprises setting the hash value to one of: a predetermined constant, the predetermined constant numerically furthest outside of the dynamically varying range; and an invalid value as disclosed by Barrell. One of ordinary skill in the art would have been motivated for the purpose of preventing storage of duplicative data (Barrell [Col 1 lines 11-24]).
Re. claim 15, Paul-Ertl teach the apparatus of claim 14, Paul-Ertl do not explicitly teach but Barrell teaches wherein the existing member of the subset is the extremum of the subset (Barell teaches the total number of hash entries can be very large and impractical to search through. The database can be designed to store up to a maximum number of entries and after that the performance of the database drops significantly [Col 4 lines 14-29]).
Therefore, it would have been obvious to one or ordinary skill in the art before the effective filing date of the claimed invention to modify the method and system disclosed by Paul-Ertl to include wherein the existing member of the subset is the extremum of the subset as disclosed by Barrell. One of ordinary skill in the art would have been motivated for the purpose of preventing storage of duplicative data (Barrell [Col 1 lines 11-24]).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Wong (US 20230119183) discloses identify second file's minimum value from at least value from applying function to second file's segment and value from applying function to second file's second segment. Identify second file's second minimum value from at least value from applying second function to second file's segment and value from applying second function to second file's second segment. Estimate first and second files' union size based on whether first file's minimum value equals second file's minimum value, whether first file's second minimum value equals second file's second minimum value, first file's size, and second file's size.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to KEVIN A AYALA whose telephone number is (571)270-3912. The examiner can normally be reached Monday-Thursday 8AM-5PM; Friday: Variable EST.
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, Jorge Ortiz-Criado can be reached at 571-272-7624. 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.
/KEVIN AYALA/Primary Examiner, Art Unit 2496