# US 2011/0225191 A1 · Index searching using a bloom filter

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

- Number: US 2011/0225191 A1
- Document ID: US20110225191A1
- Status: Published application
- Kind: A1
- Application number: 12/661,142
- Filed: 2010-03-10
- Published: 2011-09-15
- Earliest claimed: 2010-03-10
- Assignees: Data Domain, Inc.
- Inventors: Ying Xie
- Web page: https://patentgrep.com/patent/US20110225191A1

## CPC

- G06F 16/328: {Management therefor}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system for index searching comprises a first index, a second index, a processor, and a memory. The processor is configured to determine, using a Bloom filter for the second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index. The processor is further configured to, in the event that the Bloom filter indicates that an entry corresponding to the segment has been previously stored in the second index, retrieve a second index entry associated with the segment that has been previously stored. The memory is coupled to the processor and configured to provide the processor with instructions.

## Claims

### Claim 1

A system for index searching, comprising:
a first index;
a second index;
a processor configured to:
determine, using a Bloom filter for the second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index;
in the event that the Bloom filter indicates that an entry corresponding to the segment has been previously stored in the second index, retrieve a second index entry associated with the segment that has been previously stored; and
a memory coupled to the processor and configured to provide the processor with instructions.

### Claim 2 (depends on 1)

A system as in claim 1, wherein the processor is further configured to receive a request to retrieve the segment.

### Claim 3 (depends on 1)

A system as in claim 1, wherein the processor is further configured to, in the event that an entry corresponding to the segment has not been previously stored in the second index, check the first index to determine whether the segment has been previously stored.

### Claim 4 (depends on 3)

A system as in claim 3, wherein the processor is further configured to, in the event that the first index indicates that an entry corresponding to the segment has been previously stored in the first index, retrieve a first index entry associated with the segment that has been previously stored.

### Claim 5 (depends on 1)

A system as in claim 1, wherein the processor is further configured to check a memory buffer index to determine whether an entry corresponding to the segment has been previously stored in the memory buffer index.

### Claim 6 (depends on 5)

A system as in claim 5, wherein the processor is further configured to, in the event that the memory buffer index indicates that an entry corresponding to the segment has been previously stored, retrieve an index entry from the memory buffer index for the segment.

### Claim 7 (depends on 5)

A system as in claim 5, wherein the memory buffer index includes a fingerprint associated with a stored segment.

### Claim 8 (depends on 5)

A system as in claim 5, wherein the memory buffer index is transferred or merge sorted into the second index.

### Claim 9 (depends on 5)

A system as in claim 5, wherein the memory buffer index is smaller than the second index.

### Claim 10 (depends on 1)

A system as in claim 1, wherein the first index includes a fingerprint associated with a stored segment.

### Claim 11 (depends on 1)

A system as in claim 1, wherein the second index includes a fingerprint associated with a to stored segment.

### Claim 12 (depends on 1)

A system as in claim 1, wherein the second index is smaller in size than the first index.

### Claim 13 (depends on 1)

A system as in claim 1, wherein the second index is transferred or merge sorted into the first index.

### Claim 14 (depends on 1)

A system as in claim 1, wherein the second index is one of a plurality of second indices.

### Claim 15

A method for index searching, comprising:
determining, using a processor and a Bloom filter for a second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index; and
in the event that the Bloom filter indicates that an entry corresponding to the segment has been previously stored in the second index, retrieving a second index entry associated with the segment that has been previously stored.

### Claim 16

A computer program product for index searching, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:
determining, using a processor and a Bloom filter for a second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index; and
in the event that the Bloom filter indicates that an entry corresponding to the segment has been previously stored in the second index, retrieving a second index entry associated with the segment that has been previously stored.