US5990810A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for partitioning a block of data into subblocks and for storing and communcating such subblocks
Assignee: Rocksoft Ltd
•
Filing: 1996-02-15
•
Granted: 1999-11-23
•
Expires: 2016-02-15
Abstract
Abstract PCT No. PCT/AU96/00081 Sec. 371 Date Aug. 15, 1997 Sec. 102(e) Date Aug. 15, 1997 PCT Filed Feb. 15, 1996 PCT Pub. No. WO96/25801 PCT Pub. Date Aug. 22, 1996This invention provides a method and apparatus for detecting common spans within one or more data blocks by partitioning the blocks (FIG. 4) into subblocks and searching the group of subblocks (FIG. 12) (or their corresponding hashes (FIG. 13)) for duplicates. Blocks can be partitioned into subblocks using a variety of methods, including methods that place subblock boundaries at fixed positions (FIG. 3), methods that place subblock boundaries at data-dependent positions (FIG. 3), and methods that yield multiple overlapping subblocks (FIG. 6). By comparing the hashes of subblocks, common spans of one or more blocks can be identified without ever having to compare the blocks or subblocks themselves (FIG. 13). This leads to several applications including an incremental backup system that backs up changes rather than changed files (FIG. 25), a utility that determines the similarities and differences between two files (FIG. 13), a file system that stores each unique subblock at most once (FIG. 26), and a communications system that eliminates the need to transmit subblocks already possessed by the receiver (FIG. 19).
Inventors
- 👤 Ross Neil Williams
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 22:19
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; G; G06; G06F; G06F16/00; G06F16/10; G06F16/13; G06F16/137; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0608; G06F3/0628; G06F3/0638; G06F3/064; G06F3/0641; G06F3/0668; G06F3/0671; G06F7/00; G06F7/02
Claims Analysis
Total Claims: 49
Claim 1
Independent Claim
56 words
A method for organizing a block b of digital data for storage, communication, or comparison, comprising the step of: partitioning said block b into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers.
Claim 2
Independent Claim
56 words
A method for organizing a block b of digital data for storage, communication, or comparison, comprising the step of: partitioning said block b into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers.
Claim 3
Dependent Claim
22 words
The method of claim 1, wherein the constraint comprises the hash of at least a portion of b[k-A+1 . . . k+B].
Claim 4
Dependent Claim
55 words
The method of claim 1, further comprising the step of: locating the nearest subblock boundary on a side of a position p|p+1 within said block, said locating step comprising the step of: evaluating whether said predetermined constraint is satisfied at each position k|k+1 for increasing or decreasing k, wherein k starts with the value p.
Claim 5
Dependent Claim
24 words
The method of claim 1, wherein at least one bound is imposed on the size of at least one of said plurality of subblocks.
Claim 6
Dependent Claim
17 words
The method of claim 1, wherein additional subblocks are formed from at least one group of subblocks.
Claim 7
Dependent Claim
21 words
The method of claim 1, wherein an additional hierarchy of subblocks is formed from at least one group of contiguous subblocks.
Claim 8
Dependent Claim
24 words
The method of claim 1, further comprising the step of: calculating the hash of each of at least one of said plurality of subblocks.
Claim 9
Dependent Claim
42 words
The method of claim 1, further comprising the step of: forming a projection of said block, being an ordered or unordered collection of elements, wherein each element consists of a subblock, an identity of a subblock, or a reference of a subblock.
Claim 10
Dependent Claim
17 words
The method of claim 1, wherein said subblocks are compared by comparing the hashes of said subblocks.
Claim 11
Dependent Claim
44 words
The method of claim 1, wherein subsets of identical subblocks within a group of one or more subblocks are found by inserting each subblock, an identity of each subblock, a reference of each subblock, or a hash of each subblock into a data structure.
Claim 12
Independent Claim
108 words
A method for comparing one or more blocks, comprising the steps of: organizing a block b of digital data for the purpose of comparison, comprising the step of: partitioning said block b into a plurality of subblocks at at least one position k|k+1 within said block; for which b[k-A+1 . . . k+B] satisfies a predetermined constraint; and wherein A and B are natural numbers, forming a projection of each said block, being a collection of elements, wherein each element comprises a selected one of a subblock, an identity of a subblock, and a reference of a subblock, and comparing the elements of said projections of said blocks.
Claim 13
Independent Claim
108 words
A method for comparing one or more blocks, comprising the steps of: organizing a block b of digital data for the purpose of comparison, comprising the step of: partitioning said block b into a plurality of subblocks at at least one position k|k+1 within said block; for which b[k-A+1 . . . k+B] satisfies a predetermined constraint; and wherein A and B are natural numbers, forming a projection of each said block, being a collection of elements, wherein each element comprises a selected one of a subblock, an identity of a subblock, and a reference of a subblock, and comparing the elements of said projections of said blocks.
Claim 14
Independent Claim
104 words
A method for representing one or more blocks comprising a collection of subblocks and block representatives which are mapped to lists of entries which identify subblocks; said method comprising the step of modifying one of said blocks including the steps of: partitioning said block into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, adding to said collection of subblocks zero or more subblocks which are not already in said collection, and updating said subblock list associated with said modified block.
Claim 15
Independent Claim
104 words
A method for representing one or more blocks comprising a collection of subblocks and block representatives which are mapped to lists of entries which identify subblocks; said method comprising the step of modifying one of said blocks including the steps of: partitioning said block into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, adding to said collection of subblocks zero or more subblocks which are not already in said collection, and updating said subblock list associated with said modified block.
Claim 16
Independent Claim
97 words
A method for representing one or more blocks comprising a collection of subblocks and block representatives which are mapped to lists of entries which identify subblocks; said method comprising the step of modifying one of said blocks including the steps of: partitioning said block into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, removing from said collection of subblocks zero or more subblocks, and updating said subblock list associated with said modified block.
Claim 17
Independent Claim
97 words
A method for representing one or more blocks comprising a collection of subblocks and block representatives which are mapped to lists of entries which identify subblocks; said method comprising the step of modifying one of said blocks including the steps of: partitioning said block into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, removing from said collection of subblocks zero or more subblocks, and updating said subblock list associated with said modified block.
Claim 18
Independent Claim
114 words
A method for representing one or more blocks comprising a collection of subblocks and block representatives which are mapped to lists of entries which identify subblocks; said method comprising the step of modifying one of said blocks including the steps of: partitioning said block into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, adding to said collection of subblocks zero or more subblocks that are not already in the collection, removing from said collection of subblocks zero or more subblocks, and updating said subblock list associated with said modified block.
Claim 19
Independent Claim
114 words
A method for representing one or more blocks comprising a collection of subblocks and block representatives which are mapped to lists of entries which identify subblocks; said method comprising the step of modifying one of said blocks including the steps of: partitioning said block into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, adding to said collection of subblocks zero or more subblocks that are not already in the collection, removing from said collection of subblocks zero or more subblocks, and updating said subblock list associated with said modified block.
Claim 20
Independent Claim
119 words
A method for an entity E1 to communicate a block X to E2 where E1 possesses the knowledge that E2 possesses a group of Y subblocks Y 1 . . . Y m , comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E1 to E2 the contents of zero or more subblocks in X 1 and the remaining subblocks as references to subblocks in Y 1 . . . Y m , and to subblocks transmitted.
Claim 21
Independent Claim
119 words
A method for an entity E1 to communicate a block X to E2 where E1 possesses the knowledge that E2 possesses a group of Y subblocks Y 1 . . . Y m , comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E1 to E2 the contents of zero or more subblocks in X 1 and the remaining subblocks as references to subblocks in Y 1 . . . Y m , and to subblocks transmitted.
Claim 22
Independent Claim
116 words
A method for an entity E1 to communicate one or more subblocks of a group X of subblocks X 1 . . . X n to E2 where E1 possesses the knowledge that E2 possesses a block Y, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E1 to E2 the contents of zero or more subblocks in X, and the remaining subblocks as references to subblocks in Y, and to subblocks already transmitted.
Claim 23
Independent Claim
116 words
A method for an entity E1 to communicate one or more subblocks of a group X of subblocks X 1 . . . X n to E2 where E1 possesses the knowledge that E2 possesses a block Y, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E1 to E2 the contents of zero or more subblocks in X, and the remaining subblocks as references to subblocks in Y, and to subblocks already transmitted.
Claim 24
Independent Claim
146 words
A method for an entity E1 to communicate a block X to E2 where E1 possesses the knowledge that E2 possesses a block Y, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E1 to E2 the contents of zero or more subblocks in X, and the remaining subblocks as references to subblocks in Y, and to subblocks already transmitted.
Claim 25
Independent Claim
146 words
A method for an entity E1 to communicate a block X to E2 where E1 possesses the knowledge that E2 possesses a block Y, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E1 to E2 the contents of zero or more subblocks in X, and the remaining subblocks as references to subblocks in Y, and to subblocks already transmitted.
Claim 26
Independent Claim
118 words
A method for constructing a block D from a block X and a group Y of subblocks Y 1 . . . Y m such that X can be constructed from Y and D, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more subblocks in X, references to zero or more subblocks in Y, and references to zero or more subblocks in D.
Claim 27
Independent Claim
118 words
A method for constructing a block D from a block X and a group Y of subblocks Y 1 . . . Y m such that X can be constructed from Y and D, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more subblocks in X, references to zero or more subblocks in Y, and references to zero or more subblocks in D.
Claim 28
Independent Claim
118 words
A method for constructing a block D from a group X of subblocks X 1 . . . X n and a block Y such that X can be constructed from Y and D, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more subblocks in X, references to zero or more subblocks in Y, and references to zero of more subblocks in D.
Claim 29
Independent Claim
118 words
A method for constructing a block D from a group X of subblocks X 1 . . . X n and a block Y such that X can be constructed from Y and D, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more subblocks in X, references to zero or more subblocks in Y, and references to zero of more subblocks in D.
Claim 30
Independent Claim
152 words
A method for constructing a block D from a block X and a block Y such that X can be constructed from Y and D, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more in X, references to zero or more subblocks in Y, and references to zero or more subblocks in D.
Claim 31
Independent Claim
152 words
A method for constructing a block D from a block X and a block Y such that X can be constructed from Y and D, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more in X, references to zero or more subblocks in Y, and references to zero or more subblocks in D.
Claim 32
Independent Claim
138 words
A method for constructing a block D from a block X and a projection Y said projection comprising a collection of elements wherein said elements comprises a subblock in Y, an identity of a subblock in Y, or a reference of a subblock in Y, such that X can be constructed from Y and D, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more in X, references to zero or more subblocks in Y, and references to zero or more subblocks in D.
Claim 33
Independent Claim
138 words
A method for constructing a block D from a block X and a projection Y said projection comprising a collection of elements wherein said elements comprises a subblock in Y, an identity of a subblock in Y, or a reference of a subblock in Y, such that X can be constructed from Y and D, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing D from a selected at least one of: the contents of zero or more in X, references to zero or more subblocks in Y, and references to zero or more subblocks in D.
Claim 34
Independent Claim
103 words
A method for constructing a block X from a block Y and a block D, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing X from D and Y by constructing the subblocks of X based on a selected at least one of: subblocks contained within D, references in D to subblocks in Y, and references to D to subblocks in D.
Claim 35
Independent Claim
103 words
A method for constructing a block X from a block Y and a block D, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing X from D and Y by constructing the subblocks of X based on a selected at least one of: subblocks contained within D, references in D to subblocks in Y, and references to D to subblocks in D.
Claim 36
Independent Claim
112 words
A method for constructing a group X of subblocks X 1 . . . X n from a block Y and a block D, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+b] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing X 1 . . . X n from D and Y based on a selected at least one of: subblocks contained within D, references in D to subblocks in Y, and references to D to subblocks in D.
Claim 37
Independent Claim
112 words
A method for constructing a group X of subblocks X 1 . . . X n from a block Y and a block D, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+b] satisfies a predetermined constraint, and wherein A and B are natural numbers, and constructing X 1 . . . X n from D and Y based on a selected at least one of: subblocks contained within D, references in D to subblocks in Y, and references to D to subblocks in D.
Claim 38
Independent Claim
108 words
A method for communicating a data block X from one entity E1 to another entity E2, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, transmitting from E1 to E2 an identity of at least one subblock, transmitting from E2 to E1 information communicating the presence or absence of subblocks at E2, and transmitting from E1 to E2 at least the subblocks identified as not being present at E2.
Claim 39
Independent Claim
108 words
A method for communicating a data block X from one entity E1 to another entity E2, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, transmitting from E1 to E2 an identity of at least one subblock, transmitting from E2 to E1 information communicating the presence or absence of subblocks at E2, and transmitting from E1 to E2 at least the subblocks identified as not being present at E2.
Claim 40
Independent Claim
128 words
A method for communicating a block X from one entity E1 to another entity E2, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, transmitting from E2 to E1 information communicating the presence or absence at E2 of members of a group Y of subblocks Y 1 . . . Y m , and transmitting from E1 to E2 the contents of zero or more subblocks in X, and the remaining subblocks as references to subblocks in Y 1 . . . Y m and to subblocks already transmitted.
Claim 41
Independent Claim
128 words
A method for communicating a block X from one entity E1 to another entity E2, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, transmitting from E2 to E1 information communicating the presence or absence at E2 of members of a group Y of subblocks Y 1 . . . Y m , and transmitting from E1 to E2 the contents of zero or more subblocks in X, and the remaining subblocks as references to subblocks in Y 1 . . . Y m and to subblocks already transmitted.
Claim 42
Independent Claim
86 words
A method for an entity E2 to communicate to an entity E1 the fact that E2 possesses a block Y, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E2 to E1 references of the subblocks Y 1 . . . Y m .
Claim 43
Independent Claim
86 words
A method for an entity E2 to communicate to an entity E1 the fact that E2 possesses a block Y, comprising the steps of: partitioning said block Y into a plurality of subblocks Y 1 . . . Y m at at least one position k|k+1 within said block, for which Y[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, and transmitting from E2 to E1 references of the subblocks Y 1 . . . Y m .
Claim 44
Independent Claim
82 words
A method for an entity E1 to communicate a subblock X 1 to an entity E2, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, transmitting from E2 to E1 an identity of X i , transmitting X i from E1 to E2.
Claim 45
Independent Claim
82 words
A method for an entity E1 to communicate a subblock X 1 to an entity E2, comprising the steps of: partitioning said block X into a plurality of subblocks X 1 . . . X n at at least one position k|k+1 within said block, for which X[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers, transmitting from E2 to E1 an identity of X i , transmitting X i from E1 to E2.
Claim 46
Independent Claim
55 words
An apparatus for organizing a block b of digital data for storage, communication, or comparison, comprising means for partitioning said block b into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers.
Claim 47
Independent Claim
55 words
An apparatus for organizing a block b of digital data for storage, communication, or comparison, comprising means for partitioning said block b into a plurality of subblocks at at least one position k|k+1 within said block, for which b[k-A+1 . . . k+B] satisfies a predetermined constraint, and wherein A and B are natural numbers.
Claim 48
Dependent Claim
22 words
The apparatus of claim 28, in which the constraint comprises the hash of some or all of b[k-A+1 . . . k+B].
Claim 49
Dependent Claim
54 words
The apparatus of claim 28, further comprising means for locating the nearest subblock boundary on a side of a position p|p+1 within said block, said means for locating comprising: means for evaluating whether said predetermined constraint is satisfied at each position k|k+1 for increasing or decreasing k, wherein k starts with the value p.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-22 | 2003-05-24 | 2003-11-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-22 | 2007-05-24 | 2007-11-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-22 | 2011-05-24 | 2011-11-23 | $7700.00 | Window Closed / Lapsed |