Method and apparatus for window matching in delta compressors
AssigneeAT&T Corp.
InventorsBinh Dao Vo, Kiem-Phong Vo
Life of this patent
Estimating the term…
Abstract
The present invention significantly improves the performance of matching target file window partitions to source file window partitions in delta compression. In particular, the present invention enhances delta compression performance of delta compressors based on the idea of modeling a dataset with the frequencies of its n-grams and employs a method to compute good source and target window matching in linear time.
Claims9
A method for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, said method comprising:
- partitioning the source file into a plurality of source file windows;
- partitioning the target file into a plurality of target file windows;
- and
- matching one of said plurality of source file windows with one of said target file windows based upon a distance function, wherein said distance function is as follows:
- Δ
-
- (
- S
- 1
- ,
- S
- 2
- )
- =
- ∑
- i
- =
- 0
- A
- -
- 1
-
-
- F
- S
- 1
-
- [
- i
- ]
- -
- F
- S
- 2
-
- [
- i
- ]
-
- ∑
- i
- =
- 0
- A
- -
- 1
-
- max
-
- (
- F
- S
- 1
-
- [
- i
- ]
- ,
- F
- S
- 2
-
- [
- i
- ]
- )
- where,
- Δ(S1, S2) is computed and stored as the distance function between two non-empty data segments, S1 and S2, as a measure of similarity between the two data segments, where A comprises a size of an n-gram frequency array, and
- FS1 and FS2 are corresponding n-gram frequency arrays for data segments S1 and S2 respectively.
A method for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, said method comprising:
- partitioning the source file into a plurality of source file windows;
- partitioning the target file into a plurality of target file windows;
- matching one of said plurality of source file windows with one of said target file windows based upon a distance function;
- and
- performing a fast search for matching source windows, wherein said fast search comprises a computation of a signature distance function based on a signature function σ:
- δ
-
- (
- P
- 1
- ,
- P
- 2
- )
- =
-
- σ
-
- (
- P
- 1
- )
- -
- σ
-
- (
- P
- 2
- )
-
- max
-
- (
- σ
-
- (
- P
- 1
- )
- ,
- σ
-
- (
- P
- 2
- )
- )
- where P1 and P2 represent two data segments, wherein said signature function σ comprises a sum of hash values off all n-grams, wherein a result of said performing said fast search is stored.
A method for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, said method comprising:
- partitioning the source file into a plurality of source file windows;
- partitioning the target file into a plurality of target file windows;
- matching one of said plurality of source file windows with one of said target file windows based upon a distance function as a measure of similarity between two data segments;
- and
- performing a fast search for matching source windows, wherein said fast search comprises:
- a) partitioning a source file S into a sequence of segments each of a fixed size represented by λ;
- b) partitioning a target window T into a sequence of segments each of a fixed size represented by λ;
- c) computing and storing a set of all Si's such that j<=i<=a-b and δ(Si, Ti)<=ε and asserting that Tj votes for each such position (i-j)λ as a candidate for a match for each segment Tj in T, wherein said i denotes a location and said i is a non-negative integer location:, wherein said Si denotes a segment of said sequence of segments in said source file starting at said non-negative integer location i, wherein said Ti denotes a segment of said sequence of segments in said target window starting at said location I, wherein said ε denotes a constant value, wherein a denotes a highest number of said sequence of segments in said source file, and wherein b denotes a highest number of said sequence of segments in said target window;
- wherein epsilon, ε is a predetermined non-null numerical value;
- and
- d) taking top k candidate positions and applying to a small neighborhood of them to find a best match to T.
A computer-readable storage medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, comprising of:
- partitioning the source file into a plurality of source file windows;
- partitioning the target file into a plurality of target file windows;
- and
- matching one of said plurality of source file windows with one of said target file windows based upon a distance function, wherein said distance function is as follows:
- Δ
-
- (
- S
- 1
- ,
- S
- 2
- )
- =
- ∑
- i
- =
- 0
- A
- -
- 1
-
-
- F
- S
- 1
-
- [
- i
- ]
- -
- F
- S
- 2
-
- [
- i
- ]
-
- ∑
- i
- =
- 0
- A
- -
- 1
-
- max
-
- (
- F
- S
- 1
-
- [
- i
- ]
- ,
- F
- S
- 2
-
- [
- i
- ]
- )
- where,
- Δ(S1, S2) is computed and stored as the distance function between two non-empty data segments, S1 and S2, as a measure of similarity between the two data segments, where A comprises a size of an n-gram frequency array, wherein said i denotes a non-negative location and
- FS1 and FS2 are corresponding n-gram frequency arrays for data segments S1 and S2 respectively.
A computer-readable storage medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, comprising of:
- partitioning the source file into a plurality of source file windows;
- partitioning the target file into a plurality of target file windows;
- matching one of said plurality of source file windows with one of said target file windows based upon a distance function as a measure of similarity between two data segments;
- and
- performing a fast search for matching source windows, wherein said fast search comprises a computation of a signature distance function based on a signature function σ:
- δ
-
- (
- P
- 1
- ,
- P
- 2
- )
- =
-
- σ
-
- (
- P
- 1
- )
- -
- σ
-
- (
- P
- 2
- )
-
- max
-
- (
- σ
-
- (
- P
- 1
- )
- ,
- σ
-
- (
- P
- 2
- )
- )
- where P1 and P2 represent two data segments, wherein said signature function σ comprises a sum of hash values off all n-grams, wherein a result of said performing said fast search is stored.
A computer-readable storage medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, comprising of:
- partitioning the source file into a plurality of source file windows;
- partitioning the target file into a plurality of target file windows;
- matching one of said plurality of source file windows with one of said target file windows based upon a distance function;
- and
- performing a fast search for matching source windows, wherein said fast search comprises:
- a) partitioning a source file S into a sequence of segments each of a fixed size represented by λ;
- b) partitioning a target window T into a sequence of segments each of a fixed size represented by λ;
- c) computing and storing a set of all Si's such that j<=i<=a-b and δ(Si, Ti)<=ε and asserting that Tj votes for each such position (i-j)λ as a candidate for a match for each segment Tj in T, wherein said j denotes a location and wherein said i is a non-negative integer location, wherein said Si denotes a segment of said sequence of segments in said source file starting at said non-negative integer location i, wherein said Ti denotes a segment of said sequence of segments in said target window starting at said location I, wherein said ε denotes a predetermined non-null numerical value, wherein a denotes a highest number of said sequence of segments in said source file, and wherein b denotes a highest number of said sequence of segments in said target window;
- and
- d) taking top k candidate positions and applying to a small neighborhood of them to find a best match to T.
An apparatus for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, comprising:
- means for partitioning the source file into a plurality of source file windows;
- means for partitioning the target file into a plurality of target file windows;
- and
- means for matching one of said plurality of source file windows with one of said target file windows based upon a distance function, wherein said distance function is as follows:
- Δ
-
- (
- S
- 1
- ,
- S
- 2
- )
- =
- ∑
- i
- =
- 0
- A
- -
- 1
-
-
- F
- S
- 1
-
- [
- i
- ]
- -
- F
- S
- 2
-
- [
- i
- ]
-
- ∑
- i
- =
- 0
- A
- -
- 1
-
- max
-
- (
- F
- S
- 1
-
- [
- i
- ]
- ,
- F
- S
- 2
-
- [
- i
- ]
- )
- where,
- Δ(S1, S2) is computed and stored as the distance function between two non-empty data segments, S1 and S2, as a measure of similarity between the two data segments, where A comprises a size of an n-gram frequency array, wherein said i is a non-negative integer location;
- and
- FS1 and FS2 are corresponding n-gram frequency arrays for data segments S1 and S2 respectively.
Dependencies are inferred from the claim text.