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 .
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 6, 7 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 6 recites “claims
Allowable Subject Matter
Claims 1-5 and 13-19 are allowed.
Reasons for Allowance
The following is a statement of reasons for the indication of allowable subject matter: The following prior art teaches the corresponding elements in claim 1 except the bolded limitations below:
Claim
Prior art Mapping
1. (currently amended) A data processing method, comprising: using a first hash function and a second hash function to encode, each key in key-value data to be stored into a first hash value and a second hash value
Wong, US 11,010,257
Col. 7:27-55 (Examiner finds h1 teaches first hash value and h2 teaches second hash value);
traversing first hash values and second hash values of all keys in the key-value data to be stored,
Wong, US 11,010,257
col. 8:1-10 (Examiner finds “every key” teaches all keys; Examiner finds “compute” teaches traversing);
and determining parameter information of a perfect hash corresponding to the key-value data to be stored
Wong, US 11,010,257
Col. 10:9-26:
It essentially illustrates a method of returning a count to a caller as the index of a value array, as described with reference to examples illustrated in FIGS. 10A and 10B, below. In step 902, the range index of the container IDs is computed as Range_Index=(CID−min_CID)/Range_Size. In step 904, the index of the mapping table to lookup is given by the range index (range_idx) value. The value at range_idx in the mapping table gives the perfect hash bucket index. The process then uses the perfect hash bucket index to get the offset of the perfect hash function and the bitmap for the bucket, block 906. The process then reads the function at the offset specified in the bucket descriptor and applies the function to the key to get a position from the perfect hash function, block 908
wherein the parameter information of the perfect hash comprises: an index of a slot corresponding to each key;
Wong, US 11,010,257
Col. 10:9-26:
It essentially illustrates a method of returning a count to a caller as the index of a value array, as described with reference to examples illustrated in FIGS. 10A and 10B, below. In step 902, the range index of the container IDs is computed as Range_Index=(CID−min_CID)/Range_Size. In step 904, the index of the mapping table to lookup is given by the range index (range_idx) value. The value at range_idx in the mapping table gives the perfect hash bucket index. The process then uses the perfect hash bucket index to get the offset of the perfect hash function and the bitmap for the bucket, block 906. The process then reads the function at the offset specified in the bucket descriptor and applies the function to the key to get a position from the perfect hash function, block 908
(Examiner finds index of a value array teaches a slot);
and for the key-value date to be stored, writing length information of each slot into a head position of the corresponding storage block
CN 113704272 A
Fig. 4;
pp. 7-8
Referring to FIG. 4, showing the digital object state expression diagram based on updating rule, referring to FIG. 4 (a), showing the digital object sequence expression diagram based on the state chain, it should be noted that the construction of the first state chain can be finished on the basic structure of each type of blockchain the node in the first state chain is composed of several state blocks; each state comprises a block head and a block body. wherein the state area block comprises a first state tree storing state information of the digital object; the state block head stores the tree root of the first state tree, the hash pointer of the previous state block and timestamp information. the tree root of the first state tree is the block hash value of the state block, also called the hash value of the state block, putting in the state block head for data verification, and the hash pointer of the pre-sequence state block is used for pointing to the hash value of the last state block; the front and back pointing relation of the hash pointer of the previous state block, so as to form the first state chain in this embodiment according to the state block. wherein the hash (Hash) is a function of mapping the data of any length into fixed length data, the data of the fixed length is the final obtained hash value.
(Examiner finds timestamp suggests date).
according to the index of the slot corresponding to each key, and sequentially writing key-value data in each slot into the corresponding storage block, wherein the number of slots stored in each storage block is determined based on the size of the unit of storage of a storage device:
writing the at least one storage block into the storage device after compressing the at least one storage block
CN 111930751 A page 2
Further, after data writing subtable, according to the set label extracting key, compressing the data according to the timestamp by the extracted key, after compressing, generating the Compress-Block.
recording file offset position information of each block, so as to obtain offset data:
Wong, US 11,010,257
Col. 9:6-13
FIG. 7 illustrates an example memory layout of a memory efficient perfect hash after the perfect hash is created for all the buckets, under some embodiments. As shown in FIG. 7, every bucket 702 is an in-memory data structure that has three types of information. Bucket descriptors 704 comprise the header for perfect hash buckets. The offset of the perfect hash function and the start bit of the bucket in the bitmap is stored in the descriptor.
Col. 11:30-38:
The lookup table is built during the creation of perfect hash function, and contains the count of number of bits set in every 128-bit block in the bitmap. Process 120 also maintain a cumulative count of the number of entries processed until the current bucket in bucket descriptor. Bucket 0 will have a cumulative count of 0 always, since there are no entries processed before bucket 0. For the example above, bucket 1 will have a cumulative count of 9, since first bucket has 9 entries and so on
determining a part of the first hash value or the second hash value of each key to be signature information of the key, so as to obtain signature data,
CN 115269602 A
p. 8
In the embodiment application the invention, the Hash table comprises multiple rows and multiple columns, namely the storage position of the target hash result in the hash table is a certain row, by dividing the hash table according to the form of the column, increasing the hash table, and the structure is easy to be realized in the hardware. Hash result corresponding to each key value in the hash table at least comprises valid bit, signature value (signature) and pointer three parts, wherein the signature value is the second hash result determined in the embodiment of the application. Therefore, in the step 203, according to the first hash result and the second hash result to determine the target key value corresponding to the target hash result in the hash table position, the first hash result and the second hash result are used for determining the target hash result in the hash table direction index, specifically
wherein the writing the at least one storage block into the storage device after compressing the at least one storage block comprises
Wong, US 11,010,257
Col. 7:46-50:
Once the collision free mapping is obtained, the hash functions h1 and h2 are stored in the bucket descriptor and d0 and d1 are stored in a compressed form as d0+d1*phf_range. The algorithm for this process is expressed as follow
generating a data table file based on the at least one compressed storage block, the offset data, the signature data, the parameter information of the perfect hash, and attribute information of a data table:
writing the data table file into a layer Li of a log-structured-merge-tree (LSM-Tree) structure, if a first data file stored in a layer Li reaches a first preset threshold, merging the first data file into a layer Li+1, wherein i is 0 to n, and n is a positive integer greater than 1:
CN 113961514 A
Page 4
For example, in the present disclosure, the simplest two storage structures are used for convenience of
description. As shown in FIG. 1, a storage structure resident in the memory, storing all the recently written
key value pairs, and can be updated at any time, at the same time supporting the inquiry at any time. The
other storage structure is resident in the non-volatile storage device, the non-volatile storage device can be a
hard disk or a disk and so on. LSM tree comprises a multi-layer structure for storing data, the multi-layer
structure can be represented as Level 0 to Level N a plurality of levels, wherein Level N is the last level of
the multi-layer structure.
In the storage system based on the LSM tree, as the data in the memory is continuously written in order, the data range overlaps more and more, the data of the same key is continuously accumulated, so as to cause the reading performance is reduced and the space is expanded. Therefore, the combination (Compaction) mechanism is introduced, by continuously combining or deleting the data, the multi-layer combination mode to optimize the reading performance and space problem
Hereinafter, the Level 0 layer is merged into the Level 1 layer as an example, and the merging process is described. when the data of Level 0 layer reaches the preset threshold value, the Level 0 layer and Level 1 layer are combined, similar to merging and ordering, the process is combined. in the combining process, Level 1 layer in all the Level 0 layer with the key overlapping the file need to participate in the combination. after combining, it will generate new file again. The combined new files will be written in Level 1 layer in order, and the old Level 1 layer of the original file will be replaced. when the data of Level 1 layer reaches the preset threshold value, it will continue to combine with the lower layer (such as Level 2 layer). After the combination is completed, all the old files can be deleted, and only a new file is left. for example, when the data of Level 0 layer reaches the preset threshold value, can select Level 0 layer of one or more files, it is assumed to select Level 0 layer of file 0-1, then in Level 1 layer inquiring the file with the file 0-1 of the file (such as file 1-1 , 1-2), then the file 0-1, file 1-1, file 1-2, to obtain the new file 1-1, 1-2, 1-3, and stored in the Level 1 layer. It can be understood that the file 1-1, 1-2, 1-3 are arranged according to the order of the key. after combining, can delete Level 0 layer of file 0-1, and the original Level 0 layer of the file 1-1, 1-2. then, continuously writing data in Level 0 layer; when the data in Level 0 layer reaches the preset threshold value, repeating said steps. selecting one or more files of Level 0 layer and the file with key overlapping in Level 1 layer to combine, continuously generating new file. The file merging process of other layers also adopts similar principles, which will not be repeated here.
wherein the merging the first data file into the layer Li+1 comprises: if the layer Li+1 does not store any data, directly writing the first data file into the layer Li+1;
CN 113961514 A
Page 4
In the storage system based on the LSM tree, as the data in the memory is continuously written in order, the data range overlaps more and more, the data of the same key is continuously accumulated, so as to cause the reading performance is reduced and the space is expanded. Therefore, the combination (Compaction) mechanism is introduced, by continuously combining or deleting the data, the multi-layer combination mode to optimize the reading performance and space problem
Hereinafter, the Level 0 layer is merged into the Level 1 layer as an example, and the merging process is described. when the data of Level 0 layer reaches the preset threshold value, the Level 0 layer and Level 1 layer are combined, similar to merging and ordering, the process is combined. in the combining process, Level 1 layer in all the Level 0 layer with the key overlapping the file need to participate in the combination. after combining, it will generate new file again. The combined new files will be written in Level 1 layer in order, and the old Level 1 layer of the original file will be replaced. when the data of Level 1 layer reaches the preset threshold value, it will continue to combine with the lower layer (such as Level 2 layer). After the combination is completed, all the old files can be deleted, and only a new file is left. for example, when the data of Level 0 layer reaches the preset threshold value, can select Level 0 layer of one or more files, it is assumed to select Level 0 layer of file 0-1, then in Level 1 layer inquiring the file with the file 0-1 of the file (such as file 1-1 , 1-2), then the file 0-1, file 1-1, file 1-2, to obtain the new file 1-1, 1-2, 1-3, and stored in the Level 1 layer. It can be understood that the file 1-1, 1-2, 1-3 are arranged according to the order of the key. after combining, can delete Level 0 layer of file 0-1, and the original Level 0 layer of the file 1-1, 1-2. then, continuously writing data in Level 0 layer; when the data in Level 0 layer reaches the preset threshold value, repeating said steps. selecting one or more files of Level 0 layer and the file with key overlapping in Level 1 layer to combine, continuously generating new file. The file merging process of other layers also adopts similar principles, which will not be repeated here.
(Examiner finds preset threshold value includes 0 or no data)
if the layer Li+1 has stored a second data file, respectively dividing the first data file and the second data file into S data segments according to hash values of keys, and performing the following operations for a jth data segment of the first data file and a jth data segment of the second data file:
acquiring a first hash value and a second hash value of all keys in the two jth data segments
determining an index of a slot corresponding to each key according to the first hash value and the second hash value of the key:
and determining a corresponding operation according to the key-value data in each slot,
wherein S is a preset value greater than 1, and j is 1 to S.
The above analysis also applies to claim 18.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ALBERT M PHILLIPS, III whose telephone number is (571)270-3256. The examiner can normally be reached 10a-6:30pm EST M-F.
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, Ann J Lo can be reached at (571) 272-9767. 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.
/ALBERT M PHILLIPS, III/Primary Examiner, Art Unit 2159
