# US 2012/0254559 A1 · Method and Apparatus For Detecting The Presence of Subblocks in a Reduced Redundancy Storing System

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254559 A1
- Document ID: US20120254559A1
- Status: Published application
- Kind: A1
- Application number: 13/486,408
- Filed: 2012-06-01
- Published: 2012-10-04
- Earliest claimed: 2005-03-11
- Inventors: Ross Neil WILLIAMS
- Web page: https://patentgrep.com/patent/US20120254559A1

## CPC

- G06F 16/1744: {using compression, e.g. sparse files}
- G06F 16/137: {Hash-based (content-based indexing of textual data G06F16/31)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

This application concerns determining whether a particular subblock of data is present in a reduced-redundancy storage system. One embodiment achieves this by hashing subblocks in the storage system into a bitfilter that contains ‘1’ bit for each position to which at least one subblock hashes. This bitfilter provides a fast way to determine whether a subblock is in the storage system. In another embodiment, index entries for new subblocks may be buffered in a subblock index write buffer to convert a large number of random access read and write operations into a single sequential read and a single sequential write operation. The combination of the bitfilter and the write buffer yields a reduced-redundancy storage system that uses significantly less high speed random access memory than other systems that store the entire subblock index in memory.

## Claims

### Claim 1

A method for representing, in a lossy manner, the existence of subblocks residing in a storage system, the method including the step of,
creating an array of bits (bitfilter) using a function that maps a subblock to a position in the bitfilter, where each bit in the bitfilter is a predetermined bit value if at least one subblock in the storage system maps to the bit's position.

### Claim 2 (depends on 1)

The method of claim 1 wherein the function is a hash function.

### Claim 3 (depends on 1)

The method of claim 1 wherein the function is calculated using a first calculation being a cryptographic hash function whose result is input into a second calculation.

### Claim 4 (depends on 1)

The method of claim 1 wherein the function is calculated using a first calculation being a non-cryptographic hash function whose result is input into a second calculation.

### Claim 5 (depends on 3)

The method of claim 3 wherein the second calculation is a modulo K operation, where K is the number of bits in the bitfilter.

### Claim 6 (depends on 1)

The method of claim 1 wherein the number of bits in the bitfilter is a power of 2.

### Claim 7 (depends on 1)

The method of claim 1 wherein there is a plurality of functions, each of which maps a subblock to a position in the bitfilter, and where each bit in the bitfilter is said predetermined bit value if and only if at least one subblock/function combination maps to the bit's position.

### Claim 8 (depends on 1)

The method of claim 1 wherein the bitfilter is divided into one or more sections.

### Claim 9 (depends on 8)

The method of claim 8 wherein each of one or more sections is compressed by applying a compression method.

### Claim 10 (depends on 9)

The method of claim 9 wherein the compression method is a Tanaka/Leon-Garcia mode-m code.

### Claim 11 (depends on 9)

The method of claim 9 wherein the compression method is run-length encoding.

### Claim 12 (depends on 9)

The method of claim 9 wherein the compression method is arithmetic coding.

### Claim 13 (depends on 7)

The method of claim 7 wherein the bitfilter is divided into one or more sections.

### Claim 14 (depends on 13)

The method of claim 13 wherein each of one or more sections is compressed by applying a compression method.

### Claim 15 (depends on 14)

The method of claim 14 wherein the compression method is a Tanaka/Leon-Garcia mode-m code.

### Claim 16 (depends on 14)

The method of claim 14 wherein the compression method is run-length encoding.

### Claim 17 (depends on 14)

The method of claim 14 wherein the compression method is arithmetic coding.

### Claim 18 (depends on 1)

The method of claim 1 including the further step of:
creating an index of subblocks containing index entries that map a subblock or a subblock hash to a location in the subblock storage system; and
creating one or more index entry write buffers for holding newly created subblock index entries;
wherein the content of an index entry write buffer is written to the subblock index from time to time.

### Claim 19 (depends on 18)

The method in claim 18 wherein the index resides on disk and the index entry buffer resides in memory.

### Claim 20 (depends on 19)

The method in claim 19 wherein when the index entry write buffer becomes full to a predetermined level, the index is read into memory, and the elements in the index entry write buffer are added to it and the modified index is then written to disk.

### Claim 21 (depends on 1)

The method of claim 1 wherein the set of all possible subblocks is partitioned into a plurality of mutually exclusive spaces and a separate bitfilter is used to represent the presence or absence of actual subblocks in the storage system that fall within each space.

### Claim 22 (depends on 21)

The method of claim 21 wherein the partitioning of the subblock space is performed by hashing subblocks and splitting the space of subblock hashes using a digital search tree.

### Claim 23 (depends on 21)

The method of claim 21 wherein the index entry buffer is correspondingly divided.

### Claim 24 (depends on 18)

The method of claim 18 wherein the bitfilter is in memory.

### Claim 25 (depends on 1)

A method for determining whether a subblock z is absent in a storage system by applying the function of claim 1 to the subblock z and testing the value of the corresponding bit of the bitfilter, the bitfilter having been created in accordance with the method of claim 1.

### Claim 26 (depends on 7)

A method for determining whether a subblock z is absent in a storage system by applying each of the functions of claim 7 to the subblock z and testing the value of the corresponding bits of a bitfilter created in accordance with the method of claim 7, wherein the subblock is absent if all tested bits of the bitfilter are a further predetermined bit value.

### Claim 27 (depends on 25)

A method for determining, within a sequence of subblocks, the non-existence of contiguous runs of at least T present subblocks at various positions in the sequence, by using the method of claim 25 to test each subblock in the sequence for its definite absence.

### Claim 28 (depends on 19)

A method for storing a BLOB of data in a storage, communication or comparison system using the method of claim 19, comprising of the further steps of:
dividing the BLOB into subblocks using a partitioning method; and
using the bitfilter to determine whether each subblock is absent from the storage system; and if a subblock is absent, setting to a predetermined bit value the bit in the array of bits corresponding to the subblock, and adding an entry for the subblock to the index entry buffer.

### Claim 29

A data processing apparatus for representing, in a lossy manner, the existence of subblocks residing in a storage system; comprising of:
a memory data storage, and
data processing means for creating an array of bits (bitfilter) in memory using a function that maps a subblock to a position in the bitfilter, where each bit in the bitfilter is a predetermined bit value if and only if at least one subblock in the storage system maps to the bit's position.

### Claim 30 (depends on 29)

A data processing apparatus for storing one or more BLOBs of data using the apparatus according to claim 29, the apparatus further comprising of:
a disk data storage, wherein
the data processing means divides each BLOB into subblocks using a partitioning method, and creates an index of subblocks on the disk containing index entries that map a subblock or a subblock hash to a location in the storage system, and wherein the memory data storage has one or more index entry write buffers for holding newly created subblock index entries, the data processing means uses the bitfilter to determine whether each subblock is absent from the storage system and if a subblock is absent, setting to said predetermined bit value the corresponding bit in the array of bits in the bitfilter, and adding an entry for the subblock to an index entry buffer and wherein the content of an index entry write buffer in memory is written to the subblock index on disk from time to time.

### Claim 31

A computer readable memory, encoded with data representing a computer program that can be used to direct a programmable device for representing, in a lossy manner, the existence of subblocks residing in a storage system, using a processing means for operating the computer readable memory to create an array of bits (bitfilter) using a function that maps a subblock to a position in the bitfilter, where each bit in bitfilter is a predetermined bit value if and only if at least one subblock in the storage system maps to the bit's position.

### Claim 32

A computer program element comprising a computer program code means for representing, in a lossy manner, the existence of subblocks residing in a storage system, to make a programmable device execute:
a first function of creating an array of bits (bitfilter) using a function that maps a subblock to a position in the bitfilter, where each bit in the bitfilter is a predetermined bit value if and only if at least one subblock in the storage system maps to the bit's position.

### Claim 33 (depends on 4)

The method of claim 4 wherein the second calculation is a modulo K operation, where K is the number of bits in the bitfilter.

### Claim 34 (depends on 18)

The method of claim 18 wherein the index entry buffer is correspondingly divided.
