Patent ID: 7814129
Filing Date: 2010-10-12
Classification: G06F,H03M,Y10S

Abstract:
1. A method, comprising: dividing a Binary Large Object (BLOB) into a plurality of subblocks, where the BLOB (b) is divided by partitioning b into a plurality of subblocks, where at least one position k|k+1 in b for which b[k−A+1 . . . k+B] satisfies a predetermined constraint, where A and B are natural numbers; storing the plurality of subblocks in a plurality of clusters, where two or more subblocks are stored in a cluster as a contiguous sequence of bytes with no intervening metadata; creating a representation of the BLOB as one or more spans, where a span refers to a finite sequence of one or more bytes in the cluster, where a span identifies a sequence of contiguous subblocks in a cluster with a length that identifies one or more of, a number of contiguous subblocks and a number of bytes, and where a span comprises one or more of, a skip value x that indicates that the extent of the span is to be reduced by x bytes, and an extension value y that indicates that the extent of the span is to be increased by y bytes; maintaining an index that maps the hash of at least one subblock to the cluster containing the subblock, where only the T'th subblock in a BLOB is indexed, T being a positive integer, and where the index comprises one or more hash tables; and upon determining that a fragmentation threshold has been surpassed, duplicating a contiguous run of one or more subblocks in the store of subblocks.