Patent ID: 8255406

Claim:
A data management device using a multi-stage Bloom filter comprising: a storage unit that includes a number of data blocks and stores data on at least one of the data blocks; a hash generation unit that generates a hash value of the data; a memory that includes the multi-stage Bloom filter, wherein the multi-stage Bloom filter is a data structure that is used to test whether a particular entry belongs to an existing set efficiently, a first stage of the multi-stage Bloom filter being divided into filter parts of which size is equivalent to the number of the data blocks, and a p th stage (p is an integer equal to or larger than 2) being divided into filter parts of which size is a combination of filter parts of a (p−1) th stage; a registration unit that registers an entry of the data in each stage of the multi-stage Bloom filter by using the hash value of the data; and a search unit that determines whether an entry of data being searched is registered in each filter part of the multi-stage Bloom filter by using a hash value of the data being searched generated by the hash generation unit; wherein the registration unit registers the entry of the data in a filter part of the multi-stage Bloom filter at the first stage corresponding to a data block where the data is stored, and registers the entry of the data in a filter part of the multi-stage Bloom filter at the p th stage corresponding to the filter part of the multi-stage Bloom filter at the first stage in which the entry of the data is registered, and the search unit determines which filter part of the multi-stage Bloom filter at the first stage the entry of the data being searched is registered in by narrowing down filter parts from a start stage to an end stage of the multi-stage Bloom filter, wherein a stage number of the start stage being larger than a stage number of the end stage.