Dynamic bloom filter for caching query results

A computer-implemented method for caching a corpus of information, the method comprising:

• populating a dynamic Bloom filter with a plurality of virtual bits, the plurality of virtual bits representative of information comprising the corpus, a given virtual bit operative to support two or more values;
• receiving a search request that identifies requested information from the corpus;
• checking one or more bits in the Bloom filter associated with the requested information to determine whether the requested information is present in the corpus;
• retrieving the requested information from the corpus on the basis of the result of the check;
• determining whether the requested information is represented in the Bloom filter;
• determining whether to represent the requested information in the Bloom filter where the requested information is not represented in the Bloom filter;
• adding the requested information to the Bloom filter in response to the determining step without blocking the Bloom filter;
• determining whether to continue to represent the requested information in the Bloom filter where the requested information is represented in the Bloom filter;
• removing old data associated with the requested information from the Bloom filter without blocking the Bloom filter and adding new data associated with the requested information to the Bloom filter without blocking the Bloom filter in response to a determination to continue to represent the requested information in the Bloom filter;
• removing the old data associated with the requested information from the Bloom filter without blocking the Bloom filter in response to a determination to not continue to represent the requested information in the Bloom filter;
• wherein removing old data associated with the requested information from the Bloom filter comprises identifying one or more virtual bits associated with the requested information from the dynamic Bloom filter, determining whether a value of a given identified virtual bit is less than or equal to a minimum value, decrementing the value of the given identified virtual bit where the value of the given identified virtual bit is less than or equal to the minimum value, recording an indication that the given identified virtual bit is less than or equal to the minimum value in an underflow cache where the given identified virtual bit is less than or equal to the minimum value, determining whether the underflow cache indicates an underflow condition, and cleaning the Bloom filter in response to the determination of the existence of an underflow condition.