Patent ID: 8108348
Filing Date: 2012-01-31
Classification: G06F

Abstract:
1. A multi-version control method for data documents, the method comprising steps of: A. generating data-block fingerprints for all data blocks of a benchmark version; and B. determining common data contents between a newer version and the benchmark version according to the data-block fingerprints; and indexing the common data contents with an index containing a length of the common data contents and locations of the common data contents between the benchmark version and the newer version; based on these indexes, determining particular data contents which are contained in the newer version but not contained in the benchmark version; the step B comprising: B1. starting from the beginning position of the newer version, generating the data-block fingerprint for the fixed-length data block; B2. performing a binary search on the rearranged data-block fingerprints of the benchmark version; determining whether the data-block fingerprint of the newer version appears in the rearranged data-block fingerprints of the benchmark version or not; if yes, proceeding to step B3; otherwise, proceeding to step B6; B3. determining whether the contents of the data block of the newer version are identical to contents of a corresponding data block of the benchmark version or not; if yes, proceeding to step B4; otherwise, proceeding to step B6; B4. expanding and comparing the identical data contents for the data block of the newer version and the data contents of the data block in the benchmark version; terminating the expanding and comparing when related data contents are distinct; indexing the common data contents; and proceeding to step B5; B5. determining whether the last data block of the newer version has been traversed or not; if yes, indexing the data contents peculiar to the newer version and terminating a current process; otherwise, generating a data-block fingerprint for the data block starting at a beginning position of the newer version which has not been traversed, and then returning to step B2; and B6. determining whether the last data block in the newer version has been traversed or not; if yes, indexing the data contents peculiar to the newer version and terminating the current process; otherwise, in the newer version, shifting the current data block forward by pre-set bytes to obtain another data block of fixed length, and generating a data-block fingerprint for the newer data block, and then returning to step B2, wherein the step A comprises: starting from a beginning position of the benchmark version, partitioning each data block into some fixed-length sub-blocks, the length of each sub-block is equal to a length of the data-block fingerprint; performing an exclusive-OR (XOR) operation on data contents of the sub-blocks, and a result of XOR is used as the data-block fingerprint; and wherein the step A comprises: rearranging the data-block fingerprints for all data blocks in the benchmark version by heap sort; and among the rearranged data-block fingerprints, only preserving all the data-block fingerprints that appears no more than a predetermined number.