Patent Document ID: 20120310960
Application ID: 13461176
Patent Status: 0

Claim One:
1. A non-transitory, computer readable storage medium storing a search program for a computer that is capable of accessing a group of nodes having divided-data structures obtained by dividing a data structure having a transposed hierarchical bloom filter of a hierarchical bloom filter and a set of data blocks by a predetermined bit width, wherein the hierarchical bloom filter has h-stage bloom filter arrays each having a bit width of “s”, the hth-stage bloom filter array having bits indicating false positives or negatives and the pth-stage bloom filter array having n=d [h-(p-1)] bloom filters (where 1≦p≦h) each having a bit width of m=s/d [h-(p-1)] (where d indicates a division number for the hth-stage bloom filter array), the transposed hierarchical bloom filter is obtained by grouping bits at the same positions in the bloom filters in the bloom filter array for each stage, and the set of data blocks corresponds to the first-stage bloom filter array of the hierarchical bloom filter, the search program causing the computer to execute a processing, the processing comprising: converting search-target data into pieces of position information indicating in-array positions of the transposed bloom filters, based on respective types of hash functions; identifying, in the pth-stage transposed bloom filter array, the pth-stage transposed bloom filters corresponding to the respective pieces of position information; obtaining the identified pth-stage transposed bloom filters from the nodes having the identified pth-stage transposed bloom filters; determining whether or not the bit positions of the bits indicating false positives are the same in the obtained pth-stage transposed bloom filters; determining whether or not the pth stage is the first stage, when it is determined that the bit positions of the bits indicating the false positives are the same; and obtaining, when it is determined that the pth stage is the first stage, a search result from at least one of the nodes having the data blocks corresponding to the bit positions of the bits indicating the false positives, the search result indicating whether or not the search-target data exists in the data block corresponding to the bit positions of the bits indicating the false positives.