| 摘要 |
PROBLEM TO BE SOLVED: To increase search speed of search using a Bloom filter. SOLUTION: (B) represents a transposition of a Bloom filter row BF(p). In the case of the transposition, bits at identical positions in each of the Bloom filters bf(p-1) to bf(p-4) are gathered, and bit strings each of which is gathered in accordance with the identical positions are arranged in order of a bit position. In the case of a Bloom filter row BF(p) in (C), since a fourth bit and an eighth bit in four Bloom filters bf(p-1) to bf(p-4) are referred to, 8 (=4X2) memory accesses are required. On the other hand, in the case of a transposed Bloom filter row tBF(p), determination can be performed by two memory accesses, that is, extraction of transposed Bloom filters tbf(p-4) and tbf(p-8), and an AND operation. Therefore, the frequency of memory access is reduced and the search speed is increased. COPYRIGHT: (C)2012,JPO&INPIT |
