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 .
DETAILED ACTION
Claims 1-52 are present in this application. Claims 1-32 are cancelled. Claims 33-52 are pending in this office action.
This office action is NON-FINAL.
Drawings
The Drawings filed on 08/23/24 are acceptable for examination purposes.
Specification
The Specification filed on 08/23/24 is acceptable for examination purposes.
Information Disclosure Statement
The information disclosure statements (IDS) filed on 08/23/24 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
Claims 33-52 are rejected under 35 U.S.C. 101 as directed to non-statutory
subject matter of software, per se. The claim(s) lack(s) the necessary physical articles
or objects to constitute a machine or manufacture within the meaning of 35 U.S.C. 101.
In this case, applicant has claimed a “system" in the preamble to these claims without
reciting any hardware element in the bodies of these claims; this implies that Applicant
is claiming a system of software, per se, lacking the hardware necessary to realize any
of the underlying functionality. Therefore, claims 33-52 are directed to non-statutory
subject matter as computer programs, per se.
Claim Rejections 35 U.S.C. §103
6. 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 33-35, 37-40, and 44-52 are rejected under 35 U.S.C. 103 as being unpatentable over Gura et al. (US 2015/0058595 A1) in view of Wang et al. (US 2021/0390075 A1).
Regarding claim 33 Gura teaches a system for generating a hash table comprising a plurality of buckets configured to receive a number of unique keys, the system comprising, (See Gura paragraph [0036], data associated with a key k may first require the evaluation of H(k) to compute a unique index i. The index i may then be used as an address into a memory holding a d-bit data entry D(k) associated with k):
at least one processing unit configured to, (See Gura paragraph [0031], processing devices including network interface cards, network processors,):
determine an initial set of hash table parameters; (See Gura paragraph [0069], generated using the specified hash table(s), and parameters),
determine, based on the initial set of hash table parameters, (See Gura paragraph [0069], generated using the specified hash table(s), and parameters),
build the hash table according to the initial set of hash table parameters, (See Gura paragraph [0069], an index/address may be generated using the specified hash table(s), and parameters for the specified primary hash table(s) may be selected from multiple parameter sets), if the utilization value is greater than or equal to the number of unique keys, (See Gura paragraph [0036], A perfect hash function H for a set K of m unique keys of r bits is a mapping function that maps each key k.epsilon.K to a unique integer i=H(k)), See Gura paragraph [0077], input keys that result in an index greater than the maximal index may be detected.; and
if the utilization value is less than the number of unique keys, then change one or more parameters of the initial set of hash table parameters, (See Gura paragraph [0076], a logical value of 1 (true) if H(k) is less than or equal to maximal index 1058, or to output a logical value of 0 otherwise. In other words, in this and other embodiments, individual hash tables may be configured with a valid index range from 0 to the maximal index, and input keys that result in an index greater than the maximal index may be detected), to provide an updated set of hash table parameters that result in the utilization value being greater than or equal to the number of unique keys, (See Gura paragraph [0076], hash tables may be configured with a valid index range from 0 to the maximal index, and input keys that result in an index greater than the maximal index may be detected), and build the hash table according to the updated set of hash table parameters, (See Gura paragraph [0079], update one or more hash tables (e.g., when the values associated with one or more of the keys change)).
Gura does not explicitly disclose a utilization value that results in a predicted probability of an overflow event being less than or equal to a predetermined overflow probability threshold.
However, Wang teaches a utilization value that results in a predicted probability, (See Wang paragraph [0022], (a) determining probabilities of reaching an empty slot in the linear hash table and (b) using the probabilities to predict a likely number of slots to read before encountering an empty slot), of an overflow event being less than or equal to a predetermined overflow probability threshold, (See Wang paragraph [0038], The requesting device may compute a message size based on the predicted number of slots and, if the message size is greater than the threshold value, the requesting device may reduce the number of slots so that the message size is below the threshold value).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was made, to modify a utilization value that results in a predicted probability of an overflow event being less than or equal to a predetermined overflow probability threshold of Wang for dynamically adjusting read sizes of RDMA read requests sent to a remotely located linear hash table.
Regarding claim 34, Gura taught the system of claim 1, as described
above. Gura further teaches wherein the initial set of hash table parameters, (See Gura paragraph [0069], generated using the specified hash table(s), and parameters for the specified primary hash table(s)), includes one or more of a number of buckets, a bucket size, and a number of choices, (See Gura paragraph [0032], a variable number of hash tables, and each of the hash tables may support a different key size, a different number of keys, and/or differently-sized data entries associated with each key than other tables).
Regarding claim 35, Gura taught the system of claim 34, as described
above. Gura further teaches wherein the initial set of hash table parameters, (See Gura paragraph [0032], the number and/or size of the data words associated with the keys, and/or other parameters of the hash tables), further includes at least one of a size of each of the unique keys, a number of hash functions, one or more hash function seeds, an available memory from a memory storage unit, an element size or a combination thereof, (See Gura paragraph [0036], A perfect hash function H for a set K of m unique keys of r bits is a mapping function that maps each key k.epsilon.K to a unique integer i=H(k). If the unique integers i are consecutive).
Regarding claim 37, Gura taught the system of claim 33, as described
above. Gura further teaches wherein:
building the hash table according to the initial set of hash table parameters, (See Gura paragraph [0032], the user to create a variable number of hash tables, and each of the hash tables…parameters of the hash tables), occurs when a ratio of the number of unique keys, (See Gura paragraph [0036], A perfect hash function H for a set K of m unique keys of r bits is a mapping function that maps each key k.epsilon.K to a unique integer i=H(k). If the unique integers i are consecutive), to a number of elements allocated for the hash table is greater than or equal to a predetermined filling ratio threshold value, (See Gura paragraph [0077], hash tables may be configured with a valid index range from 0 to the maximal index, and input keys that result in an index greater than the maximal index may be detected); and
building the hash table according to the updated set of hash table parameters, (See Gura paragraph [0032], the user to create a variable number of hash tables, and each of the hash tables…parameters of the hash tables), occurs when a ratio of the number of unique keys to the number of elements allocated for the hash table, (See Gura paragraph [0036], A perfect hash function H for a set K of m unique keys of r bits is a mapping function that maps each key k.epsilon.K to a unique integer i=H(k). If the unique integers i are consecutive, e.g., 0.ltoreq.i.ltoreq.m-1 for all i, the mapping is called a minimal perfect hash function (MPHF)), is less than the predetermined filling ratio threshold value, (See Gura paragraph [0077], a logical value of 1 (true) if H(k) is less than or equal to maximal index 1058, or to output a logical value of 0 otherwise. In other words, in this and other…individual hash tables), and wherein changing the one or more parameters of the initial set of hash table parameters to provide the updated set of hash table parameters, (See Gura paragraph [0036], a user application may be configured to initialize one or more hash tables in the DMEM (after which it, or another user application or thread, may retrieve those values), or may be configured to update one or more hash tables (e.g., when the values associated with one or more of the keys change), further results in the ratio of the number of unique keys to the number of elements allocated, (See Gura paragraph [0036], A perfect hash function H for a set K of m unique keys of r bits is a mapping function that maps each key k.epsilon.K to a unique integer i=H(k). If the unique integers i are consecutive, e.g., 0.ltoreq.i.ltoreq.m-1 for all i), for the hash table being greater than or equal to the predetermined filling ratio threshold value, (See Gura paragraph [0036], hash tables may be configured with a valid index range from 0 to the maximal index, and input keys that result in an index greater than the maximal index may be detected).
Regarding claim 38, Gura taught the system of claim 37, as described
above. Gura further teaches wherein the number of elements allocated for the hash table, (See Gura paragraph [0032], a variable number of hash tables, and each of the hash tables may support a different key size, a different number of keys, and/or differently-sized data entries associated with each key than other tables), is equal to a number of buckets multiplied by a bucket size, and the number of elements is greater than or equal to the number of unique keys to insert into the hash table, (See Gura paragraph [0065], the d2-bit value D2(k)=DMEM(H(k)) may represent the D2(k) portion of the data associated with a given value of key k. In various embodiments, d (which may be equal to d1+d2) may be chosen in accordance with the maximum size of the data D(k) that is associated with any valid value of key k (e.g., any value of key k for which an entry is included in DMEM 810) or in accordance with the maximum size of the D2(k) portion of D(k)).
Regarding claim 39, Gura taught the system of claim 33, as described
above.
Gura does not explicitly disclose wherein the predicted probability of the overflow event is determined based at least in part on the initial set of hash table parameters. However, Wang teaches wherein the predicted probability of the overflow event is determined based at least in part on the initial set of hash table parameters, (See Wang paragraph [0022], (a) determining probabilities of reaching an empty slot in the linear hash table and (b) using the probabilities to predict a likely number of slots to read before encountering an empty slot).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was made, to modify wherein the predicted probability of the overflow event is determined based at least in part on the initial set of hash table parameters of Wang for dynamically adjusting read sizes of RDMA read requests sent to a remotely located linear hash table.
Regarding claim 40, Gura taught the system of claim 33, as described
above. Gura further teaches wherein the predetermined overflow probability threshold is greater than or equal to 0%, (See Gura paragraph [0077], hash tables may be configured with a valid index range from 0 to the maximal index, and input keys that result in an index greater than the maximal index may be detected).
Regarding claim 44, Gura taught the system of claim 33, as described
above. Gura further teaches wherein the hash table is stored in a memory storage unit, (See Gura paragraph [0009], hash tables that provide low-latency access to data stored in memory).
Regarding claim 45, Gura taught the system of claim 44, as described
above. Gura further teaches wherein the memory storage unit is internal to the system, (See Gura paragraph [0109], multiple processor cores may be included in a single processor chip (e.g., a single processor).
Regarding claim 46, Gura taught the system of claim 44, as described
above. Gura further teaches wherein the memory storage unit is external to the system, (See Gura paragraph [0114], computer system 1500 may be coupled to one or more external devices).
Regarding claim 47, Gura taught the system of claim 33, as described
above. Gura further teaches wherein the at least one processing unit is further configured to:
detect an overflow event, (See Gura paragraph [0077], an index greater than the maximal index may be detected);
in response to the detected overflow event, (See Gura paragraph [0077], an index greater than the maximal index may be detected); change one or more parameters of the initial or updated set of hash table parameters, (See Gura paragraph [0079], update one or more hash tables (e.g., when the values associated with one or more of the keys change), used to build the hash table to provide a refined set of hash table parameters, (See Gura paragraph [0032], the user to create a variable number of hash tables); and
re-build the hash table using the refined set of hash table parameters, (See Gura paragraph [0032], the user to create a variable number of hash tables, and each of the hash tables may support a different key size).
Regarding claim 48, Gura taught the system of claim 47, as described
above. Gura further teaches wherein the refined set of hash table parameters, (See Gura paragraph [0069], generated using the specified hash table(s), and parameters), includes more buckets than a number of buckets associated with the initial or updated set of hash table parameters, (See Gura paragraph [0079], initialize one or more hash tables in the DMEM (after which it, or another user application or thread, may retrieve those values), or may be configured to update one or more hash tables).
Regarding claim 49, Gura taught the system of claim 47, as described
above. Gura further teaches wherein the refined set of hash table parameters, (See Gura paragraph [0069], generated using the specified hash table(s)), includes a bucket size greater than a bucket size associated with the initial or updated set of hash table parameters, (See Gura paragraph [0079], one or more hash tables in the DMEM (after which it, or another user application or thread, may retrieve those values), or may be configured to update one or more hash tables).
Regarding claim 50, Gura taught the system of claim 47, as described
above. Gura further teaches wherein the refined set of hash table parameters, (See Gura paragraph [0069], generated using the specified hash table(s)), includes a number of choices greater than a number of choices associated with the initial or updated set of hash table parameters, (See Gura paragraph [0079], one or more hash tables in the DMEM (after which it, or another user application or thread, may retrieve those values), or may be configured to update one or more hash tables).
Regarding claim 51, Gura taught the system of claim 47, as described
above. Gura further teaches wherein detecting the overflow event, (See Gura paragraph [0032], an index greater than the maximal index may be detected), occurs during the building of the hash table or during an operation performed on the hash table, (See Gura paragraph [0032], allow the user to create a variable number of hash tables, and each of the hash tables).
Regarding claim 52, Gura taught the system of claim 47, as described
above. Gura further teaches wherein, after providing the refined set of hash table parameters, (See Gura paragraph [0069], generated using the specified hash table(s), the at least one processing unit is further configured to, (See Gura paragraph [0031], processing devices):
determine, based on the refined set of hash table parameters, (See Gura paragraph [0069], generated using the specified hash table(s), and
verify that the new utilization value is greater than or equal to a number of unique keys, (See Gura paragraph [0021], a perfect hash function to a key value, retrieve data associated with the key value, and verify the validity of the key value, in which at least a portion of the retrieved data is made available prior to verifying the validity of the key value), before re-building the hash table using the refined set of hash table parameters, (See Gura paragraph [0032], the user to create a variable number of hash tables, and each of the hash tables may support a different key size).
Gura does not explicitly disclose a new utilization value that results in a new predicted probability of a new overflow event being less than or equal to the predetermined overflow probability threshold.
However, Wang teaches a new utilization value that results in a new predicted probability, (See Wang paragraph [0022], (a) determining probabilities of reaching an empty slot in the linear hash table and (b) using the probabilities to predict a likely number of slots to read before encountering an empty slot), of a new overflow event being less than or equal to the predetermined overflow probability threshold, (See Wang paragraph [0038], The requesting device may compute a message size based on the predicted number of slots and, if the message size is greater than the threshold value, the requesting device may reduce the number of slots so that the message size is below the threshold value).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was made, to modify a new utilization value that results in a new predicted probability of a new overflow event being less than or equal to the predetermined overflow probability threshold of Wang for dynamically adjusting read sizes of RDMA read requests sent to a remotely located linear hash table.
Claims 36 and 43 are rejected under 35 U.S.C. 103 as being unpatentable
over Gura et al. (US 2015/0058595 A1) in view of Wang et al. (US 2021/0390075 A1) and further in view of CAFARELLA et al. (US 2016/0267142 A1).
Regarding claim 36, Gura taught the system of claim 34, as described
above.
Gura together with Wang does not explicitly disclose wherein the utilization value is based on an asymptotic balanced formula applied to the initial set of hash table parameters.
However, CAFARELLA teaches wherein the utilization value is based on an asymptotic balanced formula applied to the initial set of hash table parameters, (ISee CAFARELLA paragraph [0141], asymptotic running time is linear in the sum of the searched text and pattern lengths. The algorithm encodes all the search patterns in a finite automaton that consumes the input text one character at a time).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was made, to modify wherein the utilization value is based on an asymptotic balanced formula applied to the initial set of hash table parameters of CAFARELLA in order to detect a predetermined pattern in a stream of symbols.
Regarding claim 43, Gura taught the system of claim 33, as described
above.
Gura together with Wang does not explicitly disclose wherein the processing unit is an accelerator processor.
However, CAFARELLA teaches wherein the processing unit is an accelerator processor, (See CAFARELLA paragraph [0369], The processor may then issue a command to the hardware accelerator).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was made, to modify wherein the processing unit is an accelerator processor of CAFARELLA in order to detect a predetermined pattern in a stream of symbols.
Claims 41 and 42 are rejected under 35 U.S.C. 103 as being unpatentable
over Gura et al. (US 2015/0058595 A1) in view of Wang et al. (US 2021/0390075 A1) and further in view of Rajgopal et al. (US 2005/0141519 A1).
Regarding claim 41, Gura taught the system of claim 33, as described
above.
Gura together with Wang does not explicitly disclose wherein the predetermined overflow probability threshold is less than 10%.
However, Rajgopal teaches wherein the predetermined overflow probability threshold is less than 10%, (See Rajgopal paragraph [0028], determining when to stop allocation blocks to a given hash table, the simplest of which is to pre-assign a fixed (maximum) number of blocks n and stop when all of those blocks are allocated to the hash table).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was made, to modify wherein the predetermined overflow probability threshold is less than 10% of Rajgopal in order to detect a predetermined pattern in a stream of symbols.
Regarding claim 42, Gura taught the system of claim 37, as described
above.
Gura together with Wang does not explicitly disclose wherein the predetermined filling ratio threshold value is at least 80%.
However, Rajgopal teaches wherein the predetermined filling ratio threshold value is at least 80%, (See Rajgopal paragraph [0028], determining when to stop allocation blocks to a given hash table, the simplest of which is to pre-assign a fixed (maximum) number of blocks n and stop when all of those blocks are allocated to the hash table).
It would have been obvious to one with ordinary skill in the art before the
effective filing date of the claimed invention was made, to modify wherein the predetermined filling ratio threshold value is at least 80% of Rajgopal in order to detect a predetermined pattern in a stream of symbols.
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.
Eskin et al. (US 2004/0205474 A1), methods for monitoring sequential behavior performed during execution of a process on a computer system to detect an intrusion from normal operation of the computer system. The sequential behavior refers to any sequence of symbols or operations that can be audited during the operation of a process by the computer system.
Mohamed et al. (US Patent No. 10, 417, 350 B) The token combinations may be deemed “influential” in that the presence or occurrence of the token combinations in an input text collection may be correlated with a high probability (e.g., a probability above some selected threshold) of the corresponding class being selected as the class to which the input text collection belongs.
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
Prosecution Insights